排序演算法很多地方都會用到，近期又重新看了一遍演算法，並自己簡單地實作了一遍，特此記錄下來，為以後複習留點材料。
廢話不多說，以下逐一看看經典的排序演算法：
1. 選擇排序
選擇排序的基本思想是遍歷數組的過程中，以i 代表當前需要排序的序號，則需要在剩餘的[i…n-1] 中找出其中的最小值，然後將找到的最小值與i 指向的值進行交換。因為每一趟確定元素的過程中都會有一個選擇最大值的子流程，所以人們形像地稱之為選擇排序。舉個實例來看：
初始： [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
i = 0: [2 , 17, 16, 16, 7, 31, 39, 32, 38 , 11] (0th [38]<->8th [2])
i = 1: [2, 7 , 16, 16, 17 , 31, 39, 32, 38, 11] (1st [38]<->4th [17])
i = 2: [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] (2nd [11]<->9th [16])
i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] ( 無需交換)
i = 4: [2, 7, 11, 16, 16 , 31, 39, 32, 38, 17 ] (4th [17]<->9th [16])
i = 5: [2, 7, 11, 16, 16, 17 , 39, 32, 38, 31 ] (5th [31]<->9th [17])
i = 6: [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] (6th [39]<->9th [31])
i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 無交換)
i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 無交換)
i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 無交換)
由例子可以看出，選擇排序隨著排序的進行（ i 逐漸增大），比較的次數會越來越少，但是不論數組初始是否有序，選擇排序都會從i 至數組末尾進行一次選擇比較，所以給定長度的數組，選擇排序的比較次數是固定的： 1 + 2 + 3 + …. + n = n * (n + 1) / 2 ，而交換的次數則跟初始數組的順序有關，如果初始數組順序為隨機，則在最壞情況下，數組元素將會交換n 次，最好的情況下則可能0 次（數組本身即為有序）。
由此可推出，選擇排序的時間複雜度和空間複雜度分別為O(n2 ) 和O(1) （選擇排序只需要一個額外空間用於陣列元素交換）。
實現代碼：
複製代碼代碼如下:
/**
* Selection Sorting
*/
SELECTION(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = array.length;
for (int i = 0; i < len; i++) {
int selected = i;
for (int j = i + 1; j < len; j++) {
int compare = array[j].compareTo(array[selected]);
if (compare != 0 && compare < 0 == ascend) {
selected = j;
}
}
exchange(array, i, selected);
}
}
})
2. 插入排序
插入排序的基本思想是在遍歷數組的過程中，假設在序號i 之前的元素即[0..i-1] 都已經排好序，本趟需要找到i 對應的元素x 的正確位置k ，並且在尋找這個位置k 的過程中逐個將比較過的元素往後移一位，為元素x “騰位置”，最後將k 對應的元素值賦為x ，插入排序也是根據排序的特性來命名的。
以下是一個實例，紅色標記的數字為插入的數字，被劃掉的數字是未參與此次排序的元素，紅色標記的數字與被劃掉數字之間的元素為逐個向後移動的元素，例如第二次參與排序的元素為[11, 31, 12] ，需要插入的元素為12 ，但是12 目前並沒有處於正確的位置，於是我們需要依次與前面的元素31 、 11做比較，一邊比較一邊移動比較過的元素，直到找到第一個比12 小的元素11 時停止比較，此時31 對應的索引1 則是12 需要插入的位置。
初始： [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
第一趟： [11, 31 , 12, 5, 34, 30, 26, 38, 36, 18] （無移動的元素）
第二班： [11, 12 , 31, 5, 34, 30, 26, 38, 36, 18] （ 31 向後移動）
第三趟： [5 , 11, 12, 31, 34, 30, 26, 38, 36, 18] （ 11, 12, 31 皆向後移動）
第四班： [5, 11, 12, 31, 34 , 30, 26, 38, 36, 18] （無移動的元素）
第五班： [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] （ 31, 34 向後移動）
第六班： [5, 11, 12, 26 , 30, 31, 34, 38, 36, 18] （ 30, 31, 34 向後移動）
第七班： [5, 11, 12, 26, 30, 31, 34, 38 , 36, 18] （無移動的元素）
第八班： [5, 11, 12, 26, 30, 31, 34, 36 , 38, 18] （ 38 向後移動）
第九班： [5, 11, 12, 18 , 26, 30, 31, 34, 36, 38] （ 26, 30, 31, 34, 36, 38 向後移動）
插入排序會優於選擇排序，理由是它在排序過程中能夠利用前部分數組元素已經排好序的一個優勢，有效地減少一些比較的次數，當然這種優勢得看數組的初始順序如何，最壞的情況下（給定的數組恰好為倒序）插入排序需要比較和移動的次數將會等於1 + 2 + 3… + n = n * (n + 1) / 2 ，在這種極端情況下，插入排序的效率甚至比選擇排序更差。因此插入排序是一個不穩定的排序方法，插入效率與陣列初始順序息息相關。一般情況下，插入排序的時間複雜度和空間複雜度分別為O(n2 ) 和O(1) 。
實現代碼：
複製代碼代碼如下:
/**
* Insertion Sorting
*/
INSERTION(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = array.length;
for (int i = 1; i < len; i++) {
T toInsert = array[i];
int j = i;
for (; j > 0; j) {
int compare = array[j - 1].compareTo(toInsert);
if (compare == 0 || compare < 0 == ascend) {
break;
}
array[j] = array[j - 1];
}
array[j] = toInsert;
}
}
})
3. 冒泡排序
冒泡排序可以算是最經典的排序演算法了，記得小弟上學時最先接觸的也就是這個演算法了，因為實作方法最簡單，兩層for 循環，裡層循環中判斷相鄰兩個元素是否逆序，是的話將兩個元素交換，外層循環一次，就能將數組中剩下的元素中最小的元素「浮」到最前面，所以稱之為冒泡排序。
照例舉個簡單的實例吧：
初始狀態： [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
內層第一班： [24, 19, 26, 39, 36, 7, 31, 29, 23 , 38 ] （ 9th [23]<->8th [38 ）
內層第二趟： [24, 19, 26, 39, 36, 7, 31, 23 , 29 , 38] （ 8th [23]<->7th [29] ）
內層第三班： [24, 19, 26, 39, 36, 7, 23 , 31 , 29, 38] （ 7th [23]<->6th [31] ）
內層第四趟： [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] （ 7 、 23 都位於正確的順序，無需交換）
內層第五班： [24, 19, 26, 39, 7 , 36 , 23, 31, 29, 38] （ 5th [7]<->4th [36] ）
內層第六趟： [24, 19, 26, 7 , 39 , 36, 23, 31, 29, 38] （ 4th [7]<->3rd [39] ）
內層第七班： [24, 19, 7 , 26 , 39, 36, 23, 31, 29, 38] （ 3rd [7]<->2nd [26] ）
內層第八趟： [24, 7 , 19 , 26, 39, 36, 23, 31, 29, 38] （ 2nd [7]<->1st [19] ）
內層第九趟： [7 , 24 , 19, 26, 39, 36, 23, 31, 29, 38] （ 1st [7]<->0th [24] ）
……… .
其實冒泡排序跟選擇排序比較相像，比較次數一樣，都為n * (n + 1) / 2 ，但是冒泡排序在挑選最小值的過程中會進行額外的交換（冒泡排序在排序中只要發現相鄰元素的順序不對就會進行交換，與之對應的是選擇排序，只會在內層循環比較結束之後根據情況決定是否進行交換），所以在我看來，選擇排序屬於冒泡排序的改進版。
實現代碼：
複製代碼代碼如下:
/**
* Bubble Sorting, it's very similar with Insertion Sorting
*/
BUBBLE(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int length = array.length;
int lastExchangedIdx = 0;
for (int i = 0; i < length; i++) {
// mark the flag to identity whether exchange happened to false
boolean isExchanged = false;
// last compare and exchange happened before reaching index i
int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i;
for (int j = length 1; j > currOrderedIdx; j) {
int compare = array[j - 1].compareTo(array[j]);
if (compare != 0 && compare > 0 == ascend) {
exchange(array, j 1, j);
isExchanged = true;
lastExchangedIdx = j;
}
}
// if no exchange happen means array is already in order
if (isExchanged == false) {
break;
}
}
}
})
4. 希爾排序
希爾排序的誕生是由於插入排序在處理大規模陣列的時候會遇到需要移動太多元素的問題。希爾排序的想法是將一個大的數組“分而治之”，劃分為若干個小的數組，以gap 來劃分，比如數組[1, 2, 3, 4, 5, 6, 7, 8] ，如果以gap = 2 來劃分，可以分為[1, 3, 5, 7] 和[2, 4, 6, 8] 兩個數組（對應的，如gap = 3 ，則劃分的數組為： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然後分別對劃分出來的數組進行插入排序，待各個子數組排序完畢之後再減小gap 值重複進行之前的步驟，直至gap = 1 ，即對整個數組進行插入排序，此時的數組已經基本上快排好序了，所以需要移動的元素會很小很小，解決了插入排序在處理大規模數組時較多移動次數的問題。
具體實例請參考插入排序。
希爾排序是插入排序的改進版，在資料量大的時候對效率的提升幫助很大，資料量小的時候建議直接使用插入排序就好了。
實現代碼：
複製代碼代碼如下:
/**
* Shell Sorting
*/
SHELL(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int length = array.length;
int gap = 1;
// use the most next to length / 3 as the first gap
while (gap < length / 3) {
gap = gap * 3 + 1;
}
while (gap >= 1) {
for (int i = gap; i < length; i++) {
T next = array[i];
int j = i;
while (j >= gap) {
int compare = array[j - gap].compareTo(next);
// already find its position
if (compare == 0 || compare < 0 == ascend) {
break;
}
array[j] = array[j - gap];
j -= gap;
}
if (j != i) {
array[j] = next;
}
}
gap /= 3;
}
}
})
5. 歸併排序
歸併排序採用的是遞歸來實現，屬於“分而治之”，將目標數組從中間一分為二，之後分別對這兩個數組進行排序，排序完畢之後再將排好序的兩個數組“歸併”到一起，歸併排序最重要的也就是這個「歸併」的過程，歸併的過程中需要額外的跟需要歸併的兩個數組長度一致的空間，比如需要規定的數組分別為： [3, 6, 8, 11] 和[1, 3, 12, 15] （雖然邏輯上被劃為兩個數組，但實際上這些元素還是位於原來數組中的，只是透過一些index 將其劃分成兩個數組，原始數組為[3, 6, 8, 11, 1, 3, 12, 15 ，我們設定三個指針lo, mid, high 分別為0,3,7就可以實現邏輯上的子數組劃分）那麼需要的額外數組的長度為4 + 4 = 8 。歸併的過程可以簡要地概括為如下：
1） 將兩個子數組中的元素複製到新數組copiedArray 中，以前面提到的例子為例，則copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ；
2) 設定兩個指標分別指向原子數組中對應的第一個元素，假定這兩個指標取名為leftIdx 和rightIdx ，則leftIdx = 0 （對應copiedArray 中的第一個元素[3] ）， rightIdx = 4 （對應copiedArray 中的第五個元素[1] ）；
3) 比較leftIdx 和rightIdx 指向的陣列元素值，選取其中較小的一個並將其值賦給原數組中對應的位置i ，賦值完畢後分別對參與賦值的這兩個索引做自增1 操作，如果leftIdx 或rigthIdx 值已經達到對應數組的末尾，則餘下只需要將剩餘數組的元素按順序copy 到餘下的位置即可。
下面給個歸併的具體實例：
第一趟：
輔助數組[21 , 28, 39 | 35, 38] （數組被拆分為左右兩個子數組，以| 分隔開）
[21 , , , , ] （第一次21 與35 比較, 左邊子數組勝出， leftIdx = 0 ， i = 0 ）
第二趟：
輔助數組[21, 28 , 39 | 35, 38]
[21 , 28, , , ] （第二次28 與35 比較，左邊子數組勝出， leftIdx = 1 ， i = 1 ）
第三次： [21, 28, 39 | 35 , 38]
[21 , 28 , 35, , ] （第三次39 與35 比較，右邊子數組勝出， rightIdx = 0 ， i = 2 ）
第四班： [21, 28, 39 | 35, 38 ]
[21 , 28 , 35 , 38, ] （第四次39 與38 比較，右邊子數組勝出， rightIdx = 1 ， i = 3 ）
第五班： [21, 28, 39 | 35, 38]
[21 , 28 , 35 , 38 , 39] （第五次時右邊子數組已複製完，無需比較leftIdx = 2 ， i = 4 ）
以上便是一次歸併的過程，我們可以將整個需要排序的數組做有限次拆分（每次一分為二）直到分為長度為1 的小數組為止，長度為1 時數組已經不用排序了。在這之後再逆序（由於採用遞歸）依序對這些數組進行歸併操作，直到最後一次歸併長度為n / 2 的子數組，歸併完成之後數組排序也完成。
歸併排序所需的額外空間是所有排序中最多的，每次歸併需要與參與歸併的兩個數組長度之和相同個元素（為了提供輔助數組）。則可以推論歸併排序的空間複雜度為1 + 2 + 4 + … + n = n * ( n + 2) / 4 （忽略了n 的奇偶性的判斷），時間複雜度比較難估，這裡小弟也忘記是多少了（）。
實現代碼：
複製代碼代碼如下:
/**
* Merge sorting
*/
MERGE(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
this.sort(array, 0, array.length 1, ascend);
}
private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) {
// OPTIMIZE ONE
// if the substring's length is less than 20,
// use insertion sort to reduce recursive invocation
if (hi lo < 20) {
for (int i = lo + 1; i <= hi; i++) {
T toInsert = array[i];
int j = i;
for (; j > lo; j) {
int compare = array[j - 1].compareTo(toInsert);
if (compare == 0 || compare < 0 == ascend) {
break;
}
array[j] = array[j - 1];
}
array[j] = toInsert;
}
return;
}
int mid = lo + (hi lo) / 2;
sort(array, lo, mid, ascend);
sort(array, mid + 1, hi, ascend);
merge(array, lo, mid, hi, ascend);
}
private <T extends Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) {
// OPTIMIZE TWO
// if it is already in right order, skip this merge
// since there's no need to do so
int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);
if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) {
return;
}
@SuppressWarnings("unchecked")
T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
int lowIdx = 0;
int highIdx = mid lo + 1;
for (int i = lo; i <= hi; i++) {
if (lowIdx > mid lo) {
// left sub array exhausted
array[i] = arrayCopy[highIdx++];
} else if (highIdx > hi lo) {
// right sub array exhausted
array[i] = arrayCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) {
array[i] = arrayCopy[lowIdx++];
} else {
array[i] = arrayCopy[highIdx++];
}
}
}
})
6. 快速排序
快速排序也是用歸併方法實現的一個「分而治之」的排序演算法，它的魅力之處在於它能在每次partition （排序演算法的核心所在）都能為一個數組元素確定其排序最終正確位置（一次就定位準，下次循環就不考慮這個元素了）。