【果实的馈赠】排序算法全景：为什么你只需要记住3种

路飞吃下橡皮果实并不是因为它最强——而是因为它和他最契合。排序算法也一样：不是要记住所有变体，而是理解三种核心思想，根据场景选最合适的那个。

排序算法有几十种，但工程中真正用到的核心思想只有三类：分治（归并、快排）、堆（选择的极致）、非比较（计数、基数）。

一、比较排序的下界

任何基于「两两比较」的排序算法，最坏情况下都需要 Ω(n log n) 次比较。

原因：n 个元素的全排列有 n! 种，每次比较最多把可能性减半，所以至少需要 log₂(n!) ≈ n log n 次比较才能唯一确定排列顺序。

这意味着归并、快排、堆排序已经是比较排序的理论极限，冒泡和插入的 O(n²) 只适合教学或近乎有序的小数据集。

二、归并排序

分治思想：把数组对半拆分，分别排好序，再合并两个有序数组。

void mergeSort(int[] arr, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

void merge(int[] arr, int l, int mid, int r) {
    int[] temp = Arrays.copyOfRange(arr, l, r + 1);
    int i = 0, j = mid - l + 1;            // 两个子数组的起点（相对于 temp）
    for (int k = l; k <= r; k++) {
        if      (i > mid - l)               arr[k] = temp[j++];
        else if (j > r - l)                 arr[k] = temp[i++];
        else if (temp[i] <= temp[j])        arr[k] = temp[i++];
        else                                arr[k] = temp[j++];
    }
}

指标	值
时间	O(n log n) 稳定，最好最坏都一样
空间	O(n)，需要辅助数组
稳定性	稳定（相等元素相对顺序不变）
适用场景	外部排序（数据量超过内存）、链表排序、需要稳定性的场景

归并的精髓：合并两个有序数组是 O(n) 的，分治让这个操作只需做 log n 层，总代价 O(n log n)。

链表归并排序（LeetCode 148）：归并比快排更适合链表，因为链表不支持随机访问，而归并只需要顺序扫描。

ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode mid = getMid(head);
    ListNode right = mid.next;
    mid.next = null;                        // 断开两半
    return merge(sortList(head), sortList(right));
}

ListNode getMid(ListNode head) {            // 快慢指针找中点
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    return slow;
}

ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
        else                  { cur.next = l2; l2 = l2.next; }
        cur = cur.next;
    }
    cur.next = l1 != null ? l1 : l2;
    return dummy.next;
}

三、快速排序

分治思想：选一个基准（pivot），把小于 pivot 的放左边，大于的放右边，递归排两侧。

void quickSort(int[] arr, int l, int r) {
    if (l >= r) return;
    int p = partition(arr, l, r);
    quickSort(arr, l, p - 1);
    quickSort(arr, p + 1, r);
}

int partition(int[] arr, int l, int r) {
    int pivot = arr[r];                     // 选最右元素为 pivot
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (arr[j] <= pivot) {
            swap(arr, ++i, j);
        }
    }
    swap(arr, i + 1, r);
    return i + 1;
}

指标	值
时间	平均 O(n log n)，最坏 O(n²)（已排序数组 + 固定选 pivot）
空间	O(log n) 递归栈，原地排序
稳定性	不稳定
适用场景	内存排序的首选，常数因子小，实践中最快

两个优化：

随机化 pivot：每次随机选 pivot，把最坏情况的概率降到可忽略。

int randomIndex = l + (int)(Math.random() * (r - l + 1));
swap(arr, randomIndex, r);

三路快排（处理大量重复元素）：把数组分成 <pivot、==pivot、>pivot 三段，==pivot 的部分不再递归。

void quickSort3(int[] arr, int l, int r) {
    if (l >= r) return;
    int pivot = arr[l + (int)(Math.random() * (r - l + 1))];
    int lt = l, gt = r, i = l;
    while (i <= gt) {
        if      (arr[i] < pivot) swap(arr, lt++, i++);
        else if (arr[i] > pivot) swap(arr, i, gt--);
        else                     i++;
    }
    quickSort3(arr, l, lt - 1);
    quickSort3(arr, gt + 1, r);
}

LeetCode 215 · 数组中第 K 大的元素：快排的 partition 思想直接应用——每次 partition 后 pivot 落在正确位置，如果 pivot 下标 == k-1 就找到了，否则只需递归一侧，平均 O(n)：

public int findKthLargest(int[] nums, int k) {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

int quickSelect(int[] arr, int l, int r, int k) {
    if (l == r) return arr[l];
    int p = partition(arr, l, r);
    if      (p == k) return arr[p];
    else if (p < k)  return quickSelect(arr, p + 1, r, k);
    else             return quickSelect(arr, l, p - 1, k);
}

四、堆排序

利用堆的性质：最大堆的堆顶永远是最大元素。建堆后反复取出堆顶，实现原地排序。

void heapSort(int[] arr) {
    int n = arr.length;
    // 1. 建堆（从最后一个非叶子节点开始向下堆化）
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    // 2. 反复把堆顶（最大值）换到末尾，缩小堆
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

void heapify(int[] arr, int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { swap(arr, i, largest); heapify(arr, n, largest); }
}

指标	值
时间	O(n log n) 稳定，最好最坏都一样
空间	O(1) 原地，无额外空间
稳定性	不稳定
适用场景	内存严格受限、Top-K 问题

五、非比较排序

突破 O(n log n) 下界的方法：不做两两比较，利用数据分布的额外信息。

计数排序

数据范围有限（如 0~k），对每个值计数，再还原：

void countingSort(int[] arr, int k) {
    int[] count = new int[k + 1];
    for (int x : arr) count[x]++;
    int idx = 0;
    for (int i = 0; i <= k; i++)
        while (count[i]-- > 0) arr[idx++] = i;
}
// 时间 O(n + k)，空间 O(k)

基数排序

对多位数按位排序，每位做一次计数排序：

void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10)
        countByDigit(arr, exp);
}
// 时间 O(d(n+k))，d 为位数，k 为基数（通常 10）

六、三种核心思想的选择矩阵

场景	推荐	原因
通用内存排序	快排（随机化）	常数因子最小，实践最快
需要稳定性	归并	唯一稳定的 O(n log n)
链表排序	归并	链表不支持随机访问
外部排序（数据超内存）	归并	顺序读写，适合磁盘
Top-K / 实时中位数	堆	O(n log k) 的流式处理
整数范围有限	计数/基数	突破 O(n log n)
已接近有序	插入	O(n) ~ O(n²)，小数据常数最小

Java 的 Arrays.sort() 对基本类型用双轴快排（Dual-Pivot Quicksort），对对象用 TimSort（归并 + 插入的混合，稳定）。Python 的 sorted() 也是 TimSort。

路飞选择橡皮果实，不是因为它是最强的恶魔果实，而是因为它和他的战斗风格天然契合。排序算法的选择也一样：理解三种核心，遇到具体问题再选最合适的那个，而不是记住所有变体。

风车村系列完结。下一站：谢尔兹镇 · 编程语言基础——三刀流初现