引言

在一些場(chǎng)景中，我們需要對(duì)數(shù)據(jù)進(jìn)行排序，就如之前提到的冒泡排序，這篇文章將講述一些主流的排序算法。

1. 插入排序

1.1 基本思想

插入排序的基本思想是將數(shù)組分為已排序和未排序兩部分，逐步將未排序部分的元素插入到已排序部分的適當(dāng)位置，直到整個(gè)數(shù)組有序。

1.2 直接插入排序

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

1. 從數(shù)組的第二個(gè)元素開始（索引為1），認(rèn)為第一個(gè)元素是已排序的。 取出當(dāng)前元素 tmp，并將其與已排序部分的元素從后向前比較。
2. 如果已排序部分的元素大于 tmp，則將該元素向后移動(dòng)一位。
3. 重復(fù)上述步驟，直到找到一個(gè)不大于 tmp 的元素位置。
4. 將 tmp 插入到該位置。
5. 重復(fù)步驟2-5，直到所有元素都插入到已排序部分。

時(shí)間復(fù)雜度：O(n²)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定

1.3 希爾排序

希爾排序的基本思想是通過將數(shù)組分成若干子序列分別進(jìn)行插入排序，從而加快排序速度。它是對(duì)直接插入排序的一種改進(jìn)。

// 希爾排序
public static void shellSort(int[] array) {int gap = array.length / 2;while (gap > 0) {shell(array, gap);gap /= 2;}
}public static void shell(int[] array, int gap) {for (int i = gap; i < array.length; 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;}
}

1. shellSort 方法初始化間隔 gap 為數(shù)組長(zhǎng)度的一半。
2. 在 gap 大于0的情況下，調(diào)用 shell 方法對(duì)數(shù)組進(jìn)行分組排序，然后將 gap 減半。
3. shell 方法對(duì)每個(gè)間隔為 gap 的子序列進(jìn)行插入排序。
4. 在 shell 方法中，從索引 gap 開始，取出當(dāng)前元素 tmp，并將其與間隔為 gap 的已排序部分的元素從后向前比較。
5. 如果已排序部分的元素大于 tmp，則將該元素向后移動(dòng) gap 位。
6. 重復(fù)上述步驟，直到找到一個(gè)不大于 tmp 的元素位置。
7. 將 tmp 插入到該位置。
8. 重復(fù)步驟4-7，直到所有子序列都排序完成。

希爾排序由于gap值不確定，時(shí)間復(fù)雜度并沒有確切的值，但是時(shí)間復(fù)雜度是比直接插入排序要低的。
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定

2. 選擇排序

2.1 基本思想

每?次從待排序的數(shù)據(jù)元素中選出最?（或最?）的?個(gè)元素，存放在序列的起始位置，直到全部待
排序的數(shù)據(jù)元素排完。

2.2 直接選擇排序

// 選擇排序
public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}if (minIndex != i) {swap(array, i, minIndex);}}
}// 輔助方法：交換數(shù)組中的兩個(gè)元素
private static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;
}

1. 從數(shù)組的第一個(gè)元素開始，認(rèn)為第一個(gè)元素是已排序的。
2. 在未排序部分中找到最小的元素，并記錄其索引 minIndex。
3. 將最小元素與當(dāng)前元素交換位置（如果 minIndex 不等于當(dāng)前索引 i）。
4. 重復(fù)步驟2-3，直到所有元素都排序完成。

時(shí)間復(fù)雜度：O(n²)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定

2.3 直接選擇排序變種

直接選擇排序的變種在每一趟排序中同時(shí)找到未排序部分的最小值和最大值，并分別將它們放到未排序部分的兩端。

public static void selectSort2(int[] array) {int left = 0;int right = array.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;for (int i = left + 1; i <= right; i++) {if (array[i] < array[minIndex]) {minIndex = i;}if (array[i] > array[maxIndex]) {maxIndex = i;}}if (minIndex != left) {swap(array, minIndex, left);}if (maxIndex == left) {maxIndex = minIndex;}if (maxIndex != right) {swap(array, maxIndex, right);}left++;right--;}
}// 輔助方法：交換數(shù)組中的兩個(gè)元素
private static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;
}

1. 初始化兩個(gè)指針 left 和 right，分別指向數(shù)組的兩端。
2. 在未排序部分中找到最小值和最大值的索引 minIndex 和 maxIndex。
3. 將最小值與 left 位置的元素交換。
4. 如果最大值的索引是 left，則更新 maxIndex 為 minIndex，因?yàn)樽钚≈狄呀?jīng)被交換到 left 位置。
5. 將最大值與 right 位置的元素交換。
6. 移動(dòng) left 和 right 指針，縮小未排序部分的范圍。
7. 重復(fù)步驟2-6，直到 left 和 right 相遇。

2.4 堆排序

堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法，利用堆的性質(zhì)來排序數(shù)組。

// 堆排序
public static void heapSort(int[] array) {createHeap(array);int end = array.length - 1;while (end > 0) {swap(array, 0, end);siftDown(array, 0, end);end--;}
}// 創(chuàng)建最大堆
public static void createHeap(int[] array) {for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {siftDown(array, p, array.length);}
}// 向下調(diào)整堆
private static void siftDown(int[] array, int p, int length) {int c = 2 * p + 1;while (c < length) {if (c + 1 < length && array[c] < array[c + 1]) {c++;}if (array[c] > array[p]) {swap(array, c, p);p = c;c = 2 * p + 1;} else {break;}}
}// 輔助方法：交換數(shù)組中的兩個(gè)元素
private static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;
}

1. 創(chuàng)建最大堆：調(diào)用 createHeap 方法，將數(shù)組轉(zhuǎn)換為最大堆。

    從最后一個(gè)非葉子節(jié)點(diǎn)開始，向上逐個(gè)節(jié)點(diǎn)進(jìn)行向下調(diào)整（siftDown），確保每個(gè)子樹都是最大堆。
   

2. 排序過程：

    將堆頂元素（最大值）與當(dāng)前未排序部分的最后一個(gè)元素交換。調(diào)整堆頂元素，使剩余部分重新成為最大堆（siftDown）?？s小未排序部分的范圍，重復(fù)上述步驟，直到整個(gè)數(shù)組有序。
   

時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定

3. 交換排序

3.1 基本思想

交換排序的基本思想是通過比較和交換數(shù)組中的元素，使數(shù)組逐步有序。

3.2 冒泡排序

冒泡排序通過重復(fù)地遍歷數(shù)組，每次比較相鄰的兩個(gè)元素，如果它們的順序錯(cuò)誤就交換它們的位置。這樣，每一趟遍歷都會(huì)將當(dāng)前未排序部分的最大元素“冒泡”到數(shù)組的末尾。重復(fù)這個(gè)過程，直到整個(gè)數(shù)組有序。

    //冒泡排序public static void bubbleSort(int[] array) {for (int i = 0; i < array.length; i++) {boolean flg = true;for (int j = 0; j < array.length - i - 1; j++) {if (array[j] > array[j + 1]) {swap(array, j, j + 1);flg = false;}}if (flg) {break;}}}

1. 外層循環(huán)：遍歷數(shù)組的每一個(gè)元素，控制排序的趟數(shù)。
2. 內(nèi)層循環(huán)：從數(shù)組的第一個(gè)元素開始，比較相鄰的兩個(gè)元素，如果前一個(gè)元素大于后一個(gè)元素，就交換它們的位置。
3. 標(biāo)志變量 flg：用于檢測(cè)當(dāng)前趟排序是否發(fā)生了交換。如果在某一趟排序中沒有發(fā)生交換，說明數(shù)組已經(jīng)有序，可以提前結(jié)束排序。
4. 交換函數(shù) swap：用于交換數(shù)組中的兩個(gè)元素。

時(shí)間復(fù)雜度：O(n²)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定

3.3 快速排序

快速排序的基本思想是通過選擇一個(gè)樞軸元素，將數(shù)組分成兩部分，使得左側(cè)部分的所有元素都小于樞軸，右側(cè)部分的所有元素都大于樞軸。然后遞歸地對(duì)左右兩部分進(jìn)行快速排序，直到整個(gè)數(shù)組有序?？焖倥判蛴卸喾N排序方法，先介紹基本結(jié)構(gòu)。

3.3.1 快速排序的基本結(jié)構(gòu)

public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}public static void quick(int[] array, int left, int right) {if (left >= right) {return;}int index = partition(array, left, right);quick(array, left, index - 1);quick(array, index + 1, right);}

1. 快速排序入口方法 (quickSort)：

    這是快速排序的入口方法，接收一個(gè)數(shù)組 array 作為參數(shù)。調(diào)用 quick 方法，對(duì)整個(gè)數(shù)組進(jìn)行排序，初始的左右邊界分別是 0 和 array.length - 1。
   

2. 遞歸排序方法 (quick)：

   這是快速排序的遞歸方法，用于對(duì)數(shù)組的某個(gè)子區(qū)間進(jìn)行排序。
   參數(shù) left 和 right 分別表示當(dāng)前子區(qū)間的左邊界和右邊界。
   基本條件：如果 left 大于或等于 right，說明當(dāng)前子區(qū)間已經(jīng)有序或只有一個(gè)元素，直接返回。
   調(diào)用 partition 方法，將數(shù)組分成兩部分，并返回樞軸元素的位置 index。
   遞歸地對(duì)左側(cè)部分（left 到 index - 1）進(jìn)行排序。
   遞歸地對(duì)右側(cè)部分（index + 1 到 right）進(jìn)行排序。
   

下面介紹partition的各種實(shí)現(xiàn)方法：

3.3.2 Hoare法

Hoare法的partition（分區(qū)）算法是快速排序中的一種分區(qū)方法。它通過選擇一個(gè)樞軸元素，將數(shù)組分成兩部分，使得左側(cè)部分的所有元素都小于等于樞軸，右側(cè)部分的所有元素都大于等于樞軸。

    private static int partition1(int[] array, int left, int right) {int i = left;int j = right;int pivot = array[left];while (i < j) {while (i < j && array[j] >= pivot) {j--;}while (i < j && array[i] <= pivot) {i++;}swap(array, i, j);}swap(array, i, left);return i;}

1. 選擇樞軸：

    選擇最左邊的元素作為樞軸（pivot）。
   

2. 初始化指針：

    初始化兩個(gè)指針 i 和 j，分別指向數(shù)組的左邊界和右邊界。
   

3. 分區(qū)過程：

    使用兩個(gè) while 循環(huán)，分別從右向左和從左向右掃描數(shù)組：從右向左找到第一個(gè)小于樞軸的元素，更新指針 j。從左向右找到第一個(gè)大于樞軸的元素，更新指針 i。如果 i 小于 j，交換 i 和 j 指向的元素。重復(fù)上述過程，直到 i 和 j 相遇或交錯(cuò)。
   

4. 交換樞軸：

    將樞軸元素放到正確的位置，即 i 位置。返回 i 作為分區(qū)點(diǎn)。
   

3.3.3 挖坑法

    public static int partition(int[] array, int left, int right) {int base = array[left];int i = left;int j = right;while (i < j) {while (i < j && array[j] >= base) {j--;}array[i] = array[j];while (i < j && array[i] <= base) {i++;}array[j] = array[i];}array[i] = base;return i;}

1. 選擇樞軸：

    選擇最左邊的元素作為樞軸（base）。
   

2. 初始化指針：

    初始化兩個(gè)指針 i 和 j，分別指向數(shù)組的左邊界和右邊界。
   

3. 分區(qū)過程：

    使用兩個(gè) while 循環(huán)，分別從右向左和從左向右掃描數(shù)組：從右向左找到第一個(gè)小于樞軸的元素，更新指針 j，并將該元素放到 i 位置。從左向右找到第一個(gè)大于樞軸的元素，更新指針 i，并將該元素放到 j 位置。重復(fù)上述過程，直到 i 和 j 相遇或交錯(cuò)。
   

4. 交換樞軸：

    將樞軸元素放到正確的位置，即 i 位置。返回 i 作為分區(qū)點(diǎn)。
   

3.3.4 雙指針法

  private static int partition(int[] array, int left, int right) {int prev = left;int cur = left + 1;while (cur <= right) {if (array[cur] < array[left] && array[++prev] != array[cur]) {swap(array, cur, prev);}cur++;}swap(array, prev, left);return prev;}

1. 選擇樞軸：

    選擇最左邊的元素作為樞軸（array[left]）。
   

2. 初始化指針：

    初始化兩個(gè)指針 prev 和 cur，分別指向數(shù)組的左邊界和樞軸的下一個(gè)位置。
   

3. 分區(qū)過程：

    使用 while 循環(huán)，從 cur 指針開始遍歷數(shù)組，直到 cur 超過右邊界 right。如果 cur 指針指向的元素小于樞軸元素，并且 prev 指針和 cur 指針指向的元素不同，則交換 cur 和 prev 指針指向的元素。每次交換后，prev 指針向右移動(dòng)一位。cur 指針每次循環(huán)后向右移動(dòng)一位。
   

4. 交換樞軸：

    將樞軸元素放到正確的位置，即 prev 位置。返回 prev 作為分區(qū)點(diǎn)。
   

3.4 快速排序非遞歸法

非遞歸快速排序通過使用棧來模擬遞歸調(diào)用，從而避免了遞歸帶來的棧溢出問題。

    public static void quickSortNonR(int[] a, int left, int right) {Stack<Integer> st = new Stack<>();st.push(left);st.push(right);while (!st.empty()) {right = st.pop();left = st.pop();if (right - left <= 1) {continue;}int div = partition(a, left, right);st.push(div + 1);st.push(right);st.push(left);st.push(div);}}

1. 初始化棧：

    創(chuàng)建一個(gè)棧 st，用于存儲(chǔ)數(shù)組的左右邊界。將初始的左右邊界 left 和 right 壓入棧中。
   

2. 循環(huán)處理：

    當(dāng)棧不為空時(shí)，循環(huán)執(zhí)行以下步驟：從棧中彈出 right 和 left，表示當(dāng)前需要處理的子數(shù)組的左右邊界。如果子數(shù)組的長(zhǎng)度小于等于1（即 right - left <= 1），則跳過當(dāng)前循環(huán)，繼續(xù)處理下一個(gè)子數(shù)組。調(diào)用 partition 方法對(duì)當(dāng)前子數(shù)組進(jìn)行分區(qū)，返回樞軸位置 div。將右側(cè)子數(shù)組的左右邊界（div + 1 和 right）壓入棧中。將左側(cè)子數(shù)組的左右邊界（left 和 div）壓入棧中。
   

3. 分區(qū)方法：

    partition 方法用于將數(shù)組分成兩部分，使得左側(cè)部分的所有元素都小于等于樞軸，右側(cè)部分的所有元素都大于等于樞軸。
   

3.5 快速排序分析

時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(logn)
穩(wěn)定性：不穩(wěn)定

4. 歸并排序

歸并排序是一種基于分治法的排序算法。它將數(shù)組分成兩個(gè)子數(shù)組，分別對(duì)這兩個(gè)子數(shù)組進(jìn)行排序，然后將排序后的子數(shù)組合并成一個(gè)有序的數(shù)組。

4.1 基本思想

1. 分解：將數(shù)組分成兩個(gè)子數(shù)組，分別對(duì)這兩個(gè)子數(shù)組進(jìn)行排序。
2. 遞歸排序：遞歸地對(duì)每個(gè)子數(shù)組進(jìn)行歸并排序。
3. 合并：將兩個(gè)有序的子數(shù)組合并成一個(gè)有序的數(shù)組。

4.1 歸并排序遞歸

// 歸并排序
public static void mergeSort(int[] array) {mergeSortChild(array, 0, array.length - 1);
}// 遞歸排序子數(shù)組
public static void mergeSortChild(int[] array, int left, int right) {if (left >= right) {return;}int mid = (left + right) / 2;mergeSortChild(array, left, mid);mergeSortChild(array, mid + 1, right);merge(array, left, mid, right);
}// 合并兩個(gè)有序子數(shù)組
public static void merge(int[] array, int left, int mid, int right) {int s1 = left;int s2 = mid + 1;int[] tmp = new int[right - left + 1];int i = 0;while (s1 <= mid && s2 <= right) {if (array[s1] <= array[s2]) {tmp[i++] = array[s1++];} else {tmp[i++] = array[s2++];}}while (s1 <= mid) {tmp[i++] = array[s1++];}while (s2 <= right) {tmp[i++] = array[s2++];}for (int j = 0; j < tmp.length; j++) {array[left + j] = tmp[j];}
}

1. 歸并排序入口方法 (mergeSort)：

    這是歸并排序的入口方法，接收一個(gè)數(shù)組 array 作為參數(shù)。調(diào)用 mergeSortChild 方法，對(duì)整個(gè)數(shù)組進(jìn)行排序，初始的左右邊界分別是 0 和 array.length - 1。
   

2. 遞歸排序子數(shù)組 (mergeSortChild)：

    這是歸并排序的遞歸方法，用于對(duì)數(shù)組的某個(gè)子區(qū)間進(jìn)行排序。參數(shù) left 和 right 分別表示當(dāng)前子區(qū)間的左邊界和右邊界?；緱l件：如果 left 大于或等于 right，說明當(dāng)前子區(qū)間已經(jīng)有序或只有一個(gè)元素，直接返回。計(jì)算中間位置 mid，將數(shù)組分成兩部分。遞歸地對(duì)左側(cè)部分（left 到 mid）進(jìn)行排序。遞歸地對(duì)右側(cè)部分（mid + 1 到 right）進(jìn)行排序。調(diào)用 merge 方法，將兩個(gè)有序的子數(shù)組合并成一個(gè)有序的數(shù)組。
   

3. 合并兩個(gè)有序子數(shù)組 (merge)：

    參數(shù) left、mid 和 right 分別表示當(dāng)前子區(qū)間的左邊界、中間位置和右邊界。初始化兩個(gè)指針 s1 和 s2，分別指向兩個(gè)子數(shù)組的起始位置。創(chuàng)建一個(gè)臨時(shí)數(shù)組 tmp，用于存儲(chǔ)合并后的有序數(shù)組。使用 while 循環(huán)，將兩個(gè)子數(shù)組中的元素按順序合并到臨時(shí)數(shù)組 tmp 中。將剩余的元素（如果有）復(fù)制到臨時(shí)數(shù)組 tmp 中。將臨時(shí)數(shù)組 tmp 中的元素復(fù)制回原數(shù)組 array 中。
   

時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(n)
穩(wěn)定性：穩(wěn)定

4.2 歸并排序非遞。

非遞歸歸并排序（也稱為迭代歸并排序）通過逐步增加子數(shù)組的大小來實(shí)現(xiàn)排序。

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

1. 初始化間隔 (gap)：

    初始化間隔 gap 為1，表示初始的子數(shù)組大小為1。
   

2. 外層循環(huán)：

    當(dāng) gap 小于數(shù)組長(zhǎng)度時(shí)，繼續(xù)循環(huán)。每次循環(huán)將 gap 翻倍，表示子數(shù)組的大小逐步增加。
   

3. 內(nèi)層循環(huán)：

    遍歷數(shù)組，將數(shù)組分成若干個(gè)大小為 2 * gap 的子數(shù)組。計(jì)算每個(gè)子數(shù)組的左邊界 left、中間位置 mid 和右邊界 right。調(diào)用 merge 方法，將兩個(gè)有序的子數(shù)組合并成一個(gè)有序的數(shù)組。
   

5. 不基于比較的排序

不基于比較的排序算法主要包括計(jì)數(shù)排序、基數(shù)排序和桶排序。這些算法不通過比較元素來排序，而是利用元素的值來確定其位置，從而實(shí)現(xiàn)線性時(shí)間復(fù)雜度的排序。這里就介紹計(jì)數(shù)排序。

5.1 計(jì)數(shù)排序

計(jì)數(shù)排序適用于元素值范圍較小的情況。它通過統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，然后根據(jù)這些計(jì)數(shù)來確定每個(gè)元素的位置。

public static void countingSort(int[] array) {int max = array[0];int min = array[0];// 找到數(shù)組中的最大值和最小值for (int i = 1; i < array.length; i++) {if (array[i] > max) {max = array[i];}if (array[i] < min) {min = array[i];}}// 創(chuàng)建計(jì)數(shù)數(shù)組int len = max - min + 1;int[] countArray = new int[len];// 統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)for (int i = 0; i < array.length; i++) {int index = array[i] - min;countArray[index]++;}// 根據(jù)計(jì)數(shù)數(shù)組重新填充原數(shù)組int k = 0;for (int i = 0; i < countArray.length; i++) {while (countArray[i] > 0) {array[k++] = i + min;countArray[i]--;}}
}

1. 找到最大值和最小值：

    遍歷數(shù)組，找到數(shù)組中的最大值 max 和最小值 min。
   

2. 創(chuàng)建計(jì)數(shù)數(shù)組：

    根據(jù)最大值和最小值計(jì)算計(jì)數(shù)數(shù)組的長(zhǎng)度 len，即 max - min + 1。創(chuàng)建一個(gè)長(zhǎng)度為 len 的計(jì)數(shù)數(shù)組 countArray，用于統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)。
   

3. 統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)：

    遍歷原數(shù)組，對(duì)于每個(gè)元素 array[i]，計(jì)算其在計(jì)數(shù)數(shù)組中的索引 index，即 array[i] - min。將計(jì)數(shù)數(shù)組中對(duì)應(yīng)位置的值加1，表示該元素出現(xiàn)了一次。
   

4. 根據(jù)計(jì)數(shù)數(shù)組重新填充原數(shù)組：

    遍歷計(jì)數(shù)數(shù)組，對(duì)于每個(gè)非零的計(jì)數(shù)值，將對(duì)應(yīng)的元素填充回原數(shù)組。使用一個(gè)指針 k 來記錄當(dāng)前填充的位置。對(duì)于計(jì)數(shù)值 countArray[i]，將元素 i + min 填充回原數(shù)組 countArray[i] 次。
   

6. 總結(jié)

以上就是一些常用的排序算法的介紹和代碼實(shí)現(xiàn)，具體如何排序，可以看這里的鏈接： 十大經(jīng)典排序算法動(dòng)畫與解析。