java常見排序算法有哪些_Java中常用的6種排序算法詳細分解

排序算法很多地方都會用到，近期又重新看了一遍算法，并自己簡單地實現了一遍，特此記錄下來，為以后復習留點材料。

廢話不多說，下面逐一看看經典的排序算法：

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 > 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 > 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 > 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 > 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 > void sort(T[] array, boolean ascend) {

this.sort(array, 0, array.length – 1, ascend);

}

private > 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) {