元数据卡
| 属性 | 值 |
|---|---|
| 难度 | 应用 |
| 前置 | 第 9 章（基础排序 + 高级排序） |
| 关键词 | 排序对比 · 时间复杂度 · 空间复杂度 · 稳定性 · 选型 · 决策指南 |
| 预计阅读 | 15 分钟 |
| 代码行 | ~10 行（演示示例） |
你的进度
你手头已经有一整排排序武器：冒泡、选择、插入三个 O(n^2) 的基础款，归并、快速两个 O(n log n) 的高级款。现在的问题是：面对真实数据，你到底该选哪一个？
这不是理论问题。Java 的 Arrays.sort() 对基本类型用快速排序（双轴快排），对对象用归并排序（TimSort）——两个不同的选择，反映的是稳定性 vs 速度的权衡。C++ 的 std::sort 用 Introsort（快排 + 堆排混合体）。你需要在代码中做出同样的判断。
你的任务
读完这一页，你应当能：
- 根据数据规模、稳定性要求、内存限制，快速选出合适的排序算法
- 说出至少两个"数据特征影响排序选择"的真实案例
- 理解为什么没有"万能排序"
完整速查表
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 | 特点 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(1) | 稳定 | 常数大，几乎不用 |
| 选择排序 | O(n^2) | O(n^2) | O(1) | 不稳 | 交换最少，但无实际优势 |
| 插入排序 | O(n^2) | O(n^2) | O(1) | 稳定 | 几乎有序时 O(n)，TimSort 基石 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 稳定可预测，吃空间 |
| 快速排序 | O(n log n) | O(n^2) | O(log n) | 不稳 | 平均最快，缓存友好 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳 | 原地稳定时间，常数大 |
| 计数排序 | O(n + k) | O(n + k) | O(k) | 稳定 | 只适用于小范围整数 |
| 基数排序 | O(d(n + b)) | O(d(n + b)) | O(n + b) | 稳定 | 适用于整数/定长字符串 |
| 桶排序 | O(n + m) | O(n^2) | O(n + m) | 看桶内 | 适用于均匀分布数据 |
k = 数据范围大小，d = 数字位数，b = 进制基数，m = 桶数。
选型决策流程
你可以用一个简单的决策树来判断：
需要稳定性？
├── 是 → 数据是对象，需要保持原有顺序
│ ├── 数据量小（< 100） → 插入排序
│ └── 数据量大 → 归并排序（或 TimSort）
│
└── 否 → 只关心值，不关心原始位置
├── 数据量小（< 100） → 插入排序（简单好写）
├── 数据量大，内存充裕 → 快速排序
├── 数据量大，内存吃紧 → 堆排序
└── 数据范围小（如 0~1000） → 计数排序真实工程中的选择
| 场景 | 实际选择 | 原因 |
|---|---|---|
| Java 基本类型排序 | Arrays.sort(int[]) → 双轴快排 | 基本类型无需稳定性 |
| Java 对象排序 | Arrays.sort(Object[]) → TimSort | 对象排序需要稳定性 |
| C++ 默认排序 | std::sort → Introsort | 防退化到 O(n^2) |
| Python 排序 | list.sort() → TimSort | 自适应、稳定 |
| 数据库 ORDER BY | 归并排序变种 | 稳定性 + 外排序 |
| GPU 排序 | 基数排序 / 双调排序 | 适合并行化 |
深入：为什么没有万能排序
每种排序都有自己的甜蜜区。看几个例子：
当数据几乎有序时
java
// 数组基本有序：[1, 2, 3, 5, 4, 6, 7, 8]
int[] nearlySorted = {1, 2, 3, 5, 4, 6, 7, 8};插入排序在这里 O(n) 搞定——内层 while 几乎不执行。快速排序反而有额外的分区开销。这就是为什么 TimSort 在检测到已有有序 run 时退化成插入排序。
当数据范围很小时
java
// 成绩统计：只有 0~100 分，但考生有 10 万人
int n = 100000;
int[] scores = new int[n]; // 范围 0~100这里计数排序 O(n + k) 比 O(n log n) 快几个数量级。如果硬要用快速排序，你就是拿牛刀杀鸡。
当内存极度受限时
嵌入式设备可能只有几 KB 可用内存。归并排序的 O(n) 额外空间不可接受。快速排序的 O(log n) 递归栈也可能超标。堆排序的 O(1) 额外空间是唯一选择。
几种不常见的排序（了解即可）
| 算法 | 一句话 |
|---|---|
| 希尔排序 | 插入排序的跨越式进化，第一个突破 O(n^2) 的排序 |
| Introsort | 快排 + 堆排 + 插入的混合体，递归深度超过 log n 时切到堆排 |
| TimSort | 归并 + 插入的混合体，检测有序 run 合并，Python / Java 对象排序的默认选择 |
| 双调排序 | 并行排序，GPU 常用 |
旅人笔记
没有最好的排序，只有最适合当前场景的排序。选型的关键是看清三件事：数据规模、数据特征（是否几乎有序/范围大小）、约束条件（稳定性/内存）。排序是手段，不是目的——高效的搜索才是你最终想要的。
上一节：高级排序 —— 归并、快速与分治