什么时候你不该排序——选择、Top-K、中位数与流式算法

前八篇我们一直在"把排序做好"：

1. 《C语言常见排序算法详解》：比较排序的写法、复杂度、稳定性；
2. 《从会写到会用：C语言排序算法的实战选择与优化》：场景选型、qsort 泛型、快排优化；
3. 《突破 O(n log n)：C语言非比较排序实战》：计数/基数/桶排序；
4. 《数据放不进内存怎么办：C语言外部排序与海量数据排序实战》：分块、多路归并；
5. 《让多核一起干活：C语言并行排序与多线程实战》：pthread、OpenMP；
6. 《不只是数字：C语言字符串排序与后缀数组入门》：字符串比较与后缀数组；
7. 《TimSort：工业级排序的秘密》：run 识别、栈式归并、Galloping；
8. 《排序在数据库里到底怎么用》：ORDER BY、Sort-Merge Join、外部聚合。

但第 8 篇藏了一个反直觉的结论：数据库最快的排序，是不排序——ORDER BY ... LIMIT 用堆、有索引直接扫。这引出一个更根本的问题：

排序是 O(n log n)，但很多问题的答案根本不需要"全序"。我们是不是一直在为一个不需要的东西付 O(n log n) 的代价？

答案是：是的，而且很常见。本篇就来讲"排序的边界"——什么时候该用选择、Top-K、中位数、流式算法替代排序，把 O(n log n) 降到 O(n) 甚至 O(1) 空间。

一、核心洞察：全序是"过度信息"

排序的产物是全序：每个元素都知道自己排第几，任意两个元素都能比大小。

但很多问题只需要部分信息：

• “最大的 10 个” → 只需要 Top-10，不需要全序；
• “中位数” → 只需要中间那个，不需要两边有序；
• “第 k 小” → 只需要第 k 个，不需要全序；
• “去重” → 只需要相等性，不需要大小；
• “出现次数最多的” → 只需要频次，不需要顺序。

为部分信息付全序的代价，是浪费。这就是本篇的主线：按"需要多少信息"选算法，而不是无脑排序。

二、选择问题：第 k 小元素

2.1 排序解法（O(n log n)）

最直接：排完取 a[k-1]。简单，但做了大量无用功。

2.2 快速选择（Quickselect，平均 O(n)）

借用快排的 partition：每次划分后，若 pivot 正好在第 k 位，返回；否则只递归包含第 k 位的那一侧。

#include <stdlib.h>

static int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
    return i + 1;
}

/* 返回 a 中第 k 小（k 从 0 开始）的元素，会修改 a */
int quickselect(int a[], int lo, int hi, int k) {
    while (lo < hi) {
        int p = partition(a, lo, hi);
        if (p == k) return a[p];
        if (p < k) lo = p + 1;
        else       hi = p - 1;
    }
    return a[lo];
}

• 平均 O(n)，最坏 O(n²)（同快排，基准不佳时）；
• 与快排的区别：只递归一侧，所以期望复杂度是 n + n/2 + n/4 + … = O(n)；
• 最坏情况可用"三数取中"或随机化基准缓解（第 2 篇技巧直接复用）。

2.3 中位数：第 n/2 小

中位数是 k = n/2 的选择问题。Quickselect 平均 O(n) 求中位数，比排序 O(n log n) 快。这是"排序边界"最经典的例子。

2.4 最坏 O(n)：Median of Medians

理论上有最坏 O(n) 的选择算法（BFPRT），通过"五五分组的 medians 的中位数"选基准，保证划分均衡。但常数大，实践中 Quickselect + 随机化更常用。理论最优 ≠ 工程最优，这与第 2 篇、第 7 篇的结论一脉相承。

三、Top-K：只要最大的 K 个

3.1 排序解法（O(n log n)）

排完取前 K 个。K 很小时极度浪费。

3.2 大小为 K 的堆（O(n log K)）

维护一个大小为 K 的最小堆：遍历元素，若比堆顶大则替换堆顶并下沉。遍历完，堆里就是最大的 K 个。

/* 维护大小为 k 的最小堆，找最大的 k 个元素 */
static void siftDown(int heap[], int size, int i) {
    for (;;) {
        int l = 2 * i + 1, r = 2 * i + 2, m = i;
        if (l < size && heap[l] < heap[m]) m = l;
        if (r < size && heap[r] < heap[m]) m = r;
        if (m == i) break;
        int t = heap[i]; heap[i] = heap[m]; heap[m] = t;
        i = m;
    }
}

/* 返回实际写入 out 的元素个数（= min(k, n)） */
int topK Largest(int a[], int n, int k, int out[]) {
    if (k <= 0 || n <= 0) return 0;
    if (k > n) k = n;

    int *heap = (int *)malloc(k * sizeof(int));
    if (!heap) return 0;

    for (int i = 0; i < k; i++) heap[i] = a[i];
    for (int i = k / 2 - 1; i >= 0; i--) siftDown(heap, k, i);

    for (int i = k; i < n; i++) {
        if (a[i] > heap[0]) {
            heap[0] = a[i];
            siftDown(heap, k, 0);
        }
    }

    for (int i = 0; i < k; i++) out[i] = heap[i];
    free(heap);
    return k;
}

• 时间复杂度 O(n log k)，空间 O(k)；
• K 远小于 n 时，比排序 O(n log n) 快得多；
• 这就是第 8 篇"数据库 ORDER BY ... LIMIT 用 top-N 堆"的 C 实现；
• 若 K 接近 n，退化为 O(n log n)，此时不如直接排序。

3.3 快速选择 + 局部排序（O(n + K log K)）

先 Quickselect 找到第 K 大的元素，再对前 K 个排序。适合 K 较大但仍远小于 n 的场景，比堆的 O(n log K) 更优（当 K log K < n log K 时）。

选型口诀：K 很小用堆，K 中等用 Quickselect + 局部排序，K 接近 n 直接排序。

四、去重：只需要相等性

“去重"不需要大小，只需要"是否出现过”。排序去重是 O(n log n)，哈希去重是 O(n) 平均。

/* 简化示意：假设元素范围有限，用位图/计数去重 */
/* 通用场景用哈希表，这里不展开实现 */

这与第 3 篇"计数排序利用值域"同理：用哈希/位图把"相等性"问题从 O(n log n) 降到 O(n)。数据库的 DISTINCT 也是排序去重（Sort + Unique）和哈希去重（HashAggregate）二选一，与第 8 篇一致。

五、频次统计：排序 vs 哈希

“出现次数最多的元素”（众数）：

• 排序解法：排完扫描相邻相同元素计数，O(n log n)；
• 哈希解法：哈希表计数，O(n) 平均；
• 特殊场景：若元素范围小，计数数组 O(n + k)（第 3 篇计数排序思想）。

排序只在"顺便需要有序输出"时才划算。若只要频次，哈希更快。这是第 8 篇"排序 vs 哈希"决策表在单机算法层的翻版。

六、流式场景：数据来一次就没了

前八篇都假设"数据全在手里，可随机访问"。但日志流、传感器数据、网络包是流式的：来一个处理一个，不能回头。

流式场景下排序根本不可行（无法存储全量），但很多问题仍有 O(1) 空间解法：

6.1 流式中位数：双堆

维护一个最大堆（存较小一半）和一个最小堆（存较大一半），保持两堆大小差 ≤ 1。中位数在堆顶。

/* 双堆维护流式中位数（骨架示意） */
/* 最大堆存左半，最小堆存右半 */
/* 插入：与左堆顶比较决定入哪堆，再平衡大小 */
/* 中位数：奇数取元素多的堆顶，偶数取两堆顶平均 */

• 插入 O(log n)，查询 O(1)；
• 空间 O(n)，但只需存"一半 + 一半"，且支持在线查询；
• 这是流式算法的经典代表，排序做不到（排序需要全量）。

6.2 流式 Top-K：大小为 K 的堆

同第 3.2 节，堆天然适合流式：来一个比堆顶大就替换，O(log K) 每次，空间 O(K)。排序无法流式，堆可以。

6.3 流式去重/频次：哈希表 + 淘汰

哈希表计数，空间不够时用 Count-Min Sketch 等近似结构，用精度换空间。这是"排序边界"的极端：连 O(n) 空间都没有。

七、决策表：排序 vs 非排序

把本篇的讨论浓缩成一张表：

一句话总结：只有当"需要全序"或"有序输出可复用于下游"时，排序才不可替代；否则先问"我到底需要多少信息"。

八、工程启示：先问需求，再选算法

这九篇一路走来，其实在反复训练同一种思维：

1. 第 2 篇：按数据特征选排序算法；
2. 第 3 篇：用数据额外信息突破下界；
3. 第 4 篇：把矛盾从比较次数转向 I/O；
4. 第 5 篇：把矛盾转向多核；
5. 第 7 篇：真实数据特征比理论复杂度重要；
6. 第 8 篇：数据库按代价在排序/哈希/索引间选；
7. 本篇：先问"需要多少信息"，再决定要不要排序。

这是同一条主线的延伸：算法选择由问题结构决定，而不是由"我会什么算法"决定。会写快排不等于该用快排，会排序不等于该排序。

九、常见坑与检查清单

1. Quickselect 最坏 O(n²)：必须随机化基准或三数取中，否则有序输入退化。
2. Top-K 堆方向搞反：找最大 K 个用最小堆，找最小 K 个用最大堆，反了结果全错。
3. K 接近 n 还用堆：O(n log K) ≈ O(n log n)，不如直接排序。
4. 流式场景硬排序：数据来一次就没了，排序不可行，必须用堆/哈希等在线结构。
5. 去重忽略稳定性：哈希去重不保序，若需保留首次出现顺序，要额外记录下标。
6. 中位数双堆大小失衡：插入后必须平衡两堆大小差 ≤ 1，否则中位数取错。
7. Quickselect 修改原数组：若不希望修改，先拷贝；或改用不修改的选择算法。
8. 近似算法的误差：Count-Min Sketch 等有误差上界，业务要能接受。

十、小结与系列脉络

本篇是系列的"反向收束"：前八篇教你怎么排序，本篇教你什么时候不排序。

• 第 1 篇的堆：变成 Top-K 和流式中位数的核心结构；
• 第 1 篇的快排 partition：变成 Quickselect 的基础；
• 第 2 篇的随机化基准：变成 Quickselect 防退化的手段；
• 第 3 篇的"利用数据信息"：变成"用哈希/位图替代排序"；
• 第 8 篇的数据库 top-N：变成 C 语言的 Top-K 堆实现。

一句话心法：排序是手段，不是目的。先问"我需要全序吗"，再决定排不排。