什么？歸并排序？這讓博主想起了大學那會被《數據結構與算法》支配的恐懼…
哈哈言歸正傳，一直想對算法做一個專欄，因為其實工作中很少很少有機會用到算法，倒是很多工具方法底層會使用，工作被各種需求業務“折磨”的讓大家很少再花費精力去深入這些底層，更別說很少有人天天刷算法，導致以前在學校為了應付面試和筆試（也包括社招）學習的這些玩意和基礎隨著時間慢慢消磨殆盡，所以這篇專欄來了！每一篇博主都會詳細說明這些算法的設計思想和代碼實現，幫助博主和大家共同進步，每篇如果有錯誤和需要改進的地方歡迎大家提出！下面開始我們第一篇，也是基礎的——歸并排序。

---

前言

歸并排序是一種基于分治法的高效排序算法，由馮·諾依曼于1945年首次提出。它以其穩定的O(n log n)時間復雜度和優雅的實現方式在算法領域占據重要地位。下面我將詳細介紹歸并排序的原理，并提供完整的Java實現。

---

🌟 核心思想

先給出歸并排序示意圖：

歸并排序的核心思想可概括為三步：

1. 分解：將待排序數組遞歸地分成兩個子數組。
2. 解決：對子數組進行排序（遞歸排序）。
3. 合并：將兩個有序子數組合并成一個有序數組。

原始數組：[38, 27, 43, 3, 9, 82, 10]分解過程：
1. [38, 27, 43, 3]  [9, 82, 10]
2. [38, 27] [43, 3]  [9, 82] [10]
3. [38] [27] [43] [3] [9] [82] [10]合并過程：
1. [27, 38] [3, 43]  [9, 82] [10]
2. [3, 27, 38, 43]    [9, 10, 82]
最終結果：[3, 9, 10, 27, 38, 43, 82]

?? Java實現

public class MergeSort {// 歸并排序主方法public static void mergeSort(int[] arr) {if (arr == null || arr.length <= 1) {return;}int[] temp = new int[arr.length];mergeSort(arr, temp, 0, arr.length - 1);}// 遞歸排序private static void mergeSort(int[] arr, int[] temp, int left, int right) {if (left < right) {int mid = left + (right - left) / 2; // 防止整數溢出// 遞歸排序左半部分mergeSort(arr, temp, left, mid);// 遞歸排序右半部分mergeSort(arr, temp, mid + 1, right);// 合并兩個有序子數組merge(arr, temp, left, mid, right);}}// 合并兩個有序子數組private static void merge(int[] arr, int[] temp, int left, int mid, int right) {// 復制數據到臨時數組System.arraycopy(arr, left, temp, left, right - left + 1);int i = left;      // 左子數組起始索引int j = mid + 1;  // 右子數組起始索引int k = left;     // 合并數組的起始索引// 比較左右子數組元素，將較小者放入原數組while (i <= mid && j <= right) {if (temp[i] <= temp[j]) {arr[k++] = temp[i++];} else {arr[k++] = temp[j++];}}// 復制左子數組剩余元素while (i <= mid) {arr[k++] = temp[i++];}// 復制右子數組剩余元素while (j <= right) {arr[k++] = temp[j++];}}// 測試代碼public static void main(String[] args) {int[] arr = {38, 27, 43, 3, 9, 82, 10};System.out.println("排序前: " + Arrays.toString(arr));mergeSort(arr);System.out.println("排序后: " + Arrays.toString(arr));}
}

算法解析

1. mergeSort()方法：
   • 公共入口方法。
   • 創建臨時數組避免在遞歸過程中重復創建。
   • 調用私有遞歸方法。
2. 遞歸排序：
   • 計算中點：mid = left + (right - left)/2（避免整數溢出）。
   • 遞歸排序左半部分：left到mid。
   • 遞歸排序右半部分：mid+1到right。
   • 合并兩個有序子數組。
3. merge()方法：
   • 復制當前段數據到臨時數組。
   • 使用三個指針分別追蹤：
     • i：左子數組當前位置
     • j：右子數組當前位置
     • k：合并后數組當前位置
   • 比較左右子數組元素，將較小者放入原數組。
   • 處理剩余元素。

🔍 時間復雜度分析

操作	時間復雜度
分解	O(log n)
合并	O(n)
總復雜度	O(n log n)

歸并排序在任何情況下的時間復雜度都是穩定的O(n log n)，這是它的最大優勢。

📦 空間復雜度

• O(n)：需要額外的空間存儲臨時數組
• 不是原地排序算法(in-place)

? 算法特性

1. 穩定性：保持相等元素的原始順序（關鍵：合并時left[i] <= right[j]）
2. 適用場景：大數據量排序、鏈表排序、外部排序
3. 不適用場景：內存受限的小數據量排序

? 優化技巧

1. 小數組切換插入排序：當子數組長度較小時使用插入排序。

歸并排序即使處理小規模數據仍需遞歸調用、分割合并等操作，其時間復雜度雖為O(n log n)，但?遞歸棧管理、函數調用等額外開銷的常數因子較大?，插入排序在小規模數據（如n≤15）時實際運行時間接近O(n)。數據量≤15時，元素局部有序概率高，實際操作次數接近線性，且其?簡單比較交換操作的常數因子極低?，在閾值范圍內性能顯著優于歸并排序。
ex: 常數因子指算法時間復雜度表示式中的固定系數（如O(2n)中的2），簡單交換位移不需要遞歸方法調用也不需要分配空間，自然開銷低。

private static final int INSERTION_THRESHOLD = 15;private static void mergeSort(int[] arr, int[] temp, int left, int right) {if (right - left <= INSERTION_THRESHOLD) {insertionSort(arr, left, right);return;}// 其余代碼不變
}private static void insertionSort(int[] arr, int left, int right) {for (int i = left + 1; i <= right; i++) {int key = arr[i];int j = i - 1;while (j >= left && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}

2. 邊界檢查優化：在合并前檢查左子數組最大值是否小于等于右子數組最小值。

// 在merge方法開始處添加
if (arr[mid] <= arr[mid + 1]) {return; // 已經有序，無需合并
}

3. 避免重復復制：通過交換輸入數組和臨時數組的角色減少復制操作

💡 實際應用場景

1. 大數據處理：MapReduce等分布式計算框架的底層排序
2. 外部排序：處理超過內存容量的數據集
3. 穩定排序需求：數據庫排序、訂單記錄處理
4. 鏈表排序：歸并排序是鏈表最高效的排序方式（鏈表歸并排序僅需修改節點指針指向，實現?O(1)空間復雜度?的原址排序）

🌐 總結

歸并排序以其穩定高效的特性，成為處理大規模數據的首選算法之一。雖然需要額外空間，但它的分治思想在算法設計中具有重要地位，是理解遞歸和分治策略的經典案例。

學過Java的小伙伴，Arrays.sort()與Collections.sort()?底層就是使用優化后的歸并排序呦，感興趣的小伙伴可以再深入研究下。