前言

這篇文章是基于個人學習體會整理而來，主要介紹七種常見的基于比較的排序算法基本原理及實現、排序算法的性能分析、 java 中的常用排序方法。如果內容有不足之處，非常歡迎大家一起指正和交流！

1. 排序的基本概念

1.1 排序是什么？

排序算法，可以說是《數據結構與算法》這門課里最基礎、也最重要的一環。常見的排序算法有很多，比如插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、堆排序等等。

在開始之前，我們先明確幾個基本概念：

內部排序 vs 外部排序：

• 內部排序：可以想象成所有需要排序的數據都能一股腦兒地放進電腦內存里進行處理。
• 外部排序：當數據量非常大，內存一次性裝不下時，就需要借助硬盤等外部存儲，在內存和外存之間來回倒騰數據來完成排序。

排序 (Sort)：

• 簡單來說，排序就是讓一串數據記錄，根據其中我們關心的某個關鍵信息（比如數字的大小、字母的順序），按照從小到大（遞增）或從大到小（遞減）的規則重新排列。

穩定性 (Stability)：

• 這是一個衡量排序算法性質的重要指標。設想一下，如果我們要排序的數據里有好幾個值是相同的。經過排序后，如果這些相同值的記錄，它們之間的相對位置和排序前保持一致，那這種排序算法就是穩定的。反之，如果它們的相對順序被打亂了，那就是不穩定的。
• 舉個例子，假設原序列中有兩個記錄 r[i] 和 r[j]，它們的值相等，并且 r[i] 在 r[j] 的前面。如果排序后，r[i] 仍然在 r[j] 的前面，那么這個排序算法就是穩定的。

1.2 常見的排序算法概覽

為了對各種排序算法有個整體的印象，我們可以通過下面這張圖來梳理一下它們的分類關系。

2. 常見排序算法的實現

2.1 插入排序 (Insertion Sort)

2.1.1 基本思想

插入排序（Insertion Sort）是一種非常直觀的排序算法。它的工作原理可以聯想一下我們平時打撲克牌整理手牌的過程：每次摸一張新牌，都會把它插入到已經排好序的手牌中的合適位置，直到所有牌都摸完，手牌也就變得有序了。

2.1.2 直接插入排序

直接插入排序是插入排序中最基礎的一種。它的核心思路是：通過構建一個有序序列，對于還沒排序的數據，在已排序的序列中從后往前掃描，找到它應該在的位置并插入進去。

我們可以這樣想象整個過程：當處理到第 i 個元素時（i 從 1 開始），我們假定它前面的 array[0] 到 array[i-1] 這些元素已經是有序的了。現在，我們需要為 array[i] 這個新來的元素找到它的位置。我們拿著 array[i] 從后往前，依次和 array[i-1], array[i-2]… 這些比較，直到找到一個比它小或等于它的元素，那么那個位置的后面就是 array[i] 的新位置。為了給它騰出位置，所有比它大的元素都需要順序地向后挪一個位置。

參考代碼：

    /*** 直接插入排序* 時間復雜度：O(N^2)* 空間復雜度：O(1)* 穩定性：穩定的* 一個本身是穩定的排序可以被實現為不穩定的，但反過來則不行。* 最好情況：當數組本身就是有序的，時間復雜度為 O(N)。數據越趨于有序，直接插入排序的效率就越高。* @param array 待排序數組*/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 {// 找到了比 tmp 小或等于的元素，說明 tmp 應該插在這里的后面break;}}// 將 tmp 放置到正確的插入位置array[j + 1] = tmp;}}

直接插入排序的特性總結：

1. 數據敏感性：元素集合越接近有序，直接插入排序算法的時間效率就越高。
2. 時間復雜度：平均和最壞情況下都是 O(N^2)。
3. 空間復雜度：O(1)，因為它是一個原地排序算法。
4. 穩定性：穩定。

優缺點分析

• 優點：
  • 實現起來很簡單，代碼邏輯清晰易懂。
  • 對于小規模數據或者基本有序的數據，排序效率相當不錯。
  • 是原地排序，幾乎不需要額外的存儲空間。
  • 是一種穩定的排序算法，能保證相同元素的相對順序不變。
• 缺點：
  • 時間復雜度是 O(N^2)，當數據量很大時，性能會急劇下降，不太適合處理大規模數據集。

2.1.3 希爾排序 (Shell Sort)

希爾排序，可以看作是直接插入排序的“威力加強版”，它的另一個名字叫“縮小增量排序”。這個名字很形象地道出了它的精髓。

我們知道直接插入排序有兩個特點：

• 當數據幾乎有序時，它的效率非常高，接近線性時間 O(N)。
• 但在大多數情況下，它效率又很低，因為元素每次只能移動一個位置，像“龜速”一樣。

希爾排序正是抓住了這兩點，進行了一次非常巧妙的優化。它的核心思想是：先讓數組變得“大致有序”，再進行最終的插入排序。

具體怎么做呢？它引入了一個“增量”gap的概念。

1. 分組預排序：先選擇一個較大的增量 gap（比如數組長度的一半），將整個數組按照這個增量分成若干個小組。例如，array[0], array[gap], array[2*gap]… 屬于一個組；array[1], array[1+gap], array[1+2*gap]… 屬于另一個組。然后對每個小組內部進行直接插入排序。這一步的目的就是讓數據進行“大跨步”的移動，快速將較小的元素移動到前面，較大的元素移動到后面，讓整個數組迅速變得“基本有序”。
2. 縮小增量，重復過程：完成一輪后，縮小增量 gap（比如再除以2），然后重復上面的分組和組內排序過程。隨著 gap 的不斷縮小，整個數組的有序程度會越來越高。
3. 最終排序：當增量 gap 縮小到 1 時，整個數組已經非常接近有序了。此時再對全體記錄進行一次直接插入排序，由于數據已經“基本有序”，這次排序的效率會非常高。

這個動圖可能有點快，有點難理解。我們自己畫一個來展示🖌

參考代碼：

    /*** 希爾排序* 時間復雜度：約為 O(N^1.3) 到 O(N^1.5)，取決于增量序列的選擇* 空間復雜度：O(1)* 穩定性：不穩定的* @param array 待排序數組*/public static void shellSort(int[] array) {// 初始增量為數組長度int gap = array.length;// 循環縮小增量，直到增量為1while (gap > 1) {// 每次將增量減半gap /= 2;// 對當前增量下的各個分組進行插入排序shell(array, gap);// 這里的寫法是單純為了接口(主函數只傳遞一個array參數)統一多套了一層方法}}/*** 對指定增量(gap)的子序列進行直接插入排序* @param array 待排序數組* @param gap   增量*/private static void shell(int[] array, int gap) {// 從第 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) {// 將大于 tmp 的元素后移array[j + gap] = array[j];} else {// 找到插入位置break;}}// 將 tmp 插入到正確的位置array[j + gap] = tmp;}}

希爾排序的特性總結：

1. 優化思路：希爾排序可以看作是對直接插入排序的一種分組優化策略。
2. 預排序：當 gap > 1 時，所做的都是預排序，目的是讓整個數組宏觀上變得越來越有序。當 gap == 1 時，數組已經非常接近有序狀態，此時的直接插入排序效率極高，從而達到了整體優化的效果。
3. 時間復雜度：希爾排序的時間復雜度是一個比較復雜的數學問題，因為它嚴重依賴于 gap 增量序列的選擇。目前還沒有一個公認的最優增量序列。通常認為其時間復雜度在 O(N^1.3) 到 O(N^1.5) 之間，比 O(N^2) 要好得多。
4. 穩定性：由于相同元素的記錄可能被分到不同的子序列中，它們的相對順序可能會在排序過程中發生改變，因此希爾排序是不穩定的。

關于 gap 的選擇

增量序列的選擇是希爾排序性能的關鍵。不同的教材和文獻中給出了不同的建議。

在《數據結構(C語言版)》 by 嚴蔚敏 中，建議的增量序列是 n/2, n/4, ..., 1。

而在《數據結構-用面向對象方法與C++描述》 by 殷人昆 中，提到了其他可能的序列。

著名計算機科學家 Knuth 經過大量實驗，提出了一個經典的增量序列 1, 4, 13, 40, ...，其性能相對較好。在實際應用中，我們通常采用 n/2 的方式，因為它簡單且效果尚可。根據估算，其時間復雜度大約在：
$$O(n^{1.25})\text{?到?}O(1.6\times n^{1.25})$$

2.2 選擇排序 (Selection Sort)

選擇排序（Selection Sort）的思路非常耿直：每一次遍歷，都只為了做一件事——找到當前范圍里最小（或最大）的那個元素，然后把它放到隊伍的末尾（或開頭）。

這種算法有一個很“公平”的特點：不管輸入的數據長什么樣，它都勤勤懇懇地執行 O(N2) 次操作，從不偷懶。所以，它比較適合那些數據規模不大的場景。要說優點，可能就是它不需要額外的內存空間。

2.2.1 直接選擇排序

直接選擇排序是選擇排序最直接的實現。它的工作流程可以分解為以下幾步：

1. 首先，在整個數組 array[0] 到 array[n-1] 中，地毯式搜索，找到最小的那個元素。
2. 然后，把它和 array[0] 位置的元素交換。這樣，整個數組中最小的元素就“歸位”了。
3. 接下來，在剩下的 array[1] 到 array[n-1] 中，重復上面的過程：找到這個范圍內的最小值，和 array[1] 交換。
4. 如此循環，每次都從“待排序”的部分里選出最小的，放到“已排序”部分的末尾，直到所有元素都“歸位”。

參考代碼：

    /*** 直接選擇排序* 時間復雜度：O(N^2)，與數據初始順序無關* 空間復雜度：O(1)* 穩定性：不穩定的* @param array 待排序數組*/public static void selectSort(int[] array) {// 外層循環控制排序的輪數，也代表了已排序區間的末尾for (int i = 0; i < array.length; i++) {int minIndex = i; // 假設當前位置的元素是未排序區間的最小值// 內層循環在未排序區間 [i+1, array.length) 中尋找真正的最小值for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j; // 如果找到更小的值，更新最小值的索引}}// 將找到的最小值與當前輪次的起始位置交換swap(array, i, minIndex);}}/*** 雙向選擇排序 (優化版)* 在一輪中同時找到最大值和最小值*/public static void selectSort2(int[] array) {int left = 0;int right = array.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;// 在 [left, right] 區間內尋找最大值和最小值的索引for (int i = left + 1; i <= right; i++) {if (array[i] < array[minIndex]) {minIndex = i;}if (array[i] > array[maxIndex]) {maxIndex = i;}}// 將最小值交換到左邊界swap(array, left, minIndex);// 這里有個小陷阱：如果本輪的最大值恰好在 left 位置，// 經過上一步交換，它已經被換到了 minIndex 的位置，所以需要更新 maxIndex。if (maxIndex == left) {maxIndex = minIndex;}// 將最大值交換到右邊界swap(array, right, maxIndex);left++;right--;}}

關于 selectSort2 的一點思考：
這種“雙向選擇排序”的優化，并沒有從根本上改變選擇排序 O(N2) 的時間復雜度。它的改進主要體現在“常數”級別上，通過在一輪遍歷中同時搞定最大和最小兩個元素，使得外層循環的次數減少了一半。
在實際測試中，對于中等規模的數據，這種優化可能會帶來一些可見的性能提升。但對于大數據集，它依然無法和 O(N log N) 的高效排序算法（如快排、歸并、堆排）相比較速度。同時，代碼邏輯也變得更復雜了，尤其要注意 maxIndex 的更新，算是一種用代碼簡潔性換取微小性能提升的嘗試。

直接選擇排序的特性總結：

1. 易于理解：思路簡單清晰，但效率不高，在實際工程中很少被采用。
2. 時間復雜度：O(N2)，雷打不動。
3. 空間復雜度：O(1)，原地排序。
4. 穩定性：不穩定。比如序列 [5, 8, 5, 2, 9]，第一輪會把第一個 5 和 2 交換，導致兩個 5 的相對順序改變。

2.2.2 堆排序 (Heap Sort)

堆排序（Heap Sort）可以看作是選擇排序的一種高階進化版。它巧妙地利用了“堆”這個數據結構來高效地完成“選擇”這個動作。

在開始之前，有個關鍵點需要記住：排升序要建大頂堆，排降序要建小頂堆。為什么呢？

• 大頂堆：每個節點的值都比它的子節點大或相等。這意味著堆頂元素永遠是整個堆里最大的。
• 小頂堆：每個節點的值都比它的子節點小或相等。這意味著堆頂元素永遠是整個堆里最小的。

堆排序的過程分為兩大步：

1. 建堆：將無序的數組原地構建成一個大頂堆（以升序為例）。
2. 排序：
   a. 將堆頂元素（當前最大值）與堆末尾的元素交換。此時，最大的元素就“歸位”到了數組的末尾。
   b. 將剩余的 n-1 個元素重新調整成一個新的大頂堆。
   c. 重復上述過程，每次都將當前堆的最大值交換到末尾，直到所有元素都有序。

參考代碼：

    /*** 堆排序 (升序)* 時間復雜度：O(N*logN)* 空間復雜度：O(1)* 穩定性：不穩定的* @param array 待排序數組*/public static void heapSort(int[] array) {// 1. 將無序數組構建成一個大頂堆createHeap(array);int end = array.length - 1;// 2. 循環將堆頂元素與末尾元素交換，并重新調整堆while (end > 0) {swap(array, 0, end); // 將堆頂(最大值)交換到數組末尾siftDown(array, 0, end); // 對 [0, end) 區間重新進行向下調整end--;}}/*** 構建大頂堆* 從最后一個非葉子節點開始，自下而上，自右向左進行向下調整*/private static void createHeap(int[] array) {for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {siftDown(array, parent, array.length);}}/*** 向下調整算法 (大頂堆)* @param array 數組* @param parent 要調整的子樹的根節點索引* @param len    堆的有效長度*/private static void siftDown(int[] array, int parent, int len) {int child = 2 * parent + 1; // 左孩子while (child < len) {// 如果右孩子存在且大于左孩子，則選擇右孩子進行比較if (child + 1 < len && array[child] < array[child + 1]) {child++;}// 如果父節點小于子節點中的較大者，則交換if (array[child] > array[parent]) {swap(array, parent, child);// 繼續向下調整parent = child;child = 2 * parent + 1;} else {// 如果父節點已經大于等于兩個子節點，則調整完成break;}}}

堆排序的特性總結：

1. 效率提升：通過使用堆這種數據結構，堆排序將選擇過程的效率從 O(N) 提升到了 O(logN)，使得整體排序效率大大提高。
2. 時間復雜度：O(N*logN)。
3. 空間復雜度：O(1)，原地排序。
4. 穩定性：不穩定。

2.3 交換排序

交換排序的核心思想很簡單：通過比較序列中兩個元素的值，來決定是否交換它們的位置。這類排序的共同特點是：努力將值大的元素往序列尾部移動，值小的元素往序列前部移動。

2.3.1 冒泡排序 (Bubble Sort)

冒泡排序（Bubble Sort）可能是我們接觸的第一個排序算法，非常經典。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個算法的名字由來也很有趣，因為越小的元素會經由交換慢慢“浮”到數列的頂端，就像碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣。

參考代碼：

    /*** 冒泡排序 (優化版)* 時間復雜度：最壞 O(N^2)，最好 O(N)* 空間復雜度：O(1)* 穩定性：穩定的* @param array 待排序數組*/public static void bubbleSort(int[] array) {// 外層循環控制排序的輪數for (int i = 0; i < array.length - 1; i++) {boolean flag = false; // 優化標志位// 內層循環進行相鄰元素的比較和交換for (int j = 0; j < array.length - 1 - i; j++) {if (array[j] > array[j + 1]) {swap(array, j, j + 1);flag = true; // 發生了交換}}// 如果在一整輪比較中都沒有發生任何交換，說明數組已經有序if (!flag) {break; // 提前結束排序}}}

冒泡排序的特性總結：

1. 易于理解：冒泡排序是交換排序中最容易理解的一種。
2. 時間復雜度：O(N2)。雖然有優化，但在最壞情況下依然是這個量級。
3. 空間復雜度：O(1)。
4. 穩定性：穩定。

2.3.2 快速排序 (Quick Sort)

快速排序（Quick Sort）是由圖靈獎得主 Hoare 在 1962 年提出的。它的思想完美體現了分治法（Divide and Conquer）。

核心思想：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

可以說，快速排序是冒泡排序的一種遞歸分治改進版本。它的名字起得名副其實，就是快！在處理大規模數據時，它是目前公認的最快的排序算法之一。

    // 快速排序主框架 (遞歸)void quickSort(int[] array, int left, int right) {// 遞歸終止條件：區間只有一個或沒有元素if (left >= right) {return;}// 核心步驟：對 [left, right] 區間進行分區，找到基準值的最終位置int pivotIndex = partition(array, left, right);// 分治：遞歸地對左右兩個子區間進行排序quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex + 1, right);}

這個遞歸框架和二叉樹的前序遍歷非常相似，理解了這一點，就能很快地寫出主干代碼。接下來的關鍵，就在于如何實現 partition（分區）這個核心操作。

partition 的目標是：在數組的一個區間內，選定一個基準值（pivot），然后將所有小于基準值的元素移動到它的左邊，所有大于基準值的元素移動到它的右邊，最后返回基準值所在的最終索引。

常見的 partition 實現方式有三種：

2.3.2.1 Hoare 法

這是 Hoare 本人提出的原始版本。

• 思路：選定最左邊的元素為基準值。設置左右兩個指針，右指針從右向左找第一個小于基準值的數，左指針從左向右找第一個大于基準值的數，然后交換它們。重復這個過程，直到左右指針相遇，最后將基準值與相遇位置的元素交換。

    // Hoare 分區法private static int partitionHoare(int[] array, int left, int right) {int pivotIndex = left; // 基準值的初始索引int pivot = array[left]; // 基準值while (left < right) {// 右指針從右向左找小while (left < right && array[right] >= pivot) {right--;}// 左指針從左向右找大while (left < right && array[left] <= pivot) {left++;}swap(array, left, right);}// 將基準值換到相遇點swap(array, pivotIndex, left);return left; // 返回基準值最終的位置}

2.3.2.2 挖坑法

挖坑法是對 Hoare 法的一種形象化理解，更容易掌握。

• 思路：將最左邊的元素（基準值）挖出來，形成第一個“坑”。然后右指針從右向左找一個小的數，填到左邊的坑里，自己形成一個新的坑。接著左指針從左向右找一個大的數，填到右邊的坑里，自己又形成一個新坑。如此交替，直到左右指針相遇，最后將最初挖出的基準值填入最后一個坑中。
  

    // 挖坑法private static int partitionWiggle(int[] array, int left, int right) {int pivot = array[left]; // 將基準值挖出，形成第一個坑while (left < right) {// 右指針找小，填左坑while (left < right && array[right] >= pivot) {right--;}array[left] = array[right]; // 填坑// 左指針找大，填右坑while (left < right && array[left] <= pivot) {left++;}array[right] = array[left]; // 填坑}array[left] = pivot; // 將基準值填入最后的坑return left;}

2.3.2.3 前后指針法

這種方法也非常經典，思路清晰。

• 思路：選定最左邊的元素為基準值。使用兩個指針 prev 和 cur，prev 指向“小于基準值區域”的末尾，cur 負責向右遍歷數組。如果 cur 遇到的元素小于基準值，就將 prev 向后移動一位，并交換 prev 和 cur 指向的元素。遍歷結束后，將基準值與 prev 指向的元素交換即可。

    // 前后指針法private static int partitionPointer(int[] array, int left, int right) {int pivot = array[left];int prev = left; // “小于區域”的邊界for (int cur = left + 1; cur <= right; cur++) {if (array[cur] < pivot) {prev++;swap(array, cur, prev);}}swap(array, left, prev);return prev;}

三種分區方法的比較

• Hoare 法：是快排的“原版”實現，但實現起來略微復雜，尤其是最后基準值的交換位置需要想清楚。
• 挖坑法：邏輯最形象，最容易理解和手寫，是初學者掌握快排的首選。
• 前后指針法：代碼簡潔，也是一種非常高效的實現方式，在很多標準庫中可以看到它的身影。

在面試或做題時，挖坑法通常是最穩妥、最不容易出錯的選擇。

2.3.3 快速排序的優化

理論上，快速排序的時間復雜度是 O(N*logN)，性能非常出色。但通過實際測試我們會發現，在某些特定情況下，比如一個已經完全有序或逆序的數組，我們基礎版本的快速排序可能會“退化”，甚至拋出 StackOverflowError 棧溢出異常。

這是因為，如果每次選取的基準值（pivot）都恰好是當前區間的最大或最小值，那么分區操作就會變得極不均衡，一邊是 0 個元素，另一邊是 n-1 個元素。這會導致遞歸樹變成一條長長的鏈，遞歸深度接近 N，當 N 非常大時，就會耗盡調用棧空間。

為了解決這些問題，我們可以從以下幾個方面對快速排序進行優化：

2.3.3.1 優化一：三數取中法選擇基準值

一個好的基準值，應該能盡可能地將數組分成規模相當的兩個部分。最理想的基準值是數組的中位數，但找中位數本身代價太高。

一個簡單又高效的替代方案是“三數取中法”：從區間的 left, mid, right 三個位置中，選擇大小居中的那個數作為基準值。這樣可以極大地避免選到極端值，讓分區更均衡。

    // 三數取中法private static int getMedian(int[] array, int left, int right) {int mid = left + (right - left) / 2; // 避免整數溢出// 通過一系列比較，最終讓 array[mid] 成為三數中的中值if (array[left] > array[right]) {swap(array, left, right);}if (array[mid] > array[right]) {swap(array, mid, right);}if (array[mid] > array[left]) {swap(array, mid, left);}// 此時，array[left] 就是三數中的中值return left;}

在 partition 方法的一開始，調用 getMedian 并將返回的索引與 left 交換，就可以確保我們總是用一個相對“靠譜”的基準值來進行分區。

2.3.3.2 優化二：小區間改用插入排序

遞歸是有開銷的。當快速排序的遞歸深入到很小的子區間時，再繼續遞歸就有點“殺雞用牛刀”了。由于插入排序在處理小規模、近乎有序的數據時效率很高，我們可以在遞歸到一定深度（例如，當區間長度小于某個閾值，如 16）時，停止遞歸，轉而使用插入排序來處理這些小區間。

    // 對小區間使用插入排序private static void insertSortRange(int[] array, int left, int right) {for (int i = left + 1; i <= right; i++) {int tmp = array[i];int j = i - 1;for (; j >= left && array[j] > tmp; j--) {array[j + 1] = array[j];}array[j + 1] = tmp;}}// 在快速排序主框架中加入判斷void quickSort(int[] array, int left, int right) {if (left >= right) return;// 當區間長度小于閾值時，使用插入排序if (right - left + 1 <= 16) {insertSortRange(array, left, right);return;}// ... 后續分區和遞歸邏輯}

2.3.3.3 優化三：非遞歸實現

為了從根本上避免棧溢出的風險，我們可以將快速排序從遞歸形式改寫為非遞歸形式。這通常需要借助一個棧（或隊列）來手動模擬遞歸調用的過程。

    // 快速排序的非遞歸實現public static void quickSortNonRecursive(int[] array) {if (array == null || array.length <= 1) {return;}Deque<Integer> stack = new ArrayDeque<>();stack.push(array.length - 1);stack.push(0);while (!stack.isEmpty()) {int left = stack.pop();int right = stack.pop();if (left >= right) {continue;}int pivotIndex = partition(array, left, right);// 先壓入右半部分，再壓入左半部分stack.push(right);stack.push(pivotIndex + 1);stack.push(pivotIndex - 1);stack.push(left);}}

2.4 歸并排序 (Merge Sort)

歸并排序（Merge Sort）是另一個基于分治法的、非常高效的排序算法。它穩定、可靠，無論輸入數據是什么樣，都能保證 O(N*logN) 的時間復雜度。

2.4.1 基本思想

它的核心思想可以概括為“先拆分，后合并”：

1. 分解 (Divide)：不斷地將一個大數組一分為二，直到每個子數組都只包含一個元素。顯然，只含一個元素的數組本身就是有序的。
2. 合并 (Conquer)：然后，再將這些有序的子數組兩兩合并，形成一個更大的有序數組。這個合并的過程是關鍵，它能保證兩個有序的子數組在合并后，新的大數組依然是有序的。
3. 重復這個合并過程，直到所有子數組最終合并成一個完整的、有序的大數組。

參考代碼：

    /*** 歸并排序 (遞歸實現)* 時間復雜度：O(N*logN)* 空間復雜度：O(N)* 穩定性：穩定的* @param array 待排序數組*/public static void mergeSort(int[] array) {mergeSortRecursive(array, 0, array.length - 1);}private static void mergeSortRecursive(int[] array, int left, int right) {if (left >= right) {return;}int mid = left + (right - left) / 2;// 遞歸排序左半部分mergeSortRecursive(array, left, mid);// 遞歸排序右半部分mergeSortRecursive(array, mid + 1, right);// 將兩個有序的子數組合并merge(array, left, mid, right);}// 合并兩個有序子數組的核心方法private static void merge(int[] array, int left, int mid, int right) {int[] temp = new int[right - left + 1]; // 臨時數組存放合并結果int i = left;    // 左子數組的起始指針int j = mid + 1; // 右子數組的起始指針int k = 0;       // 臨時數組的指針// 比較兩個子數組的元素，按序填充到臨時數組while (i <= mid && j <= right) {if (array[i] <= array[j]) { // 使用 <= 保證穩定性temp[k++] = array[i++];} else {temp[k++] = array[j++];}}// 將剩余的元素（如果有一邊先走完）復制到臨時數組while (i <= mid) {temp[k++] = array[i++];}while (j <= right) {temp[k++] = array[j++];}// 將排好序的臨時數組內容復制回原數組的相應位置for (int l = 0; l < temp.length; l++) {array[left + l] = temp[l];}}

非遞歸實現：

歸并排序也可以用非遞歸（迭代）的方式實現，思路是從底向上進行合并。

• 首先，將數組看作是 N 個長度為 1 的有序子數組。
• 然后，兩兩合并，得到 N/2 個長度為 2 的有序子數組。
• 接著，再兩兩合并，得到 N/4 個長度為 4 的有序子數組。
• …如此循環，gap（每次合并的子數組長度）從 1, 2, 4, … 翻倍增長，直到 gap 大于等于數組長度。

    /*** 歸并排序 (非遞歸實現)*/public static void mergeSortNonRecursive(int[] array) {int n = array.length;for (int gap = 1; gap < n; gap *= 2) {for (int i = 0; i < n; i += 2 * gap) {int left = i;int mid = Math.min(i + gap - 1, n - 1);int right = Math.min(i + 2 * gap - 1, n - 1);merge(array, left, mid, right);}}}

2.4.2 歸并排序總結

1. 缺點：歸并排序最大的缺點是需要 O(N) 的額外空間復雜度，這在內存受限的場景下是個問題。
2. 優點：它的思考方式，尤其適合解決在磁盤上進行的“外部排序”問題。
3. 時間復雜度：O(N*logN)，非常穩定。
4. 空間復雜度：O(N)。
5. 穩定性：穩定。

2.4.3 海量數據的排序問題（外部排序）

當我們需要處理的數據量遠超內存容量時，比如有 100G 的數據文件，但內存只有 1G，這時就必須借助外部存儲（如磁盤）來進行排序，這就是外部排序。

歸并排序的思想是解決這類問題的天然利器。

1. 分割：首先，將 100G 的大文件分割成 200 個 512M 的小文件。
2. 內部排序：然后，依次將每個 512M 的小文件讀入內存，使用任意一種內部排序算法（比如快速排序）對其進行排序，并將排好序的結果寫回磁盤，生成 200 個有序的臨時文件。
3. 多路歸并：最后，對這 200 個有序的臨時文件進行一次“多路歸并”。每次從每個文件中讀取一小部分數據到內存中的輸入緩沖區，然后在這 200 個元素中找到最小的，寫入到最終的輸出文件中。重復這個過程，直到所有文件都被合并完畢。

通過這種方式，我們就能在有限的內存下，完成對海量數據的排序。

3. 排序算法性能大比拼

下面這個表格清晰地展示了各種排序算法在不同情況下的性能表現和特點。

排序方法	最好情況	平均情況	最壞情況	空間復雜度	穩定性
插入排序	O(N)	O(N2)	O(N2)	O(1)	穩定
希爾排序	O(N)	O(N^1.3)	O(N2)	O(1)	不穩定
選擇排序	O(N2)	O(N2)	O(N2)	O(1)	不穩定
堆排序	O(N*logN)	O(N*logN)	O(N*logN)	O(1)	不穩定
冒泡排序	O(N)	O(N2)	O(N2)	O(1)	穩定
快速排序	O(N*logN)	O(N*logN)	O(N2)	O(logN)	不穩定
歸并排序	O(N*logN)	O(N*logN)	O(N*logN)	O(N)	穩定

幾個記憶小技巧：

• 穩定性：在常見的排序算法中，只有插入排序、冒泡排序、歸并排序是穩定的。可以記作“插冒歸（插帽龜）”是穩定的。
• 最快：在平均情況下，快速排序通常被認為是“最快”的，這也是它名字的由來。
• 空間：歸并排序是典型的“空間換時間”代表，需要 O(N) 的額外空間。而快速排序的遞歸實現需要 O(logN) 的棧空間。

4. 非比較排序：另一種思路

我們前面討論的所有排序算法，都基于一個共同的前提：通過比較元素的大小來決定它們的順序。但還有一類排序算法，它們另辟蹊徑，不通過比較，也能完成排序，我們稱之為“非比較排序”。這類算法通常非常快，能達到線性時間復雜度，但它們的使用場景也有限制。

4.1 計數排序 (Counting Sort)

計數排序就是非比較排序中的一個典型代表。它非常適用于對一個確定范圍內的整數進行排序。

核心思想：它的核心思路不是比較，而是“計數”。

1. 找出待排序數組中的最大值 max 和最小值 min，以確定需要計數的范圍。
2. 創建一個計數數組 count，長度為 max - min + 1。
3. 遍歷原數組，將每個元素出現的次數，統計到 count 數組的相應位置上。比如，元素 x 出現了幾次，就在 count[x - min] 的位置記上幾。
4. 最后，遍歷計數數組 count，根據每個元素的計數值，將元素按順序重新寫回原數組。

    /*** 計數排序* 適用場景：數據量大，但數據范圍相對集中（例如，對百萬考生的百分制成績進行排序）* 時間復雜度：O(N + range)，其中 range 是數據的范圍 (max - min)* 空間復雜度：O(range)* 穩定性：可以實現為穩定的，但當前代碼版本是不穩定的* @param array 待排序數組*/public static void countSort(int[] array) {if (array == null || array.length <= 1) {return;}// 1. 找到數據的范圍int maxVal = array[0];int minVal = array[0];for (int i = 1; i < array.length; i++) {if (array[i] < minVal) {minVal = array[i];}if (array[i] > maxVal) {maxVal = array[i];}}// 2. 創建計數數組并統計頻率int range = maxVal - minVal + 1;int[] count = new int[range];for (int x : array) {count[x - minVal]++;}// 3. 根據計數結果，重寫原數組int arrayIndex = 0;for (int i = 0; i < range; i++) {while (count[i] > 0) {array[arrayIndex++] = i + minVal;count[i]--;}}}

4.2 桶排序與基數排序

除了計數排序，桶排序（Bucket Sort）和基數排序（Radix Sort）也是常見的非比較排序算法，它們同樣能達到線性的時間復雜度。

• 桶排序：可以看作是計數排序的升級版，它將數據分布到有限數量的“桶”里，然后對每個桶里的數據再單獨進行排序。
• 基數排序：一種非常巧妙的排序方式，它將整數按位數切割成不同的數字，然后按每個位數分別比較。

由于篇幅關系，這里就不展開詳細介紹了，感興趣的同學可以查閱相關資料深入了解。

5. 總結

排序是計算機科學中最基礎也最核心的問題之一。通過這次學習，我們一起探索了從簡單直觀的 O(N2) 算法（如冒泡、插入、選擇），到更高效的 O(N*logN) 算法（如快排、歸并、堆排）的演進過程。

每種排序算法都有其獨特的思想和適用場景：

• 插入排序和冒泡排序簡單易懂，在數據量小或基本有序時表現不錯。
• 希爾排序作為插入排序的改進版，顯著提升了性能。
• 選擇排序思路直接，但效率較低；而它的高級版堆排序則一躍成為高效排序的代表。
• 快速排序名副其實，是大多數場景下的首選，但需要注意最壞情況下的優化。
• 歸并排序穩定可靠，是外部排序和需要穩定性的場景下的不二之選。
• 最后，計數排序等非比較排序算法為我們打開了新世界的大門，展示了在特定條件下超越比較排序極限的可能性。

沒有“最好”的算法，只有“最合適”的算法。深刻理解它們的原理、優劣和適用場景，才能在解決實際問題時游刃有余。