各種排序算法：冒擇路(入)兮(稀)快歸堆，桶式排序，基數排序
冒泡排序，選擇排序，插入排序，稀爾排序，快速排序，歸并排序，堆排序，桶式排序，基數排序
一、冒泡排序(BubbleSort)
1. 基本思想：
兩兩比較待排序數據元素的大小，發現兩個數據元素的次序相反時即進行交換，直到沒有反序的數據元素為止。
2. 排序過程：
設想被排序的數組R［1..N］垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最后任何兩個氣泡都是輕者在上，重者在下為止。
【示例】：
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
java代碼實現：
/**
* 冒泡排序：執行完一次內for循環后，最小的一個數放到了數組的最前面（跟那一個排序算法* 不一樣）。相鄰位置之間交換
*/
public class BubbleSort {
/**
* 排序算法的實現，對數組中指定的元素進行排序
* @param array 待排序的數組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
public void bubble(Integer[] array, int from, int end) {
//需array.length - 1輪比較
for (int k = 1; k < end - from + 1; k++) {
//每輪循環中從最后一個元素開始向前起泡，直到i=k止，即i等于輪次止
for (int i = end - from; i >= k; i--) {
//按照一種規則（后面元素不能小于前面元素）排序
if ((array[i].compareTo(array[i - 1])) < 0) {
//如果后面元素小于了（當然是大于還是小于要看比較器實現了）前面的元素，則前后交換
swap(array, i, i - 1);
}
}
}
}
/**
* 交換數組中的兩個元素的位置
* @param array 待交換的數組
* @param i 第一個元素
* @param j 第二個元素
*/
public void swap(Integer[] array, int i, int j) {
if (i != j) {//只有不是同一位置時才需交換
Integer tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 7, 2, 4, 3, 12, 1, 9, 6, 8, 5, 11, 10 };
BubbleSort bubblesort = new BubbleSort();
bubblesort.bubble(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
另外一種實現方式：
/**
冒泡排序：執行完一次內for循環后，最大的一個數放到了數組的最后面。相鄰位置之間交換
*/
public class BubbleSort2{
public static void main(String[] args){
int[] a = {3,5,9,4,7,8,6,1,2};
BubbleSort2 bubble = new BubbleSort2();
bubble.bubble(a);
for(int num:a){
System.out.print(num + " ");
}
}
public void bubble(int[] a){
for(int i=a.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(new Integer(a[j]).compareTo(new Integer(a[j+1]))>0){
swap(a,j,j+1);
}
}
}
}
public void swap(int[] a,int x,int y){
int temp;
temp=a[x];
a[x]=a[y];
a[y]=temp;
}
}
二、選擇排序
1. 基本思想：
每一趟從待排序的數據元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。
2. 排序過程：
【示例】：
初始關鍵字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 ［38 65 97 76 49 27 49]
第二趟排序后 13 27 ［65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序結果 13 27 38 49 49 76 76 97
java代碼實現：
/**
* 簡單選擇排序：執行完一次內for循環后最小的一個數放在了數組的最前面。
*/
public class SelectSort {
/**
* 排序算法的實現，對數組中指定的元素進行排序
* @param array 待排序的數組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
public void select(Integer[] array) {
int minIndex;//最小索引
/*
* 循環整個數組（其實這里的上界為 array.length - 1 即可，因為當 i= array.length-1
* 時，最后一個元素就已是最大的了，如果為array.length時，內層循環將不再循環），每輪假設
* 第一個元素為最小元素，如果從第一元素后能選出比第一個元素更小元素，則讓讓最小元素與第一
* 個元素交換
*/
for (int i=0; i<array.length; i++) {
minIndex = i;//假設每輪第一個元素為最小元素
//從假設的最小元素的下一元素開始循環
for (int j=i+1;j<array.length; j++) {
//如果發現有比當前array[smallIndex]更小元素，則記下該元素的索引于smallIndex中
if ((array[j].compareTo(array[minIndex])) < 0) {
minIndex = j;
}
}
//先前只是記錄最小元素索引，當最小元素索引確定后，再與每輪的第一個元素交換
swap(array, i, minIndex);
}
}
public static void swap(Integer[] intgArr,int x,int y){
//Integer temp; //這個也行
int temp;
temp=intgArr[x];
intgArr[x]=intgArr[y];
intgArr[y]=temp;
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
SelectSort insertSort = new SelectSort();
insertSort.select(intgArr);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
三、插入排序(Insertion Sort)
1. 基本思想：
每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。
2. 排序過程：
【示例】：
[初始關鍵字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
java代碼實現：
/**
* 直接插入排序：
* 注意所有排序都是從小到大排。
*/
public class InsertSort {
/**
* 排序算法的實現，對數組中指定的元素進行排序
* @param array 待排序的數組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
public void insert(Integer[] array, int from, int end) {
/*
* 第一層循環：對待插入（排序）的元素進行循環
* 從待排序數組斷的第二個元素開始循環，到最后一個元素（包括）止
*/
for (int i=from+1; i<=end; i++) {
/*
* 第二層循環：對有序數組進行循環，且從有序數組最第一個元素開始向后循環
* 找到第一個大于待插入的元素
* 有序數組初始元素只有一個，且為源數組的第一個元素，一個元素數組總是有序的
*/
for (int j = 0; j < i; j++) {
Integer insertedElem = array[i];//待插入到有序數組的元素
//從有序數組中最一個元素開始查找第一個大于待插入的元素
if ((array[j].compareTo(insertedElem)) > 0) {
//找到插入點后，從插入點開始向后所有元素后移一位
move(array, j, i - 1);
//將待排序元素插入到有序數組中
array[j] = insertedElem;
break;
}
}
}
//=======以下是java.util.Arrays的插入排序算法的實現
/*
* 該算法看起來比較簡潔一j點，有點像冒泡算法。
* 將數組邏輯上分成前后兩個集合，前面的集合是已經排序好序的元素，而后面集合為待排序的
* 集合，每次內層循從后面集合中拿出一個元素，通過冒泡的形式，從前面集合最后一個元素開
* 始往前比較，如果發現前面元素大于后面元素，則交換，否則循環退出
*
* 總感覺這種算術有點怪怪，既然是插入排序，應該是先找到插入點，而后再將待排序的元素插
* 入到的插入點上，那么其他元素就必然向后移，感覺算法與排序名稱不匹，但返過來與上面實
* 現比，其實是一樣的，只是上面先找插入點，待找到后一次性將大的元素向后移，而該算法卻
* 是走一步看一步，一步一步將待排序元素往前移
*/
/*
for (int i = from; i <= end; i++) {
for (int j = i; j > from && c.compare(array[j - 1], array[j]) > 0; j--) {
swap(array, j, j - 1);
}
}
*/
}
/**
* 數組元素后移
* @param array 待移動的數組
* @param startIndex 從哪個開始移
* @param endIndex 到哪個元素止
*/
public void move(Integer[] array, int startIndex, int endIndex) {
for (int i = endIndex; i >= startIndex; i--) {
array[i+1] = array[i];
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
InsertSort insertSort = new InsertSort();
insertSort.insert(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
四、稀爾排序
java代碼實現：
/**
* 插入排序----希爾排序：我們選擇步長為：15,7,3,1
* 我們選擇步長公式為：2^k-1,2^(k-1)-1,……,15,7,3,1 (2^4-1,2^3-1,2^2-1,2^1-1)
* 注意所有排序都是從小到大排。
*/
public class ShellSort {
/**
* 排序算法的實現，對數組中指定的元素進行排序
* @param array 待排序的數組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
public void sort(Integer[] array, int from, int end) {
//初始步長，實質為每輪的分組數
int step = initialStep(end - from + 1);
//第一層循環是對排序輪次進行循環。(step + 1) / 2 - 1 為下一輪步長值
for (; step >= 1; step = (step + 1) / 2 - 1) {
//對每輪里的每個分組進行循環
for (int groupIndex = 0; groupIndex < step; groupIndex++) {
//對每組進行直接插入排序
insertSort(array, groupIndex, step, end);
}
}
}
/**
* 直接插入排序實現
* @param array 待排序數組
* @param groupIndex 對每輪的哪一組進行排序
* @param step 步長
* @param end 整個數組要排哪個元素止
* @param c 比較器
*/
public void insertSort(Integer[] array, int groupIndex, int step, int end) {
int startIndex = groupIndex;//從哪里開始排序
int endIndex = startIndex;//排到哪里
/*
* 排到哪里需要計算得到，從開始排序元素開始，以step步長，可求得下元素是否在數組范圍內，
* 如果在數組范圍內，則繼續循環，直到索引超現數組范圍
*/
while ((endIndex + step) <= end) {
endIndex += step;
}
// i為每小組里的第二個元素開始
for (int i = groupIndex + step; i <= end; i += step) {
for (int j = groupIndex; j < i; j += step) {
Integer insertedElem = array[i];
//從有序數組中最一個元素開始查找第一個大于待插入的元素
if ((array[j].compareTo(insertedElem)) >= 0) {
//找到插入點后，從插入點開始向后所有元素后移一位
move(array, j, i - step, step);
array[j] = insertedElem;
break;
}
}
}
}
/**
* 根據數組長度求初始步長
*
* 我們選擇步長的公式為：2^k-1,2^(k-1)-1,...,15,7,3,1 ，其中2^k 減一即為該步長序列，k
* 為排序輪次
*
* 初始步長：step = 2^k-1
* 初始步長約束條件：step < len - 1 初始步長的值要小于數組長度還要減一的值（因
* 為第一輪分組時盡量不要分為一組，除非數組本身的長度就小于等于4）
*
* 由上面兩個關系試可以得知：2^k - 1 < len - 1 關系式，其中k為輪次，如果把 2^k 表 達式
* 轉換成 step 表達式，則 2^k-1 可使用 (step + 1)*2-1 替換（因為 step+1 相當于第k-1
* 輪的步長，所以在 step+1 基礎上乘以 2 就相當于 2^k 了），即步長與數組長度的關系不等式為
* (step + 1)*2 - 1 < len -1
*
* @param len 數組長度
* @return
*/
public static int initialStep(int len) {
/*
* 初始值設置為步長公式中的最小步長，從最小步長推導出最長初始步長值，即按照以下公式來推:
* 1,3,7,15,...,2^(k-1)-1,2^k-1
* 如果數組長度小于等于4時，步長為1，即長度小于等于4的數組不用分組，此時直接退化為直接插入排序
*/
int step = 1;
//試探下一個步長是否滿足條件，如果滿足條件，則步長置為下一步長
while ((step + 1) * 2 - 1 < len - 1) {
step = (step + 1) * 2 - 1;
}
System.out.println("初始步長 : " + step);
return step;
}
/**
* 以指定的步長將數組元素后移，步長指定每個元素間的間隔
* @param array 待排序數組
* @param startIndex 從哪里開始移
* @param endIndex 到哪個元素止
* @param step 步長
*/
protected final void move(Integer[] array, int startIndex, int endIndex, int step) {
for (int i = endIndex; i >= startIndex; i -= step) {
array[i + step] = array[i];
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 8, 2, 6, 3, 7, 0 };
ShellSort shellSort = new ShellSort();
shellSort.sort(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
五、快速排序（Quick Sort）
1. 基本思想：
在當前無序區R[1..H]中任取一個數據元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區劃分為左右兩個較小的無序區：R[1..I-1]和R[I+1..H]，且左邊的無序子區中數據元素均小于等于基準元素，右邊的無序子區中數據元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當R[1..I-1]和R[I+1..H]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區中的數據元素均已排序為止。
2. 排序過程：
【示例】：
初始關鍵字 ［49 38 65 97 76 13 27 49］
一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］
二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］
三趟排序之后 13 27 38 49 49 ［65］76 97
最后的排序結果 13 27 38 49 49 65 76 97
各趟排序之后的狀態
java代碼實現：
/**
* 快速排序：
*/
public class QuickSort {
/**
* 排序算法的實現，對數組中指定的元素進行排序
* @param array 待排序的數組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
//定義了一個這樣的公有方法sort，在這個方法體里面執行私有方法quckSort（這種方式值得借鑒）。
public void sort(Integer[] array, int from, int end) {
quickSort(array, from, end);
}
/**
* 遞歸快速排序實現
* @param array 待排序數組
* @param low 低指針
* @param high 高指針
* @param c 比較器
*/
private void quickSort(Integer[] array, int low, int high) {
/*
* 如果分區中的低指針小于高指針時循環；如果low=higth說明數組只有一個元素，無需再處理；
* 如果low > higth，則說明上次樞紐元素的位置pivot就是low或者是higth，此種情況
* 下分區不存，也不需處理
*/
if (low < high) {
//對分區進行排序整理
//int pivot = partition1(array, low, high);
int pivot = partition2(array, low, high);
//int pivot = partition3(array, low, high);
/*
* 以pivot為邊界，把數組分成三部分[low, pivot - 1]、[pivot]、[pivot + 1, high]
* 其中[pivot]為樞紐元素，不需處理，再對[low, pivot - 1]與[pivot + 1, high]
* 各自進行分區排序整理與進一步分區
*/
quickSort(array, low, pivot - 1);
quickSort(array, pivot + 1, high);
}
}
/**
* 實現一
*
* @param array 待排序數組
* @param low 低指針
* @param high 高指針
* @param c 比較器
* @return int 調整后中樞位置
*/
private int partition1(Integer[] array, int low, int high) {
Integer pivotElem = array[low];//以第一個元素為中樞元素
//從前向后依次指向比中樞元素小的元素，剛開始時指向中樞，也是小于與大小中樞的元素的分界點
int border = low;
/*
* 在中樞元素后面的元素中查找小于中樞元素的所有元素，并依次從第二個位置從前往后存放
* 注，這里最好使用i來移動，如果直接移動low的話，最后不知道數組的邊界了，但后面需要
* 知道數組的邊界
*/
for (int i = low + 1; i <= high; i++) {
//如果找到一個比中樞元素小的元素
if ((array[i].compareTo(pivotElem)) < 0) {
swap(array, ++border, i);//border前移，表示有小于中樞元素的元素
}
}
/*
* 如果border沒有移動時說明說明后面的元素都比中樞元素要大，border與low相等，此時是
* 同一位置交換，是否交換都沒關系；當border移到了high時說明所有元素都小于中樞元素，此
* 時將中樞元素與最后一個元素交換即可，即low與high進行交換，大的中樞元素移到了 序列最
* 后；如果 low <minIndex< high，表 明中樞后面的元素前部分小于中樞元素，而后部分大于
* 中樞元素，此時中樞元素與前部分數組中最后一個小于它的元素交換位置，使得中樞元素放置在
* 正確的位置
*/
swap(array, border, low);
return border;
}
/**
* 實現二
*
* @param array 待排序數組
* @param low 待排序區低指針
* @param high 待排序區高指針
* @param c 比較器
* @return int 調整后中樞位置
*/
private int partition2(Integer[] array, int low, int high) {
int pivot = low;//中樞元素位置，我們以第一個元素為中樞元素
//退出條件這里只可能是 low = high
while (true) {
if (pivot != high) {//如果中樞元素在低指針位置時，我們移動高指針
//如果高指針元素小于中樞元素時，則與中樞元素交換
if ((array[high].compareTo(array[pivot])) < 0) {
swap(array, high, pivot);
//交換后中樞元素在高指針位置了
pivot = high;
} else {//如果未找到小于中樞元素，則高指針前移繼續找
high--;
}
} else {//否則中樞元素在高指針位置
//如果低指針元素大于中樞元素時，則與中樞元素交換
if ((array[low].compareTo(array[pivot])) > 0) {
swap(array, low, pivot);
//交換后中樞元素在低指針位置了
pivot = low;
} else {//如果未找到大于中樞元素，則低指針后移繼續找
low++;
}
}
if (low == high) {
break;
}
}
//返回中樞元素所在位置，以便下次分區
return pivot;
}
/**
* 實現三
*
* @param array 待排序數組
* @param low 待排序區低指針
* @param high 待排序區高指針
* @param c 比較器
* @return int 調整后中樞位置
*/
private int partition3(Integer[] array, int low, int high) {
int pivot = low;//中樞元素位置，我們以第一個元素為中樞元素
low++;
//----調整高低指針所指向的元素順序，把小于中樞元素的移到前部分，大于中樞元素的移到后面部分
//退出條件這里只可能是 low = high
while (true) {
//如果高指針未超出低指針
while (low < high) {
//如果低指針指向的元素大于或等于中樞元素時表示找到了，退出，注：等于時也要后移
if ((array[low].compareTo(array[pivot])) >= 0) {
break;
} else {//如果低指針指向的元素小于中樞元素時繼續找
low++;
}
}
while (high > low) {
//如果高指針指向的元素小于中樞元素時表示找到，退出
if ((array[high].compareTo(array[pivot])) < 0) {
break;
} else {//如果高指針指向的元素大于中樞元素時繼續找
high--;
}
}
//退出上面循環時 low = high
if (low == high) {
break;
}
swap(array, low, high);
}
//----高低指針所指向的元素排序完成后，還得要把中樞元素放到適當的位置
if ((array[pivot].compareTo(array[low])) > 0) {
//如果退出循環時中樞元素大于了低指針或高指針元素時，中樞元素需與low元素交換
swap(array, low, pivot);
pivot = low;
} else if ((array[pivot].compareTo(array[low])) <= 0) {
swap(array, low - 1, pivot);
pivot = low - 1;
}
//返回中樞元素所在位置，以便下次分區
return pivot;
}
/**
* 交換數組中的兩個元素的位置
* @param array 待交換的數組
* @param i 第一個元素
* @param j 第二個元素
*/
public void swap(Integer[] array, int i, int j) {
if (i != j) {//只有不是同一位置時才需交換
Integer tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
QuickSort quicksort = new QuickSort();
quicksort.sort(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
六、歸并排序
java代碼實現：
/**
歸并排序：里面是一個遞歸程序，深刻理解之。
*/
public class MergeSort{
/**
* 遞歸劃分數組
* @param arr
* @param from
* @param end
* @param c void
*/
public void partition(Integer[] arr, int from, int end) {
//劃分到數組只有一個元素時才不進行再劃分
if (from < end) {
//從中間劃分成兩個數組
int mid = (from + end) / 2;
partition(arr, from, mid);
partition(arr, mid + 1, end);
//合并劃分后的兩個數組
merge(arr, from, end, mid);
}
}
/**
* 數組合并，合并過程中對兩部分數組進行排序
* 前后兩部分數組里是有序的
* @param arr
* @param from
* @param end
* @param mid
* @param c void
*/
public void merge(Integer[] arr, int from, int end, int mid) {
Integer[] tmpArr = new Integer[10];
int tmpArrIndex = 0;//指向臨時數組
int part1ArrIndex = from;//指向第一部分數組
int part2ArrIndex = mid + 1;//指向第二部分數組
//由于兩部分數組里是有序的，所以每部分可以從第一個元素依次取到最后一個元素，再對兩部分
//取出的元素進行比較。只要某部分數組元素取完后，退出循環
while ((part1ArrIndex <= mid) && (part2ArrIndex <= end)) {
//從兩部分數組里各取一個進行比較，取最小一個并放入臨時數組中
if (arr[part1ArrIndex] - arr[part2ArrIndex] < 0) {
//如果第一部分數組元素小，則將第一部分數組元素放入臨時數組中，并且臨時數組指針
//tmpArrIndex下移一個以做好下次存儲位置準備，前部分數組指針part1ArrIndex
//也要下移一個以便下次取出下一個元素與后部分數組元素比較
tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];
} else {
//如果第二部分數組元素小，則將第二部分數組元素放入臨時數組中
tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];
}
}
//由于退出循環后，兩部分數組中可能有一個數組元素還未處理完，所以需要額外的處理，當然不可
//能兩部分數組都有未處理完的元素，所以下面兩個循環最多只有一個會執行，并且都是大于已放入
//臨時數組中的元素
while (part1ArrIndex <= mid) {
tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];
}
while (part2ArrIndex <= end) {
tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];
}
//最后把臨時數組拷貝到源數組相同的位置
System.arraycopy(tmpArr, 0, arr, from, end - from + 1);
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = {5,9,1,4,2,6,3,8,0,7};
MergeSort insertSort = new MergeSort();
insertSort.partition(intgArr,0,intgArr.length-1);
for(Integer a:intgArr){
System.out.print(a + " ");
}
}
}
七、堆排序(Heap Sort)
1. 基本思想：
堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
2. 堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性：
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])
堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉子結點的關鍵字均大于等于其孩子結點的關鍵字。例如序列10,15,56,25,30,70就是一個堆，它對應的完全二叉樹如上圖所示。這種堆中根結點（稱為堆頂）的關鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結點的關鍵字均大于等于其孩子的關鍵字，則稱之為大根堆。
3. 排序過程：
堆排序正是利用小根堆（或大根堆）來選取當前無序區中關鍵字小（或最大）的記錄實現排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當前無序區調整為一個大根堆，選取關鍵字最大的堆頂記錄，將它和無序區中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區是在原記錄區的尾部形成并逐步向前擴大到整個記錄區。
【示例】：對關鍵字序列42，13，91，23，24，16，05，88建堆
java代碼實現：
/**
* 選擇排序之堆排序：
*/
public class HeapSort {
/**
* 排序算法的實現，對數組中指定的元素進行排序
* @param array 待排序的數組
* @param from 從哪里開始排序
* @param end 排到哪里
* @param c 比較器
*/
public void sort(Integer[] array, int from, int end) {
//創建初始堆
initialHeap(array, from, end);
/*
* 對初始堆進行循環，且從最后一個節點開始，直接樹只有兩個節點止
* 每輪循環后丟棄最后一個葉子節點，再看作一個新的樹
*/
for (int i = end - from + 1; i >= 2; i--) {
//根節點與最后一個葉子節點交換位置，即數組中的第一個元素與最后一個元素互換
swap(array, from, i - 1);
//交換后需要重新調整堆
adjustNote(array, 1, i - 1);
}
}
/**
* 初始化堆
* 比如原序列為：7,2,4,3,12,1,9,6,8,5,10,11
* 則初始堆為：1,2,4,3,5,7,9,6,8,12,10,11
* @param arr 排序數組
* @param from 從哪
* @param end 到哪
* @param c 比較器
*/
private void initialHeap(Integer[] arr, int from, int end) {
int lastBranchIndex = (end - from + 1) / 2;//最后一個非葉子節點
//對所有的非葉子節點進行循環 ，且從最一個非葉子節點開始
for (int i = lastBranchIndex; i >= 1; i--) {
adjustNote(arr, i, end - from + 1);
}
}
/**
* 調整節點順序，從父、左右子節點三個節點中選擇一個最大節點與父節點轉換
* @param arr 待排序數組
* @param parentNodeIndex 要調整的節點，與它的子節點一起進行調整
* @param len 樹的節點數
* @param c 比較器
*/
private void adjustNote(Integer[] arr, int parentNodeIndex, int len) {
int minNodeIndex = parentNodeIndex;
//如果有左子樹，i * 2為左子節點索引
if (parentNodeIndex * 2 <= len) {
//如果父節點小于左子樹時
if ((arr[parentNodeIndex - 1].compareTo(arr[parentNodeIndex * 2 - 1])) < 0) {
minNodeIndex = parentNodeIndex * 2;//記錄最大索引為左子節點索引
}
// 只有在有或子樹的前提下才可能有右子樹，再進一步斷判是否有右子樹
if (parentNodeIndex * 2 + 1 <= len) {
//如果右子樹比最大節點更大
if ((arr[minNodeIndex - 1].compareTo(arr[(parentNodeIndex * 2 + 1) - 1])) < 0) {
minNodeIndex = parentNodeIndex * 2 + 1;//記錄最大索引為右子節點索引
}
}
}
//如果在父節點、左、右子節點三都中，最大節點不是父節點時需交換，把最大的與父節點交換，創建大頂堆
if (minNodeIndex != parentNodeIndex) {
swap(arr, parentNodeIndex - 1, minNodeIndex - 1);
//交換后可能需要重建堆，原父節點可能需要繼續下沉
if (minNodeIndex * 2 <= len) {//是否有子節點，注，只需判斷是否有左子樹即可知道
adjustNote(arr, minNodeIndex, len);
}
}
}
/**
* 交換數組中的兩個元素的位置
* @param array 待交換的數組
* @param i 第一個元素
* @param j 第二個元素
*/
public void swap(Integer[] array, int i, int j) {
if (i != j) {//只有不是同一位置時才需交換
Integer tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/**
* 測試
* @param args
*/
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
HeapSort heapsort = new HeapSort();
heapsort.sort(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + " ");
}
}
}
八、桶式排序
java代碼實現：
/**
* 桶式排序:
* 桶式排序不再是基于比較的了，它和基數排序同屬于分配類的排序，
* 這類排序的特點是事先要知道待排 序列的一些特征。
* 桶式排序事先要知道待排 序列在一個范圍內，而且這個范圍應該不是很大的。
* 比如知道待排序列在[0,M）內，那么可以分配M個桶，第I個桶記錄I的出現情況，
* 最后根據每個桶收到的位置信息把數據輸出成有序的形式。
* 這里我們用兩個臨時性數組，一個用于記錄位置信息，一個用于方便輸出數據成有序方式，
* 另外我們假設數據落在0到MAX,如果所給數據不是從0開始，你可以把每個數減去最小的數。
*/
public class BucketSort {
public void sort(int[] keys,int from,int len,int max)
{
int[] temp=new int[len];
int[] count=new int[max];
for(int i=0;i<len;i++)
{
count[keys[from+i]]++;
}
//calculate position info
for(int i=1;i<max;i++)
{
count[i]=count[i]+count[i-1];//這意味著有多少數目小于或等于i，因此它也是position+ 1
}
System.arraycopy(keys, from, temp, 0, len);
for(int k=len-1;k>=0;k--)//從最末到開頭保持穩定性
{
keys[--count[temp[k]]]=temp[k];// position +1 =count
}
}
/**
* @param args
*/
public static void main(String[] args) {
int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16};
BucketSort bucketSort=new BucketSort();
bucketSort.sort(a,0,a.length,20);//actually is 18, but 20 will also work
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+",");
}
}
}
九、基數排序
java代碼實現：
/**
* 基數排序：
*/
import java.util.Arrays;
public class RadixSort {
/**
* 取數x上的第d位數字
* @param x 數
* @param d 第幾位，從低位到高位
* @return
*/
public int digit(long x, long d) {
long pow = 1;
while (--d > 0) {
pow *= 10;
}
return (int) (x / pow % 10);
}
/**
* 基數排序實現，以升序排序（下面程序中的位記錄器count中，從第0個元素到第9個元素依次用來
* 記錄當前比較位是0的有多少個..是9的有多少個數，而降序時則從第0個元素到第9個元素依次用來
* 記錄當前比較位是9的有多少個..是0的有多少個數）
* @param arr 待排序數組
* @param digit 數組中最大數的位數
* @return
*/
public long[] radixSortAsc(long[] arr) {
//從低位往高位循環
for (int d = 1; d <= getMax(arr); d++) {
//臨時數組，用來存放排序過程中的數據
long[] tmpArray = new long[arr.length];
//位記數器，從第0個元素到第9個元素依次用來記錄當前比較位是0的有多少個..是9的有多少個數
int[] count = new int[10];
//開始統計0有多少個，并存儲在第0位，再統計1有多少個，并存儲在第1位..依次統計到9有多少個
for (int i = 0; i < arr.length; i++) {
count[digit(arr[i], d)] += 1;
}
/*
* 比如某次經過上面統計后結果為：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]則經過下面計算后 結果為：
* [0, 2, 5, 8, 8, 8, 8, 8, 8, 8]但實質上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中
* 非零數才用到，因為其他位不存在，它們分別表示如下：2表示比較位為1的元素可以存放在索引為1、0的
* 位置，5表示比較位為2的元素可以存放在4、3、2三個(5-2=3)位置，8表示比較位為3的元素可以存放在
* 7、6、5三個(8-5=3)位置
*/
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
/*
* 注，這里只能從數組后往前循環，因為排序時還需保持以前的已排序好的 順序，不應該打
* 亂原來已排好的序，如果從前往后處理，則會把原來在前面會擺到后面去，因為在處理某個
* 元素的位置時，位記數器是從大到到小（count[digit(arr[i], d)]--）的方式來處
* 理的，即先存放索引大的元素，再存放索引小的元素，所以需從最后一個元素開始處理。
* 如有這樣的一個序列[212,213,312]，如果按照從第一個元素開始循環的話，經過第一輪
* 后（個位）排序后，得到這樣一個序列[312,212,213]，第一次好像沒什么問題，但問題會
* 從第二輪開始出現，第二輪排序后，會得到[213,212,312]，這樣個位為3的元素本應該
* 放在最后，但經過第二輪后卻排在了前面了，所以出現了問題
*/
for (int i = arr.length - 1; i >= 0; i--) {//只能從最后一個元素往前處理
//for (int i = 0; i < arr.length; i++) {//不能從第一個元素開始循環
tmpArray[count[digit(arr[i], d)] - 1] = arr[i];
count[digit(arr[i], d)]--;
}
System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
}
return arr;
}
/**
* 基數排序實現，以降序排序（下面程序中的位記錄器count中，從第0個元素到第9個元素依次用來
* 記錄當前比較位是0的有多少個..是9的有多少個數，而降序時則從第0個元素到第9個元素依次用來
* 記錄當前比較位是9的有多少個..是0的有多少個數）
* @param arr 待排序數組
* @return
*/
public long[] radixSortDesc(long[] arr) {
for (int d = 1; d <= getMax(arr); d++) {
long[] tmpArray = new long[arr.length];
//位記數器，從第0個元素到第9個元素依次用來記錄當前比較位是9的有多少個..是0的有多少個數
int[] count = new int[10];
//開始統計0有多少個，并存儲在第9位，再統計1有多少個，并存儲在第8位..依次統計
//到9有多少個，并存儲在第0位
for (int i = 0; i < arr.length; i++) {
count[9 - digit(arr[i], d)] += 1;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
tmpArray[count[9 - digit(arr[i], d)] - 1] = arr[i];
count[9 - digit(arr[i], d)]--;
}
System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
}
return arr;
}
private int getMax(long[] array) {
int maxlIndex = 0;
for (int j = 1; j < array.length; j++) {
if (array[j] > array[maxlIndex]) {
maxlIndex = j;
}
}
return String.valueOf(array[maxlIndex]).length();
}
public static void main(String[] args) {
long[] ary = new long[] { 123, 321, 132, 212, 213, 312, 21, 223 };
RadixSort rs = new RadixSort();
System.out.println("升 - " + Arrays.toString(rs.radixSortAsc(ary)));
ary = new long[] { 123, 321, 132, 212, 213, 312, 21, 223 };
System.out.println("降 - " + Arrays.toString(rs.radixSortDesc(ary)));
}
}
十、幾種排序算法的比較和選擇
1. 選取排序方法需要考慮的因素：
(1) 待排序的元素數目n；
(2) 元素本身信息量的大小；
(3) 關鍵字的結構及其分布情況；
(4) 語言工具的條件，輔助空間的大小等。
2. 小結：
(1) 若n較小(n <= 50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。
(2) 若文件的初始狀態已按關鍵字基本有序，則選用直接插入或冒泡排序為宜。
(3) 若n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。 快速排序是目前基于比較的內部排序法中被認為是最好的方法。
(4) 在基于比較排序方法中，每次比較兩個關鍵字的大小之后，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當文件的n個關鍵字隨機分布時，任何借助于"比較"的排序算法，至少需要O(nlog2n)的時間。
(5) 當記錄本身信息量較大時，為避免耗費大量時間移動記錄，可以用鏈表作為存儲結構。
排序簡介
排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中占有很大比重;并且排序本身對推動算法分析的發展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，并對它們進行分析和比較。
1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸并排序；
5、基數排序；
學習重點
1、掌握排序的基本概念和各種排序方法的特點，并能加以靈活應用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸并排序的方法及其性能分析方法；
3、了解基數排序方法及其性能分析方法。
排序（sort）或分類
所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
1．被排序對象--文件
被排序的對象--文件由一組記錄組成。
記錄則由若干個數據項(或域)組成。其中有一項可用來標識一個記錄，稱為關鍵字項。該數據項的值稱為關鍵字(Key)。
注意：
在不易產生混淆時，將關鍵字項簡稱為關鍵字。
2．排序運算的依據--關鍵字
用來作排序運算依據的關鍵字，可以是數字類型，也可以是字符類型。
關鍵字的選取應根據問題的要求而定。
【例】在高考成績統計中將每個考生作為一個記錄。每條記錄包含準考證號、姓名、各科的分數和總分數等項內容。若要惟一地標識一個考生的記錄，則必須用"準考證號"作為關鍵字。若要按照考生的總分數排名次，則需用"總分數"作為關鍵字。
排序的穩定性
當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。
在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序后這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。
注意：
排序算法的穩定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得算法不滿足穩定性要求，則該排序算法就是不穩定的。
排序方法的分類
1．按是否涉及數據的內、外存交換分
在排序過程中，若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換，則稱之為內部排序(簡稱內排序)；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。
注意：
① 內排序適用于記錄個數不很多的小文件
② 外排序則適用于記錄個數太多，不能一次將其全部記錄放人內存的大文件。
2．按策略劃分內部排序方法
可以分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。
排序算法分析
1．排序算法的基本操作
大多數排序算法都有兩個基本的操作：
(1) 比較兩個關鍵字的大?。?
(2) 改變指向記錄的指針或移動記錄本身。
注意：
第(2)種基本操作的實現依賴于待排序記錄的存儲方式。
2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結構
排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置）
（2） 以鏈表作為存儲結構
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序；
（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用于難于在鏈表上實現，仍需避免排序過程中移動記錄的排序方法。
3．排序算法性能評價
（1） 評價排序算法好壞的標準
評價排序算法好壞的標準主要有兩條：
① 執行時間和所需的輔助空間
② 算法本身的復雜程度
（2） 排序算法的空間復雜度
若排序算法所需的輔助空間并不依賴于問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。
（3） 排序算法的時間開銷
大多數排序算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序算法其執行時間不僅依賴于問題的規模，還取決于輸入實例中數據的狀態。
文件的順序存儲結構表示
#define n l00 //假設的文件長度，即待排序的記錄數目
typedef int KeyType； //假設的關鍵字類型
typedef struct{ //記錄類型
KeyType key； //關鍵字項
InfoType otherinfo；//其它數據項，類型InfoType依賴于具體應用而定義
}RecType；
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
注意：
若關鍵字類型沒有比較算符，則可事先定義宏或函數來表示比較運算。
【例】關鍵字為字符串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。
按平均時間將排序分為四類：
（1）平方階(O(n2))排序
一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；
（2）線性對數階(O(nlgn))排序
如快速、堆和歸并排序；
（3）O(n1+￡)階排序
￡是介于0和1之間的常數，即0<￡<1，如希爾排序；
（4）線性階(O(n))排序
如桶、箱和基數排序。
各種排序方法比較
簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。
影響排序效果的因素
因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥存儲結構；
⑦時間和輔助空間復雜度等。
不同條件下，排序方法的選擇
(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少于直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。
快速排序是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序所需的輔助空間少于快速排序，并且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
若要求排序穩定，則可選用歸并排序。但本章介紹的從單個記錄起進行兩兩歸并的 排序算法并不值得提倡，通?？梢詫⑺椭苯硬迦肱判蚪Y合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸并之。因為直接插入排序是穩定的，所以改進后的歸并排序仍是穩定的。
4)在基于比較的排序方法中，每次比較兩個關鍵字的大小之后，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。
當文件的n個關鍵字隨機分布時，任何借助于"比較"的排序算法，至少需要O(nlgn)的時間。
箱排序和基數排序只需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數排序可能在O(n)時間內完成對n個記錄的排序。但是，箱排序和基數排序只適用于像字符串和整數這類有明顯結構特征的關鍵字，而當關鍵字的取值范圍屬于某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時只有借助于"比較"的方法來排序。
若n很大，記錄的關鍵字位數較少且可以分解時，采用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也只有在關鍵字是隨機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種分配排序均假定了關鍵字若為數字時，則其值均是非負的，否則將其映射到箱(桶)號時，又要增加相應的時間。
(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導致實現歸并、快速(它們用遞歸實現較簡單)和基數(使用了指針)等排序算法變得復雜。此時可考慮用其它排序。
(6)本章給出的排序算法，輸人數據均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結構。譬如插入排序、歸并排序、基數排序都易于在鏈表上實現，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在鏈表上卻難于實現，在這種情況下，可以提取關鍵字建立索引表，然后對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結束后，向量t就指示了記錄之間的順序關系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結束后，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。