八大排序(玩命整理)

04-08

八大排序演算法的關係如下:

性能比較：

下面慢慢分析各大排序演算法的原理實現和性能，慢慢來....不急，一個一個來！！

直插排序

原理

對於第 i 個元素，其前面 i - 1 個元素已經有序，遍歷前面的 i - 1 個有序元素，將這個元素插入到合適的的位置中，依次類推。

演算法實現

public void insertSort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) { // 從第二個元素開始，默認第一個已經有序 if (arr[i] < arr[i - 1]) { // 倒序遍歷前 i - 1 個有序元素 int temp = arr[i]; for (int j = i - 1; j >= 0 & temp < arr[j]; j--) { arr[j + 1] = arr[j]; // 依次往後挪動元素 } arr[j + 1] = temp; // 插入位置 } }}

分析

① 最好情況：

元素全部有序，第個元素開始在遍歷時都不會滿足if (arr[i] < arr[i - 1]) 這個條件，因此只會進行 n - 1次比較，時間複雜度為O(n)。

② 最壞情況：

元素為逆序，需要比較次數為：1 + 2 + … + (n - 1) = n * (n - 1) / 2 次，因此時間複雜度為O(n2)。

希爾排序

原理

希爾排序(Shell Sort)又叫縮小增量排序。

設定一個初始步長，對元素進行分組的插入排序，然後逐漸縮小步長，每縮小一次步長，就會對同組元素進行一次插入排序，直到步長為0。

好處：剛開始步長最大，需要插入排序的元素少，速度快；而步長很小時元素都基本有序了，需要挪動的元素少，速度快。

我們還需要知道的是，希爾排序是對直接插入排序的一個改進，可以理解成先分組再直插排序。

簡單選擇排序

原理

簡單選擇排序很簡單…假設數組長度為n，第一次從n個裡面選擇最小的數與arr[0]交換，第二次從後 n - 1 個數中選最小的與arr[1]交換... 以此類推。

演算法實現

public void easySelectSort(int[] arr) { int len = arr.length; for (int i = 0; i < len; i++) { int min = i; for (int j = i + 1; j < len; j++) { // 找最小的元素下標 → min if (arr[j] < arr[min]) { min = j; } } if (min != i) { // 交換 int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } }}

分析

由於簡單選擇排序演算法每次都要遍歷一次剩下的元素，然後決定交換問題，所以遍歷這一步都是無法避免的。所以比較次數都為 (n - 1) + (n - 2) + … + 1 = n * (n - 1) / 2 → O(n2)。

所以最好和最壞情況都是一毛一樣滴。

堆排序

原理

我們將原始數組抽象成一個堆的結構:

根據這個結構我們可以知道的是: 第 i 個結點其左右子節點分別是 arr[i * 2 + 1] 和 arr[i* 2 + 2]，arr[0]為堆的根節點。

堆排序主要其實就是進行兩步操作：1）構建大頂堆；2）通過選擇和調整堆來構建有序的結果。

說起來有點抽象，我們直接上規則：

① 構建大頂堆

從第一個非葉子節點的點開始調整結點順序，使其成為大頂堆。(第一個非葉節點為arr[len / 2 - 1])
判斷每一組(基準結點+其左右孩子節點)是否滿足大頂堆結構，若不滿足，則將最大孩子節點和基準結點交換
重複上述步驟，直到構建為大頂堆

② 調整堆，使其成為有序數組

從最後一個節點開始，與根節點作交換
交換後，忽略交換過的節點，調整剩餘堆的結構，使其成為大頂堆
重複以上步驟，直到所有元素交換完畢(這樣能保證每一次交換後，最大的元素都換到下面去了)

放一張過程示意圖:

演算法實現

public void heapSort(int[] arr) { int len = arr.length; // ① 構建大頂堆 // 從第一個不是葉子節點的開始，從右到左，從上到下依次調整 for (int i = len / 2 - 1; i >= 0; i--) { adjustNode(arr, i, len); } // ② 將大頂堆轉換成有序數組過程 for (int i = len - 1; i > 0 ; i--) { swap(arr, 0, i); adjustNode(arr, 0, i); }}/** * arr: 數組 * base: 待調整的基準 * len: 數組長度 */public void adjustNode(int[] arr, int base, int len) { int originNum = arr[base]; // 從每一個結點的左下子節點開始，如有調整，則挪動元素並以被挪動的 // 子節點為基點，再重複以上過程。 for (int i = basse * 2 + 1; i < len; i = i * 2 + 1) { if (i + 1 < len && arr[i + 1] > arr[i]) { // 如果右邊的子節點大，則指向右邊節點 i++; } if (arr[i] > arr[base]) { // 將大的那個子節點往上挪動，並將基準置為當前子節點 arr[base] = arr[i]; base = i; } else { // 已經是大頂堆了 break; } }}public void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}

冒泡排序

原理

冒泡排序的過程正如它的名字，像水裡的氣泡一樣往上冒。

它能夠保證每一趟都能把最小的元素移動到最前面去，具體過程是通過從後往前元素間兩兩比較，小的挪動到前面，依次類推向前操作。

再對之後 n - 1 個元素進行同樣的操作，直到全部有序為止。

示意圖：

演算法實現

public void bubbleSort(int[] arr) { int len = arr.length; if (len == null || len == 0) return; int swapCount; // 記錄每一趟的交換次數 for (int i = 0; i < len - 1; i++) { // 只需要進行 n - 1 趟即可 if (swapCount == 0 && i != 0) { // 如果發現某一趟沒有交換任何元素，證明已經有序 break; } swapCount = 0; // 每進行完一趟，前i個元素已經有序 for (int j = len - 1; j > i; j--) { if (arr[j] < arr[j - 1]) { swap(arr, j, j - 1); swapCount++; } } }}public void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}

分析

由於該演算法的每一趟是從後往前依次比較交換的，如果在第一趟完成後，發現元素已經有序，則之後不需要再做後幾趟的交換排序了，因此這種情況只需要比較 n - 1次，最好的時間複雜度為O(n)；而最差情況下是做完每一趟的排序，因此總次數為 (n - 1) + (n - 2) + … + 1 = n * (n - 1) / 2，因此最壞時間複雜度為O(n2)。

快速排序

(未完待續...拚命更新中...)