目錄

1. 插入排序

2. 希爾排序

3. 選擇排序

4. 堆排序

5. 冒泡排序

6. 快速排序

1. 快速排序的實現

1. 思路（以從小到大排序為例）

2. 選取基準元素的方法（Hoare）

3. 選取基準元素的方法（挖坑法）

2. 快速排序的優化

3. 快速排序的非遞歸實現

7. 歸并排序

1. 歸并排序的實現

2. 歸并排序的非遞歸實現

3. 海量數據的排序問題

8. 計數排序

---

1. 插入排序

時間復雜度：O(n^2)

空間復雜度：O(1)

穩定性：穩定

特點：數據越有序，排序越快

思路（以從小到大排序為例）：

指針 i 標記新拿到的數據，指針 j 標記已有的排好序的數據，初始情況為 i = 1，?j = i - 1；

i 向后遍歷，如果拿到的數據比 j 指向的數據大，直接將 i 指向的數據放在 j + 1 的位置；

注意：第一次挪 j 位置的數據會覆蓋掉原來 i 位置的數據，因此需要定義一個變量，提前保存好 i 位置的數據；

如果 i 指向的數據小于等于 j 指向的數據，將 j 指向的數據放在 j + 1 位置即可；

如果 i 指向的數據比所有的 j 維護的數據都小，那么 j 會減小至負數，將 i 位置數據放到 0 位置即可；

    public static void insertSort(int[] array){int n = array.length;for(int i = 1; i < n; i++){int j = i - 1;int tmp = array[i];for( ; j >= 0; j--){if(tmp < array[j]){array[j + 1] = array[j];}else{break;}}array[j + 1] = tmp;}}

2. 希爾排序

時間復雜度：O(n^1.3 ~ n^1.5)

空間復雜度：O(1)

穩定性：不穩定

思路（以從小到大排序為例）：

先將數據分成若干組，每組元素間隔距離為?gap，每組元素以插入排序的方式進行排序；

排序完成后，每組元素間隔距離為 gap / 2，再以插入排序的方式進行排序，直至 gap = 1，整體完成排序；

    public static void shellSort(int[] array){int gap = array.length;while(gap > 0){gap /= 2;shell(array, gap);}}private static void shell(int[] array, int gap){int n = array.length;for(int i = gap; i < n; i++){int tmp = array[i];int j = i - gap;for(; j >= 0; j -= gap){if(array[j] > tmp){array[j + gap] = array[j];}else{break;}}array[j + gap] = tmp;}}

3. 選擇排序

時間復雜度：O(n^2)

空間復雜度：O(1)

穩定性：不穩定

思路（以從小到大排序為例）：

定義 i 指針遍歷數組，定義 j = i + 1，找最小值，找到最小值后，將下標 j 存在 minIndex 里面；

交換 i 位置和 minIndex 位置元素，直到 i 遍歷數組完成；

    public static void selectSort(int[] array){int n = array.length;for(int i = 0; i < n; i++){int minIndex = i;for(int j = i + 1; j < n; j++){if(array[j] < array[minIndex]){minIndex = j;}}swap(array, i, minIndex);}}private static void swap(int[] array, int i, int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}

4. 堆排序

時間復雜度：O(n* logn)

空間復雜度：O(1)

穩定性：不穩定

思路（以從小到大排序為例）：

建立一個大根堆，從后往前遍歷每一棵子樹，如果根節點值小于左右孩子節點的最大值，根節點值和最大值交換，重新指向交換過的孩子節點并向下調整；

交換堆頂元素和最后一個元素，并將堆頂元素向下調整；

    private static void swap(int[] array, int i, int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}public static void heapSort(int[] array){// 建一個大根堆int n = array.length;int parent = (n - 1 - 1) / 2;for( ; parent >= 0; parent--){shiftDown(array, parent, n);}// 排序int end = n - 1;while(end > 0){swap(array, 0, end);shiftDown(array, 0, end--);}}private static void shiftDown(int[] array, int parent, int size){int child = parent * 2 + 1;while(child < size){if(child + 1 < size && array[child] < array[child + 1]){child++;}if(array[child] > array[parent]){swap(array, child, parent);parent = child;child = parent * 2 + 1;}else{break;}}}

5. 冒泡排序

時間復雜度：O(n*2)

空間復雜度：O(1)

穩定性：穩定

思路（以從小到大排序為例）：

定義指針 i 標記排序的趟數，如果數組長度為 n，排 n - 1 趟即可；

定義指針 j 標記要比較的元素，和 j + 1 位置的元素做比較，如果 array[j] > array[j + 1]，交換 j 位置和 j + 1 位置的元素；

優化：如果一趟排序下來沒有發生交換，表示已經有序了，跳出循環即可；

    public static void bubbleSort(int[] array){int n = array.length;for(int i = 0; i < n - 1; i++){boolean flag = false;for(int j = 0; j < n - 1 - i; j++){if(array[j] > array[j + 1]){swap(array, j, j + 1);flag = true;}}if(!flag) break;}}private static void swap(int[] array, int i, int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}

6. 快速排序

時間復雜度：

快排算法的時間復雜度取決于分割數組的方式（基準元素的選取），因此分割方式不同，時間復雜度不同；

如果基準元素每次都正好選取了要排序部分的中位數，那么時間復雜度應為 O(n*logn)；

如果基準元素每次都正好選取了要排序部分的最小值或者最大值，那么時間復雜度應為 O(n^2)；

空間復雜度：O(logn)

穩定性：不穩定

1. 快速排序的實現

1. 思路（以從小到大排序為例）

采用數組分塊的思想，選取一個基準元素，將數組分成兩塊，此時基準元素已經有序了，分別處理基準元素左右兩遍的區間；

左邊部分再選取基準元素，在 [left, pivot - 1] 中遞歸；

右邊部分再選取基準元素，在 [pivot + 1, right] 中遞歸；

2. 選取基準元素的方法（Hoare）

left 指向待排序的區間的左端點，right 指向待排序的區間的右端點；

選取左端點指向的元素為基準元素；

如果 right 指針指向的元素大于等于基準元素，就向左移動；

如果 left 指針指向的元素小于等于基準元素，就向右移動；

此時 right 指向的是比基準元素小的值，left 指向的是比基準元素大的值，交換 left 和 right 指向的元素；

直到 left 指針和 right 指針相遇，此時指向的位置，左邊的元素都小于等于基準元素，右邊的元素都大于等于基準元素；

    public static void quickSort(int[] array){int n = array.length;quick(array, 0, n - 1);}public static void quick(int[] array, int left, int right){if(left >= right) return;int pivot = partition(array, left, right);quick(array, left, pivot - 1);quick(array, pivot + 1, right);}private static int partition(int[] array, int left, int right){int tmp = array[left];int pos = left;while(left < right){while(left < right && array[right] >= tmp) right--;while(left < right && array[left] <= tmp) left++;swap(array, left, right);}swap(array, pos, left);return left;}private static void swap(int[] array, int i, int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}

要點 1：為什么選取基準元素，移動 left 和 right 指針的時候要取等號？

防止 left 和 right 指針指向的元素都恰好等于基準元素的值，都等于會陷入死循環；

要點 2：為什么要先移動 right 指針，而不是先移動 left 指針？

如果先移動 left，當 left 和 right 指針相遇的時候，指向的元素的值會大于基準元素，如果交換基準元素和該元素，就會把比基準元素大的值交換到左邊去，不符合排序的思想；

3. 選取基準元素的方法（挖坑法）

left 指向待排序的區間的左端點，right 指向待排序的區間的右端點；

選取左端點指向的元素為基準元素；

如果 right 指針指向的元素大于等于基準元素，就向左移動；

此時 right 指向的是比基準元素小的值，把 right 指向的元素放到?left 指向的位置；

如果 left 指針指向的元素小于等于基準元素，就向右移動；

此時 left 指向的是比基準元素大的值，把 left 指向的元素放到 right 指向的位置；

直到 left 指針和 right 指針相遇，把基準元素放到此時指向的位置，左邊的元素都小于等于基準元素，右邊的元素都大于等于基準元素，此時基準元素已經有序了；

    private static int partition2(int[] array, int left, int right){int tmp = array[left];while(left < right) {while(left < right && array[right] >= tmp) right--;array[left] = array[right];while(left < right && array[left] <= tmp) left++;array[right] = array[left];}array[left] = tmp;return left;}

2. 快速排序的優化

使用快排為了避免出現選取基準元素選取到區間中的最大值或者最小值的情況，因此可以結合三數取中法進行優化；

思路：

定義 left 指向區間的左端點，right 指向區間的右端點，mid 指向區間的中點；

找出 left，right，mid 指向的元素中第二大的元素，返回下標；

    private static int midOfThree(int[] array, int left, int right){int mid = (left + right) / 2;if(array[left] < array[right]){if(array[mid] < array[left]) return left;else if(array[mid] > array[right]) return right;else return mid;}else {if(array[mid] < array[right]) return right;else if(array[mid] > array[left]) return left;else return mid;}}

結合三數取中法優化：

記錄三數取中法返回的下標 index，index 指向的元素和 left 指向的元素進行交換，保證數組分塊時，每次選取 left 指向的元素都不是區間內的最大值和最小值，使分塊形成的二叉樹盡可能接近完全二叉樹；

    public static void quick(int[] array, int left, int right){if(left >= right) return;int index = midOfThree(array, left, right);swap(array, index, left);int pivot = partition(array, left, right);quick(array, left, pivot - 1);quick(array, pivot + 1, right);}

3. 快速排序的非遞歸實現

快速排序可以借助遞歸實現，遞的過程就是調用方法在棧上開辟棧幀的過程，歸的過程就是方法返回銷毀棧幀的過程，因此遞歸通常可以借助棧來轉化為非遞歸。

思路：

遞歸是找基準元素將數組分塊，再分別處理左邊區間和右邊區間；

因此可以將區間的左右端點加入到棧中，每次彈出一組端點，分別為區間的右端點和左端點；

調用數組分塊的方法，將這段區間分為兩塊，再重新將兩塊區間的端點加入到棧中；

直至彈出棧中所有的數對，排序就完成了；

    // 快排的非遞歸版本public static void quickSortNor(int[] array){int n = array.length;Stack<Integer> stack = new Stack<>();stack.push(0);stack.push(n - 1);while(!stack.isEmpty()){int right = stack.pop();int left = stack.pop();int pivot = partition2(array, left, right);if(left + 1 < pivot){stack.push(left);stack.push(pivot - 1);}if(pivot + 1 < right){stack.push(pivot + 1);stack.push(right);}}}

7. 歸并排序

時間復雜度：O(n*logn)

空間復雜度：O(n)

穩定性：穩定

1. 歸并排序的實現

思路：

給定一段待排序的區間，left 指向區間左端點，right 指向區間右端點，mid 指向區間左中點；

先對左邊區間進行排序 [left, mid]，再對右邊區間進行排序 [mid + 1, right]；

合并兩個有序區間；

    public static void mergeSort(int[] array){mergeSortFunc(array, 0, array.length - 1);}private static void mergeSortFunc(int[] array, int left, int right) {if(left >= right) return;int mid = (right + left) / 2;mergeSortFunc(array, left, mid);mergeSortFunc(array, mid + 1, right);merge(array, left, mid, right);}private static void merge(int[] array, int left, int mid, int right){int i = left;int j = mid + 1;int k = 0;int[] tmp = new int[right - left + 1];while(i <= mid && j <= right){if(array[i] <= array[j]){tmp[k++] = array[i++];}else{tmp[k++] = array[j++];}}while(i <= mid) tmp[k++] = array[i++];while(j <= right) tmp[k++] = array[j++];for(int l = left; l <= right; l++){array[l] = tmp[l - left];}}

2. 歸并排序的非遞歸實現

思路：

定義變量 gap 表示每次排序的子區間的長度，從左向右對子區間進行排序；

left 用于表示子區間的左端點，mid 表示子區間的右端點，mid + 1 表示下一個子區間的左端點，right 表示下一個子區間的右端點，分別計算 left，mid，right 的值；

調用 merge() 方法合并兩個有序區間；

gap 增大為原來的 2 倍，繼續重復上述步驟，直到 gap 增大到大于等于整個數組的長度；

    public static void mergeSortNor(int[] array){int n = array.length;int gap = 1;while(gap < n){for(int i = 0; i < n; i += 2 * gap){int left = i;int mid = i + gap - 1;int right = mid + gap;if(mid >= n) mid = n - 1;if(right >= n) right = n - 1;merge(array, left, mid, right);}gap *= 2;}}

3. 海量數據的排序問題

外部排序：排序過程需要在磁盤外部進行的排序；

前提：內存只有 1G，需要排序 100G 的數據；

因為內存只有 1G，無法將所有數據全部放下，所以需要外部排序，而歸并排序是最常用的外部排序；

實現步驟：

1. 先把數據分割成 200 份，每份 512M；

2. 對每一份 512M 的數據進行排序，因為內存可以放得下，因此選用哪種排序方式均可；

3. 進行 2 路歸并，同時讀取兩個文件中的數據，每次讀 1 個數據，進行比較排序，并寫入到一個新文件中；

4. 得到新文件再按照上述方式進行 2 路歸并，最終形成一個新的數據有序的文件；

8. 計數排序

時間復雜度：O(N+數據范圍)

空間復雜度：O(數據范圍)

穩定性：穩定

思路（下面代碼是不穩定的排序）：

遍歷一遍數組，找出最小值 minVal 和最大值 maxVal；

建立一個計數數組 count，大小為 maxVal - minVal + 1；

遍歷一遍數組，統計每個數字出現的次數，minVal 放到下標為 0 的位置，依次類推；

遍歷一遍 count 數組，如果 count[i] 不等于 0，依次將數字放到原數組中；

    public static void countSort(int[] array){int n = array.length;int minVal = array[0];int maxVal = array[0];for(int x : array){if(minVal > x) minVal = x;if(maxVal < x) maxVal = x;}int[] count = new int[maxVal - minVal + 1];for(int x : array){count[x - minVal]++;}int pos = 0;for(int i = 0; i < count.length; i++){while(count[i]-- > 0){array[pos++] = i + minVal;}}}