作者：失控的的狗蛋~

來源：CSDN

排序算法

待排序的元素需要實現 JAVA 的 Comparable 接口，該接口有 compareTo() 方法，可以用它來判斷兩個元素的大小關系。

使用輔助函數 less() 和 swap() 來進行比較和交換的操作，使得代碼的可讀性和可移植性更好。

敲黑板：排序算法的成本模型是比較和交換的次數，也是衡量排序算法的好壞的方式。

選擇排序（Selection Sort）

從數組中選擇最小元素，將它與數組的第一個元素交換位置。再從數組剩下的元素中選擇出最小的元素，將它與數組的第二個元素交換位置。不斷進行這樣的操作，直到將整個數組排序。

選擇排序需要 ~N2/2 次比較和 ~N 次交換，它的運行時間與輸入無關，這個特點使得它對一個已經排序的數組也需要這么多的比較和交換操作。

看一張動圖（動圖網站鏈接在下面大家沒事可以去看看，那個網站有各種算法可以模擬過程讓你更直觀的理解算法）

• 冒泡排序（Bubble Sort）

從左到右不斷交換相鄰逆序的元素，在一輪的循環之后，可以讓未排序的最大元素上浮到右側。

在一輪循環中，如果沒有發生交換，那么說明數組已經是有序的，此時可以直接退出。

插入排序（Insertion Sort）

每次都將當前元素插入到左側已經排序的數組中，使得插入之后左側數組依然有序。

對于數組 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交換相鄰元素，令逆序數量減少 1，因此插入排序需要交換的次數為逆序數量。

插入排序的時間復雜度取決于數組的初始順序，如果數組已經部分有序了，那么逆序較少，需要的交換次數也就較少，時間復雜度較低。

平均情況下插入排序需要 ~N2/4 比較以及 ~N2/4 次交換；

最壞的情況下需要 ~N2/2 比較以及 ~N2/2 次交換，最壞的情況是數組是倒序的；

最好的情況下需要 N-1 次比較和 0 次交換，最好的情況就是數組已經有序了

希爾排序（Shell Sort）

對于大規模的數組，插入排序很慢，因為它只能交換相鄰的元素，每次只能將逆序數量減少 1。希爾排序的出現就是為了解決插入排序的這種局限性，它通過交換不相鄰的元素，每次可以將逆序數量減少大于 1。

希爾排序使用插入排序對間隔 h 的序列進行排序。通過不斷減小 h，最后令 h=1，就可以使得整個數組是有序的。

• 歸并排序（Merge Sort）

歸并排序的思想是將數組分成兩部分，分別進行排序，然后歸并起來。

1. 歸并方法

歸并方法將數組中兩個已經排序的部分歸并成一個。

2. 自頂向下歸并排序

將一個大數組分成兩個小數組去求解。

因為每次都將問題對半分成兩個子問題，這種對半分的算法復雜度一般為 O(NlogN)。

3. 自底向上歸并排序

先歸并那些微型數組，然后成對歸并得到的微型數組。

快速排序（Quick Sort）

快速排序的基本思想：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：

從數列中挑出一個元素，稱為 “基準”（pivot）；

重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作；

遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

排序算法比較

Java 的排序算法實現

Java 主要排序方法為 java.util.Arrays.sort()，對于原始數據類型使用三向切分的快速排序，對于引用類型使用歸并排序。