元数据卡

属性	值
难度	核心
前置	第 9 章 基础排序、递归
关键词	归并排序 · 快速排序 · 分治 · Lomuto 分区 · Hoare 分区 · O(n log n)
预计阅读	20 分钟

---

你的进度

基础排序给了你三种武器——可惜都是 O(n^2)。当数组规模变成几百万时，你必须突破到 O(n log n)。怎么做？分治：把数组切成两半，分别排好，再合并——归并排序。选一个支点，比它小的放左边、大的放右边，各自递归——快速排序。两种算法都基于分而治之，但性格截然不同。

---

你的任务

读完这一页，你应当能：徒手写出归并和快速排序的 Java 实现；画出 n=8 的归并递归树并分析复杂度；解释随机 pivot 如何防退化；对比归并与快排的优缺点。

---

分治思想

分治（Divide and Conquer）三步走：分解——把原问题切成子问题；解决——递归解决每个子问题；合并——把子问题的解合并成原问题的解。排序是分治最自然的应用场景。

---

归并排序：最规整的分治

核心直觉：把数组对半切，分别排好，再合并。 递归地切到只剩一个元素（天然有序），然后回溯合并。

        [38, 27, 43, 3, 9, 82, 10]
              /              \
     [38, 27, 43, 3]     [9, 82, 10]
       /        \           /     \
   [38, 27]   [43, 3]   [9]   [82, 10]
    /    \     /    \          /    \
 [38]  [27] [43]  [3]      [82]  [10]
    \    /     \    /          \    /
   [27, 38]   [3, 43]       [10, 82]
       \        /              /
     [3, 27, 38, 43]     [9, 10, 82]
              \              /
        [3, 9, 10, 27, 38, 43, 82]

合并时两个指针对比左右数组，取较小者写入结果。

Java 实现

import java.util.Arrays;

public class MergeSort {
    // 运行: javac MergeSort.java && java MergeSort
    // 输出: [3, 9, 10, 27, 38, 43, 82]
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1, n2 = right - mid;
        int[] L = new int[n1], R = new int[n2];
        System.arraycopy(arr, left, L, 0, n1);
        System.arraycopy(arr, mid + 1, R, 0, n2);
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) arr[k++] = L[i++];
            else arr[k++] = R[j++];
        }
        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }

    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }
}

复杂度分析：为什么最坏也是 O(n log n)？ 递归树每次切一半，树深 log n，每层合并总代价 O(n)，总代价 = O(n log n)。拿 n=1,000,000 举例：O(n^2) 是 10^12 次操作（几小时），O(n log n) 是 2千万次（毫秒级）。

场景	时间	空间	稳定
全部	O(n log n)	O(n)	稳定

代价：需要额外 O(n) 空间存放合并结果——经典的空间换时间。

---

快速排序：分治的叛逆者

核心直觉：选一个 pivot（支点），比它小的放左边，比它大的放右边。左右分别递归。 归并排序先切再排，快速排序反过来——先排再切，赌随机 pivot 大概率能均分。

Lomuto 分区（最简单，适合面试）

分区过程: arr=[10, 7, 8, 9, 1, 5], pivot=5

j=0: arr[0]=10 > 5 → 不动
j=1: arr[1]=7  > 5 → 不动
j=2: arr[2]=8  > 5 → 不动
j=3: arr[3]=9  > 5 → 不动
j=4: arr[4]=1 <= 5 → i=0, 交换 → [1, 7, 8, 9, 10, 5]
收尾：交换 arr[1] 和 arr[5] → [1, 5, 8, 9, 10, 7]
返回 pivot 位置: 1

import java.util.Arrays;

public class QuickSort {
    // 运行: javac QuickSort.java && java QuickSort
    // 输出: [1, 5, 7, 8, 9, 10]
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int p = partition(arr, low, high);
            quickSort(arr, low, p - 1);
            quickSort(arr, p + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // 选最后一个作 pivot
        int i = low - 1;        // 小值区域的右边界
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            }
        }
        int tmp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = tmp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] data = {10, 7, 8, 9, 1, 5};
        quickSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }
}

随机选 pivot —— 防退化

如果每次 pivot 恰好是最小/最大元素，复杂度退化成 O(n^2)。随机化解法（把随机选中的 pivot 换到末尾，复用 Lomuto 分区）：

import java.util.Random;

private static int randomPartition(int[] arr, int low, int high) {
    int r = low + new Random().nextInt(high - low + 1);
    int tmp = arr[r]; arr[r] = arr[high]; arr[high] = tmp;
    return partition(arr, low, high);
}

随机化之后退化概率几乎为 0。

复杂度

场景	时间	空间（递归栈）	稳定
最好 / 平均	O(n log n)	O(log n)	不稳定
最坏	O(n^2)	O(n)	不稳定

不稳定原因：分区时的跨越 swap 会打乱相等元素顺序。

---

归并与快排对比

维度	归并排序	快速排序
时间复杂度	O(n log n)，无退化	平均 O(n log n)，最坏 O(n^2)
空间	O(n) 额外数组	O(log n) 递归栈
稳定	稳定	不稳定
工程选择	需要稳定性时（对象排序）	通用首选（基本类型排序）
实际例子	Java Arrays.sort(Object[])	Java Arrays.sort(int[])，C++ std::sort

快速排序为什么快？ 缓存友好（线性访问），原地排序，常数项小。归并排序为什么不可替代？ 永远 O(n log n)、稳定、适合外排序。

---

旅人笔记

归并是分治最规整的体现——稳定可预测，代价是吃内存。快速是工程上的王者——平均最快、原地排序，代价是输入敏感。需要稳定性用归并，内存吃紧用快排，数据量小用插入——没有银弹，只有最合适的权衡。

上一节：初级排序 —— 冒泡、选择、插入

→ 进入下一节：排序对比 —— 选型指南与速查表