排序不只是排序：Top-K、找中位数、外部排序，一个思想打通三类难题

很多人以为排序只用来"把数组排整齐"。其实，排序是解决一大类"选择/统计"问题的通用钥匙。学会 B1 的排序直觉后，下面三类经典问题都会变得顺理成章。

问题一：Top-K（找前 K 大）。最朴素的做法是把全部 n 个排好序再取前 K 个，耗时 O(n log n)。但这其实"排多了"——我们只要前 K，不需要全序。更聪明的是用堆（缺口 B4/B6）维护大小为 K 的最小堆，只需 O(n log K)；或在随机化快速选择的平均 O(n) 内搞定。排序给了我们"基准解法"，而后续算法是它对问题的裁剪。

问题二：中位数 / 第 k 小（选择问题）。CLRS 第 9 章专门讲期望线性时间选择：类似快排的分区，但只递归进包含第 k 小的那一侧，平均 O(n)，最坏仍 O(n²)（最坏情况有更精巧的"中位数的中位数"算法做到严格 O(n)）。这本质上是"排序思想"在"我不需要全序"时的精准特化。

问题三：外部排序（数据大到内存装不下）。当数据以 TB 计，无法一次读入内存，就用多路归并：先分块在内存里各自排序（内部排序，正是今天学的那些），再像归并排序一样把多个有序块流式合并。数据库、大数据框架（MapReduce 的 shuffle 阶段）都靠它。这里"先局部排序、再归并"的范式，正是 B2 归并排序的工程放大版。

一条主线：排序 → 选择 → 外部处理，是"全序 → 部分序 → 分布式全序"的能力递进。今天先把 B1 的三种基础排序学扎实，后面 B2 归并、B4 堆、B6 选择会一环扣一环地展开这条主线。

关联推荐

• 哈希表：为什么 Redis、Python 字典都靠它"秒查" — 另一个"基础结构打通难题"的例子
• 从冒泡到快排 — 排序家族的总览入口
• 算法与问题求解入门 — 建立"算法是解决问题的步骤"这一总认知