排序算法应用 · 融合风（象牙 + Obsidian 入口）

速查

选排序算法要综合数据规模、是否有序、稳定性、空间：小数据用直接插入；大数据平均最快用快排；要求稳定用归并；要求最坏 $O(n\log n)$ 用堆 / 归并；取前 $k$ 大用小根堆 $O(n\log k)$；关键字范围小用计数 / 基数。

一、根据数据特征选择排序算法 ▾

数据特征	推荐算法	原因
数据量小 $(n\leq50)$	直接插入	常数因子小，简单高效
数据量大	快速 / 归并 / 堆	$O(n\log n)$
基本有序	直接插入	最好 $O(n)$
逆序程度大	快速 / 归并 / 堆	不依赖初始序列
关键字范围小	计数 / 基数排序	$O(n)$ 或 $O(d\cdot n)$

二、Top-K 问题的排序解法 ▾

问题：从 $n$ 个元素中找出最大（或最小）的 $k$ 个。

方法	时间	适用场景
排序后取前 $k$ 个	$O(n\log n)$	需要完整排序
建堆取 $k$ 次堆顶	$O(n+k\log n)$	$k$ 较小
快速选择算法	$O(n)$ 平均	只需要第 $k$ 大
小根堆维护 $k$ 个元素	$O(n\log k)$	$k$ 较小，流式数据

建堆取 Top-K取前 $k$ 个最大用小根堆（堆顶是最小，方便淘汰小值）；取前 $k$ 个最小用大根堆。

三、排序算法的工程实现 ▾

实际排序库（C++ STL sort、Java Arrays.sort）采用混合策略：

Introsort：快排 + 堆排 + 插入排序
- 小规模子数组用插入排序
- 递归深度超限切换为堆排序
- 正常情况用快速排序
TimSort（Python / Java）：归并 + 插入
- 利用数据中已有的有序段（run）
- 小规模用插入排序

四、外部排序的应用 ▾

数据量超过内存时用外部排序：

多路归并：数据分段排序后写入磁盘，再多路归并
关键：减少磁盘 I/O 次数
败者树优化多路归并的选择过程

关键性质 ▾

应用场景	最优策略	时间
Top-K（$k$ 小）	堆	$O(n\log k)$
Top-K（$k$ 大）	排序取前 $k$	$O(n\log n)$
第 $k$ 大	快速选择	$O(n)$ 平均
中位数	快速选择	$O(n)$ 平均
数据去重	排序后扫描	$O(n\log n)$
区间合并	排序后扫描	$O(n\log n)$

易错点 ▾

注意

Top-K 用堆时，取最大 $k$ 个用小根堆（不是大根堆）
快速选择平均 $O(n)$ 但最坏 $O(n^2)$
排序后查找用二分 $O(\log n)$，但排序本身 $O(n\log n)$，需权衡
外部排序路数增加 → 趟数减少，但每趟比较增多

核心结论 ▾

必背选算法要综合考虑规模、有序性、稳定性、空间；Top-K 优先堆 $O(n\log k)$；工程常用混合排序（Introsort、TimSort）；排序是去重、查找、区间问题的基础；外部排序以减少 I/O 为核心。

记忆卡片 ▾

如何找前 $k$ 个最大？

建小根堆，遍历剩余元素替换堆顶，$O(n\log k)$。

为何取前 $k$ 大用小根堆？

堆顶是当前 $k$ 个中最小的，方便和新元素比较淘汰。

要求稳定且 $O(n\log n)$ 选什么？

归并排序。

数据基本有序选什么？

直接插入排序，最好 $O(n)$。

交互动画 · Top-K 最小堆（求前 3 大） ▾

点击「下一个」逐个插入，维护容量为 3 的小根堆（保留最大的 3 个）

相关知识点

sorting-algorithm-comparison quick-sort heap-sort

↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。