算法學習筆記：13.歸并排序——從原理到實戰，涵蓋 LeetCode 與考研 408 例題

歸并排序是一種基于分治策略的經典排序算法，由約翰?馮?諾依曼在 1945 年提出。它以穩定的 O (nlogn) 時間復雜度和良好的可并行性，在大規模數據排序場景中占據重要地位。與快速排序的 “先分區后排序” 不同，歸并排序采用 “先排序后合并” 的思路，其穩定性（相等元素相對順序不變）使其在數據庫排序等對穩定性有要求的場景中備受青睞。

歸并排序算法核心思路

歸并排序的核心思想是分治（Divide and Conquer），即將一個大問題分解為若干個小問題，分別解決后再將結果合并。具體可分為三個步驟：分解（Divide）、治理（Conquer）、合并（Merge）。

關鍵步驟解析

（1）分解（Divide）

將待排序數組不斷二分，直到每個子數組只包含一個元素（此時子數組天然有序）。例如，對數組[8, 4, 5, 7, 1, 3, 6, 2]，分解過程如下：

第一層：[8,4,5,7] 和 [1,3,6,2]

第二層：[8,4]、[5,7] 和 [1,3]、[6,2]

第三層：[8]、[4]、[5]、[7]、[1]、[3]、[6]、[2]

（2）治理（Conquer）

遞歸處理每個子數組，由于當子數組長度為 1 時已天然有序，因此這一步主要是遞歸的終止條件。

（3）合并（Merge）

將兩個有序子數組合并為一個更大的有序數組，這是歸并排序的核心步驟。合并過程需借助一個輔助數組，具體步驟如下：

初始化兩個指針i和j，分別指向兩個子數組的起始位置。

初始化輔助數組指針k，指向輔助數組起始位置。

比較i和j指向的元素，將較小的元素放入輔助數組，并移動對應指針。

重復步驟 3，直到其中一個子數組遍歷完畢。

將剩余子數組的元素依次放入輔助數組。

將輔助數組的元素復制回原數組的對應位置。

歸并排序的整體流程

歸并排序的整體流程是 “分解 - 合并” 的遞歸過程，可用以下流程圖表示：

?歸并排序的 Java 實現（基礎版）

public class MergeSortBasic {// 對外暴露的排序方法public static void sort(int[] arr) {if (arr == null || arr.length <= 1) {return;}int[] temp = new int[arr.length]; // 輔助數組（避免遞歸中重復創建）mergeSort(arr, 0, arr.length - 1, temp);}// 遞歸執行歸并排序private static void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {int mid = left + (right - left) / 2; // 避免溢出，等價于(left + right) / 2mergeSort(arr, left, mid, temp); // 左子數組排序mergeSort(arr, mid + 1, right, temp); // 右子數組排序merge(arr, left, mid, right, temp); // 合并}}// 合并兩個有序子數組private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left; // 左子數組起始索引int j = mid + 1; // 右子數組起始索引int k = left; // 輔助數組起始索引// 比較并合并兩個子數組while (i <= mid && j <= right) {if (arr[i] <= arr[j]) { // 保持穩定性（<= 確保相等元素左子數組在前）temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 處理左子數組剩余元素while (i <= mid) {temp[k++] = arr[i++];}// 處理右子數組剩余元素while (j <= right) {temp[k++] = arr[j++];}// 將輔助數組復制回原數組for (k = left; k <= right; k++) {arr[k] = temp[k];}}// 測試public static void main(String[] args) {int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};sort(arr);for (int num : arr) {System.out.print(num + " "); // 輸出：1 2 3 4 5 6 7 8}}}

LeetCode 例題實戰

例題 1：912. 排序數組（中等）

題目描述：給你一個整數數組 nums，請你將該數組升序排列。

示例：

輸入：nums = [5,2,3,1]

輸出：[1,2,3,5]

解題思路：直接使用歸并排序對數組進行排序。與快速排序相比，歸并排序的時間復雜度穩定為 O (nlogn)，適合處理包含大量重復元素或近乎有序的數組。

Java 代碼實現：


class Solution {public int[] sortArray(int[] nums) {if (nums == null || nums.length <= 1) {return nums;}int[] temp = new int[nums.length];mergeSort(nums, 0, nums.length - 1, temp);return nums;}private void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid, temp);mergeSort(arr, mid + 1, right, temp);merge(arr, left, mid, right, temp);}}private void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left;int j = mid + 1;int k = left;while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}while (i <= mid) {temp[k++] = arr[i++];}while (j <= right) {temp[k++] = arr[j++];}for (k = left; k <= right; k++) {arr[k] = temp[k];}}}

復雜度分析：

時間復雜度：O (nlogn)，無論數組初始狀態如何，分解和合并的總操作次數均為 O (nlogn)。

空間復雜度：O (n)，來自輔助數組temp。

例題 2：315. 計算右側小于當前元素的個數（困難）

題目描述：給你一個整數數組 nums ，按要求返回一個新數組 counts 。數組 counts 有該性質：counts[i] 的值是 nums[i] 右側小于 nums[i] 的元素的數量。

示例：

輸入：nums = [5,2,6,1]
輸出：[2,1,1,0]
解釋：
5 的右側有 2 個更小的元素 (2 和 1)
2 的右側有 1 個更小的元素 (1)
6 的右側有 1 個更小的元素 (1)
1 的右側沒有更小的元素

解題思路：本題可借助歸并排序的合并過程統計逆序對。在合并兩個有序子數組時，當右子數組元素nums[j]小于左子數組元素nums[i]時，右子數組中j到mid+1的所有元素均小于nums[i]，因此counts[i]需加上right - j + 1（剩余元素個數）。為避免原數組索引被排序打亂，需額外記錄元素原始索引。

Java 代碼實現：

class Solution {private int[] counts;public List<Integer> countSmaller(int[] nums) {int n = nums.length;counts = new int[n];if (n == 0) {return new ArrayList<>();}// 構建數組，存儲值和原始索引int[][] arr = new int[n][2];for (int i = 0; i < n; i++) {arr[i][0] = nums[i];arr[i][1] = i;}int[][] temp = new int[n][2]; // 輔助數組mergeSort(arr, 0, n - 1, temp);// 轉換為List返回List<Integer> result = new ArrayList<>();for (int count : counts) {result.add(count);}return result;}private void mergeSort(int[][] arr, int left, int right, int[][] temp) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid, temp);mergeSort(arr, mid + 1, right, temp);merge(arr, left, mid, right, temp);}}private void merge(int[][] arr, int left, int mid, int right, int[][] temp) {int i = left;int j = mid + 1;int k = left;while (i <= mid && j <= right) {if (arr[i][0] <= arr[j][0]) {// 右子數組中j到right的元素均小于arr[i][0]counts[arr[i][1]] += right - j + 1;temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 左子數組剩余元素，右側已無元素，無需計數while (i <= mid) {temp[k++] = arr[i++];}// 右子數組剩余元素，左側已無元素，無需計數while (j <= right) {temp[k++] = arr[j++];}// 復制回原數組for (k = left; k <= right; k++) {arr[k] = temp[k];}}}

復雜度分析：

時間復雜度：O (nlogn)，歸并排序的時間復雜度為 O (nlogn)，合并過程中計數操作僅為 O (1)。

空間復雜度：O (n)，來自輔助數組和存儲索引的數組。

考研 408 例題解析

例題 1：基本概念與時間復雜度分析（選擇題）

題目：下列關于歸并排序的敘述中，正確的是（）。
A. 歸并排序的時間復雜度為 O (nlogn)，空間復雜度為 O (1)
B. 歸并排序是不穩定的排序算法
C. 歸并排序在最壞情況下的時間復雜度優于快速排序
D. 歸并排序適合對鏈表進行排序
答案：C、D
解析：
A 錯誤：歸并排序空間復雜度為 O (n)（輔助數組），鏈表排序可優化至 O (1)，但數組排序仍為 O (n)。
B 錯誤：歸并排序是穩定排序（合并時相等元素按原順序放置）。
C 正確：歸并排序最壞時間復雜度為 O (nlogn)，而快速排序最壞為 O (n2)。
D 正確：鏈表歸并排序無需輔助數組，通過指針操作合并，空間復雜度 O (logn)（遞歸棧），效率高。

例題 2：算法設計題（408 高頻考點）

題目：已知單鏈表的頭指針為head，設計一個算法對該鏈表進行歸并排序，要求時間復雜度為 O (nlogn)，空間復雜度為 O (logn)。

解題思路：鏈表歸并排序與數組歸并排序思路一致，但需注意：

分解：通過快慢指針找到鏈表中點，斷開鏈表為左右兩部分。

合并：通過指針操作合并兩個有序鏈表，無需輔助數組。

Java 代碼實現：

class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public class MergeSortList {public ListNode sortList(ListNode head) {// 基線條件：空鏈表或單節點鏈表無需排序if (head == null || head.next == null) {return head;}// 找到鏈表中點并斷開ListNode mid = findMid(head);ListNode rightHead = mid.next;mid.next = null; // 斷開// 遞歸排序左右鏈表ListNode left = sortList(head);ListNode right = sortList(rightHead);// 合并有序鏈表return merge(left, right);}// 快慢指針找中點（偶數節點取左中點）private ListNode findMid(ListNode head) {if (head == null) {return null;}ListNode slow = head;ListNode fast = head.next; // 確保偶數時取左中點while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}// 合并兩個有序鏈表private ListNode merge(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode curr = dummy;while (l1 != null < / doubaocanvas >
｝

希望本文能夠幫助讀者更深入地理解歸并排序，并在實際項目中發揮其優勢。謝謝閱讀！

希望這份博客能夠幫助到你。如果有其他需要修改或添加的地方，請隨時告訴我。