8.5　工程中如何选排序

学习目标：学完本节，你能

说清内省排序（Introsort）是怎么把三种算法拼起来的；
在具体需求下快速选出正确的排序方案；
说清 Array.Sort / List<T>.Sort() / LINQ OrderBy 三者的差异与取舍。

先修：8.1–8.4（全部排序算法）。 固定术语：内省排序、混合排序、决策表。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、回想一下：三种 $O(n \log n)$ 算法各有什么毛病

算法	快吗	最坏情况	额外空间	稳定
快速排序	✅ 最快	❌ $O(n^2)$	✅ $O(\log n)$	❌
归并排序	中等	✅ $O(n \log n)$	❌ $O(n)$	✅
堆排序	❌ 较慢	✅ $O(n \log n)$	✅ $O(1)$	❌

每种算法都有明显的短板。那能不能"取长补短"？

答案就是本章的主角：内省排序（Introsort）。

它的思路是：用快排打头（因为快），但加上两个"保险丝" —— 递归太深就切堆排序，数组太小就切插入排序。

二、内省排序：三个算法的组合

.NET 的 Array.Sort、List<T>.Sort()、C++ 的 std::sort 用的都是它。

三个组成部分：

阶段	用什么	为什么
主体	快速排序（三数取中 + 三路分区）	平均最快
深度保险	递归超过 $2\log_2 n$ 层 → 切换堆排序	彻底杜绝 $O(n^2)$ 和栈溢出
小数组	规模小于约 16 → 切换插入排序	减少递归开销

流程图：

              开始排序
                 │
                 ▼
        ┌────────────────┐
        │ 数组规模 < 16？  │──是──> 插入排序 ──> 返回
        └────────────────┘
                 │否
                 ▼
        ┌────────────────┐
        │ 递归深度超标？    │──是──> 堆排序 ──> 返回
        └────────────────┘
                 │否
                 ▼
            三路分区 + 递归

这三条"保险丝"各自解决一个问题：

堆排序兜底 → 解决"最坏情况退化"（8.2 节实测的 376 倍退化，以及栈溢出风险）
插入排序收尾 → 解决"小数组上递归开销过大"
三路分区 → 解决"大量重复元素导致退化"（8.4 节实测的 447 倍差距里，有一部分就是这个原因）

这就是"混合排序"（Hybrid Sort）的核心思想：

没有哪个算法在所有场景下都是最优的，那就让每个算法只负责它最擅长的那一段。

这个思路在工程里到处都是：数据库的查询优化器会"根据数据量选择不同的连接算法"，HTTP 服务器会"根据请求大小选择不同的解析路径"，本质都是"同一件事，按场景切换实现"。

三、.NET 提供了哪些排序 API

var data = new[] { 5, 2, 8, 1, 9, 3 };

// 1. Array.Sort —— 原地排序数组
Array.Sort(data);                          // 返回 void，直接改原数组

// 2. List<T>.Sort —— 原地排序列表
var list = data.ToList();
list.Sort();                               // 返回 void

// 3. LINQ OrderBy —— 返回新序列，不改原数据
var sorted = data.OrderBy(x => x).ToArray();
// data 仍然是 [5, 2, 8, 1, 9, 3]

// 4. 多关键字
var result = words.OrderBy(w => w.Length).ThenBy(w => w).ToArray();

关键差异一览：

API	是否原地	稳定	返回类型	适用
`Array.Sort`	✅	❌	`void`	数组，性能优先
`List<T>.Sort()`	✅	❌	`void`	列表，性能优先
`OrderBy` / `ThenBy`	❌（复制）	✅	`IOrderedEnumerable`	需要稳定或链式操作
`Array.Sort(keys, items)`	✅	❌	`void`	按键排另一个数组（很少用但很有用）

四、实测：稳定性差异

这是个非常实际的坑。

  === 实验二：Array.Sort 不稳定，OrderBy 稳定 ===

  2,000 条记录，优先级只有 1 和 2，各占一半（大量重复）。
  原始顺序: #0000(1) #0001(2) #0002(1) #0003(2) ...
  （同优先级的记录，原始序号是递增的）

  Array.Sort 稳定性: 不稳定 ✗
    前 10 个结果: #0000 #0814 #1590 #0816 #0818 #1588 #0820 #0822 #1586 #0824
  OrderBy    稳定性: 稳定 ✓
    前 10 个结果: #0000 #0002 #0004 #0006 #0008 #0010 #0012 #0014 #0016 #0018

看这两个结果：

OrderBy：#0000 #0002 #0004 #0006 ... —— 同优先级的记录按原始序号严格递增 ✓
Array.Sort：#0000 #0814 #1590 #0816 ... —— 完全打乱了 ✗

这个差异会导致什么后果？

假设你有一个商品列表，要"按销量排序，销量相同的保持原有顺序"。

用 OrderBy：正确

用 Array.Sort：销量相同的商品顺序每次都不同，用户刷新页面会看到列表"乱跳"

而且更麻烦的是：这个 bug 在小数据量下不会出现。

我第一版测试用了 6 个元素，结果 Array.Sort 显示"稳定 ✓" —— 因为它在小数组上会退化成插入排序，而插入排序是稳定的。

换成 2000 个元素，它的不稳定才暴露出来。

"在小数据上碰巧正确"是最危险的一类 bug —— 测试环境通过，生产环境出错。

五、实测：性能对比

=== 实验三：几种做法的实际耗时（n = 2,000,000）===

  Array.Sort          :     96.4 ms
  List<T>.Sort        :     97.9 ms
  OrderBy().ToArray() :    297.8 ms   （稳定，但慢 3.1 倍）
  手写快排            :    160.6 ms   （慢 1.7 倍）

三个结论：

Array.Sort 和 List<T>.Sort() 几乎一样快 —— 它们内部是同一套实现。
OrderBy 慢 3.1 倍 —— 这是稳定性的代价。它要分配新数组、做归并式的合并。
手写快排慢 1.7 倍 —— 即使我已经用了随机化基准。

第 3 点最值得记住：

我写的快排已经是"教科书正确"的实现了 —— 随机化基准、Lomuto 分区、正确的递归边界。但它还是比官方实现慢 70%。

官方实现多做了什么？

三路分区（处理重复元素）

小数组切换到插入排序

深度监控 + 堆排序兜底

用 Span<T> 避免边界检查

内联热点代码、减少内存访问

针对特定类型（如 int）的特殊优化

结论：不要自己写排序。 这不是"造轮子"的问题，而是这个轮子已经被优化到了人工难以企及的程度。

六、实测：小数组上官方实现依然更快

教科书说"小数组上插入排序更快，所以内省排序会切换过去"。我实测了一下：

           n |         插入排序 |   Array.Sort | 谁更快
--------------------------------------------------------
          8 |      0.31 ms |      0.12 ms | Array.Sort 快 2.53 倍
         16 |      0.50 ms |      0.19 ms | Array.Sort 快 2.56 倍
         32 |      1.03 ms |      0.55 ms | Array.Sort 快 1.87 倍
         64 |      3.46 ms |      1.00 ms | Array.Sort 快 3.47 倍
        128 |      3.88 ms |      2.25 ms | Array.Sort 快 1.72 倍
      1,000 |     77.30 ms |     23.70 ms | Array.Sort 快 3.26 倍

Array.Sort 在【所有规模】上都比我们手写的插入排序快 2～3 倍。

这和教科书说法矛盾吗？不矛盾 —— 因为：

Array.Sort 内部确实用了插入排序，只是它的实现比教科书版本优化得多（用 Span<T>、减少边界检查、更好的内存访问模式）。
我们的测量包含"克隆数组"的开销，而克隆本身也要时间。

这个结果再次印证了第五节的主题："理解算法"和"写出生产级实现"是两件事。

学到的东西不是白学的 —— 它让你能：

判断某段代码的复杂度瓶颈在哪

理解为什么某个 API 慢、慢在哪个环节

在数据结构选型时做出正确决定

知道"什么时候该用哪个算法"，而不是"怎么实现它"

七、决策流程：我该用哪个？

这是本节最实用的一张表。

第一步：能用现成 API 吗？

                  要排序
                    │
        ┌───────────┴───────────┐
        │                       │
   需要【稳定】？              不需要
        │                       │
        ▼                       ▼
   OrderBy / ThenBy        Array.Sort
   （或加决胜关键字）        List<T>.Sort()

99% 的情况到这里就结束了。

第二步：特殊情况才需要考虑手写

情况	方案	参考
要排的数据值域很小（如状态码、评分）	计数排序	8.4 节（实测快 447 倍）
要排大量 32 位整数	基数排序	8.4 节
只要前 K 个（K 远小于 n）	大小为 K 的堆	8.3 节
数据大到内存放不下	外部归并排序	8.1 节
数据几乎有序	插入排序（或直接 `Array.Sort`）	8.1 节
需要并发排序	`Array.Sort` + 分块并行	超出本书范围

第三步：完整决策表

需求特征	推荐	复杂度	理由
通用排序，无特殊要求	`Array.Sort`	$O(n \log n)$	内省排序，快且无最坏情况
需要稳定	`OrderBy`	$O(n \log n)$	归并类实现，慢 3 倍但正确
需要稳定 + 性能	`Array.Sort` + 加决胜关键字	$O(n \log n)$	用"原始下标"当第二关键字
值域 $k = O(n)$	计数排序	$O(n+k)$	不比较，直接定位
大量整数，值域大	基数排序	$O(d \cdot n)$	按位拆分
Top-K（K 小）	小顶堆	$O(n \log k)$	只维护 K 个候选
数据在磁盘上	外部归并	$O(n \log n)$ + I/O	顺序读写磁盘
元素是大对象，移动代价高	选择排序（如果 n 小）	$O(n^2)$ 比较 / $O(n)$ 移动	7.1 节

八、一个重要的实践：用决胜关键字实现稳定

"需要稳定但想用 Array.Sort 的性能" —— 这是个常见的两难。

解法：在比较函数里显式加一个"原始下标"作为决胜条件。

// 目标：按价格排序，价格相同的保持原有顺序
var items = GetItems();

// 方法 1：用 OrderBy（简单，但慢）
var sorted1 = items.OrderBy(x => x.Price).ToArray();

// 方法 2：带上下标，用 Array.Sort（快，而且稳定）
var indexed = items.Select((item, index) => (item, index)).ToArray();
Array.Sort(indexed, (a, b) =>
{
    int cmp = a.item.Price.CompareTo(b.item.Price);
    return cmp != 0 ? cmp : a.index.CompareTo(b.index);   // <- 决胜条件
});
var sorted2 = indexed.Select(x => x.item).ToArray();

实测两者结果一致，但方法 2 明显更快（因为走的是内省排序，而且不需要分配临时数组）。

这个技巧的通用性很强：

任何"排序不稳定"的问题，都可以通过"给元素编号 + 把编号作为最后一级比较关键字"来解决。

代价是要多存一个下标、多一次比较。但这是确定性正确，不依赖任何实现细节。

九、练习

练习 8.5.1（选择）下面六个场景，你会用什么排序？说明理由。 (a) 一个电商网站的商品列表，按价格排序，价格相同的保持上架顺序 (b) 统计 1000 万条日志中出现最多的 10 个 IP (c) 排序 1000 万个 32 位整数，用于数据分析 (d) 一个实时系统要给 100 个传感器读数排序，每 10 毫秒一次 (e) 排一个 50 GB 的日志文件（内存只有 8 GB） (f) 按用户评分（0.0~5.0，一位小数）排序 100 万条评论

练习 8.5.2（判断）判断对错并说明理由： (a) Array.Sort 比冒泡排序快，因为它用的是更好的算法。 (b) 内省排序是"三种排序算法的组合"。 (c) 既然 Array.Sort 已经很快了，那学习排序算法就没有意义了。

练习 8.5.3（推理）你要排序一个包含 100 万个元素的 List<Order>，每个 Order 有 20 个字段，大小约 200 字节。 (a) 直接排序这个列表，会移动多少数据量？ (b) 如果改成"排序下标数组"，会有什么不同？ (c) 这个技巧什么时候特别有用？

练习 8.5.4（工程判断）一个服务用 Array.Sort 排序用户数据，偶尔会有用户反馈"列表顺序变了"。 (a) 可能是什么原因？ (b) 怎么验证你的猜测？ (c) 怎么修复？

练习 8.5.5（挑战·设计）设计一个"混合排序策略"，用于处理完全不可预测的输入（可能有序、可能大量重复、可能随机）： (a) 你会组合哪些算法？ (b) 什么条件下切换？ (c) 怎么验证它在各种输入下都不会退化？

十、练习答案

8.5.1

场景	方案	理由
(a)	`OrderBy`（或 `Array.Sort` + 决胜关键字）	需要稳定。价格相同的要按上架顺序。
(b)	哈希表计数 + 小顶堆	不是完整排序。用哈希表统计每个 IP 的次数，再用大小为 10 的小顶堆取 Top-10。
(c)	`Array.Sort`，或基数排序	1000 万个整数，`Array.Sort` 已经足够快。如果对性能极度敏感可以试基数排序，但要注意它要分配临时数组。
(d)	插入排序	$n = 100$ 非常小，而且每 10 毫秒一次意味着延迟敏感 —— 插入排序没有递归、没有内存分配，可预测。
(e)	外部归并排序	50 GB > 8 GB 内存。切块排序后多路归并。
(f)	计数排序	评分只有 51 种可能（0.0 到 5.0，每位小数 = 51 个值）。转成整数（乘 10）后值域 $k = 51 \ll n$，完美适配。

(d) 和 (f) 是最容易被忽略的两个：

(d) 的关键是"$n$ 很小 + 延迟敏感" —— 这时候渐进复杂度根本不是重点，常数和可预测性才是。

(f) 的关键是"值域很小" —— 这是计数排序的完美场景，但很多人看到"评分"会习惯性地用 OrderBy。

8.5.2

(a) 对，但说法不够准确。 更准确的说法是：

Array.Sort 快，是因为它不仅用了渐进复杂度更优的算法（$O(n \log n)$ vs $O(n^2)$），还做了大量常数级优化。

而且在数据几乎有序时，冒泡排序（带优化）可能是 $O(n)$，反而比 Array.Sort 的 $O(n \log n)$ 更快（8.1 节实测过类似的现象）。
(b) 对。 内省排序 = 快速排序（主体）+ 堆排序（兜底）+ 插入排序（小数组）。

"内省"（Introspective）这个名字的含义是"会自我检查" —— 它会监控自己的递归深度，发现"快排要退化了"就主动切换。

这是它区别于普通混合排序的地方：大多数混合排序只是"按规模切换"，而内省排序还会"按运行时的表现切换"。
(c) 错，而且这是本章最想纠正的误解。
学习排序算法的价值不在于"自己实现它们"，而在于：
1. 判断力：知道某段代码慢在哪，是 "$O(n^2)$ 了" 还是 "常数太大"
2. 选型能力：知道什么时候该用 OrderBy（稳定）、什么时候该用计数排序（值域小）
3. 理解边界：知道 Array.Sort 不稳定、知道它的最坏情况有保障（而朴素快排没有）
4. 迁移能力：排序里的思想（分治、堆、稳定性、下界）在别的问题里反复出现
"会调 API"和"知道该调哪个 API、以及为什么"是两回事。

8.5.3

(a) 每个 Order 是 200 字节，排序过程中元素会被交换多次。

快排平均每个元素参与约 $O(\log n)$ 次交换，每次交换涉及两个 200 字节对象的复制（如果 Order 是结构体）或两个引用的交换（如果是类）。

分两种情况：

如果 Order 是 class（引用类型）：List<Order> 里存的是引用（8 字节），交换只是交换引用 —— 代价很小。
如果 Order 是 struct（值类型）：排序要直接搬移 200 字节的结构体 —— 代价巨大。

假设是 struct：

$$\text{总移动量} \approx 10^6 \times 20 \text{ 次交换} \times 200 \text{ 字节} = 4 \text{ GB}$$

4 GB 的内存搬运。

(b) 改成"排序下标数组"：

var indices = Enumerable.Range(0, orders.Count).ToArray();
Array.Sort(indices, (i, j) => orders[i].Price.CompareTo(orders[j].Price));
// 之后用 indices 去访问 orders

这时排序过程中移动的是 int（4 字节），而不是 200 字节的结构体。

$$\text{总移动量} \approx 10^6 \times 20 \times 4 \text{ 字节} = 80 \text{ MB}$$

从 4 GB 降到 80 MB —— 50 倍。

(c) 什么时候特别有用？

元素很大（结构体、或包含大量字段）—— 移动代价高
不希望修改原数组（排序下标数组是"间接排序"，原数组不动）
排序关键字多于一个 —— 可以同时维护多个下标数组（按价格排一个、按时间排一个）
需要频繁按不同关键字排序 —— 排一遍下标数组比排数据本身便宜得多

代价：每次访问都要多一次间接寻址（orders[indices[i]]），破坏了缓存局部性。

所以这是个权衡：如果元素很小（比如 int），直接排序更快；如果元素很大，间接排序更划算。

8.5.4

(a) 最可能的原因是"Array.Sort 不稳定，而业务逻辑隐含地依赖了稳定性"。

具体场景：代码里写的是

Array.Sort(users, (a, b) => a.Score.CompareTo(b.Score));

但需求其实是"按分数排序，同分的保持原有顺序"。

同分的用户每次排序后顺序都可能不同 —— 用户就会看到"列表跳来跳去"。

（次要可能）：多线程并发修改了列表，或者数据本身在两次排序之间变了。

(b) 验证方法：

构造一个确定性的复现用例：

// 造 2000 条数据，分数只有两个值，各占一半，带原始序号
var users = Enumerable.Range(0, 2000)
    .Select(i => new User { Id = i, Score = i % 2 })
    .ToList();

Array.Sort(users.ToArray(), (a, b) => a.Score.CompareTo(b.Score));

// 检查：同分的用户，Id 是否仍然递增？

如果 Id 不是递增的，就证实了不稳定。

注意数据量要够大（比如 2000 条）。小数据量下 Array.Sort 会退化成插入排序（稳定的），测不出来。本节实验二就踩过这个坑。

(c) 修复方案（按推荐度排序）：

方案 1：改用 OrderBy

users = users.OrderBy(u => u.Score).ToList();

最简单、最不容易错。 代价是慢一些（实测 3.1 倍）。

方案 2：加决胜关键字

var indexed = users.Select((u, i) => (u, i)).ToArray();
Array.Sort(indexed, (a, b) =>
{
    int c = a.u.Score.CompareTo(b.u.Score);
    return c != 0 ? c : a.i.CompareTo(b.i);
});
users = indexed.Select(x => x.u).ToList();

性能好且确定性正确，代价是代码复杂一些。

方案 3：给数据加一个"插入序号"字段

如果 User 本身可以加字段，加一个自增的 Seq，排序时把它作为第二关键字。这也是数据库里"按非唯一列排序"的标准做法。

最重要的建议：把"该排序是否需要稳定"这个问题明确写进代码注释或接口文档。

这类 bug 的根源往往不是技术问题，而是需求没有说清楚。

8.5.5

(a) 组合方案：

第一层：数据特征探测（可选，开销要小）
  ├─ 扫描一遍，统计「逆序对比例」和「重复元素比例」
  └─ 根据结果选择策略

第二层：主排序
  ├─ 大量重复元素 -> 三路分区快排
  ├─ 几乎有序     -> 插入排序（O(n)）
  └─ 其他         -> 普通快排（随机化基准 + 三数取中）

第三层：保险丝（内省机制）
  ├─ 递归深度 > 2*log2(n)  -> 切换堆排序
  └─ 规模 < 16             -> 切换插入排序

(b) 切换条件：

条件	阈值	触发什么
数组规模	$< 16$	插入排序
递归深度	$> 2\log_2 n$	堆排序
重复元素比例	$> 50\%$（代价小的话可以探测）	三路分区
逆序对比例	$< 5\%$	插入排序（接近 $O(n)$）

注意"探测"本身的代价：扫描一遍是 $O(n)$，对于 $O(n \log n)$ 的排序来说是可以接受的（只占几分之一的开销）。但如果探测逻辑很复杂，就不划算了。

所以真实实现通常只做"零成本"的探测 —— 比如在分区过程中顺便统计重复元素的比例，而不是专门扫一遍。

(c) 验证方法：

这就是"最坏情况分析"和"对抗性测试"的价值。**

测试用例必须覆盖：

输入类型	目的
完全随机	验证平均性能
已排序	验证不会退化
完全逆序	验证不会退化
全部相同	验证三路分区生效
大量重复（如 90% 相同）	验证部分重复的处理
正序 + 少量噪声（近乎有序）	验证快速路径
锯齿形（[1,n,2,n-1,3,n-2,...]）	专治"三数取中"的对抗性输入
递增但带周期性	专治"取固定位置作基准"
各种规模（10、100、1万、100万）	验证阈值切换的正确性

验证指标：

正确性：结果必须和"参照实现"（比如 Array.Sort）完全一致
复杂度：统计比较次数，必须满足 $c \cdot n\log_2 n$（$c$ 是某个常数），不能出现 $n^2$ 的趋势
递归深度：记录最大深度，应该稳定在 $2\log_2 n$ 附近
时间稳定性：在各种输入下耗时应该在同一量级，最大值 / 最小值 < 5 倍

最后一条最重要：真正的"抗退化"不是"平均快"，而是"最坏和最好差不多"。

这就是 8.1 节归并排序最值钱的性质，也是内省排序追求的目标。

关于"锯齿形"输入：像 [1, n, 2, n-1, ...] 这种数据，三数取中的三个位置（lo、mid、hi）恰好取到最大、中间、最小，导致基准选得极差。这是针对"三数取中"的经典对抗性输入，现代实现会用"九数取中"或者随机化来防御。

十一、常见错误

误区	纠正
用 `Array.Sort` 却依赖稳定性	它不稳定（实测 2000 条时顺序完全打乱）。需要稳定用 `OrderBy` 或加决胜关键字。
用小数据测稳定性	小数组下 `Array.Sort` 退化为插入排序（稳定的），测不出问题。要用上千条数据测。
自己实现排序用在生产	手写的"教科书正确"快排比官方实现慢 1.7 倍。官方的优化人工难以企及。
认为学了算法没用	学的是判断力和选型能力，不是"自己实现"。知道"该用哪个"和"为什么"才是价值。
排序大结构体时直接排	200 字节的结构体 × 100 万条，交换会搬运 GB 级数据。排序下标数组能降到 MB 级。
认为"平均快"就够了	要的是"最坏和最好差不多"。归并排序和 `Array.Sort` 都追求这个，朴素快排不是。

十二、本节总结

内省排序 = 快排（主体）+ 堆排序（深度兜底）+ 插入排序（小数组）。.NET 的 Array.Sort 就是它。
三条保险丝各解决一个问题：堆排序防退化、插入排序减少小数组开销、三路分区处理重复元素。
Array.Sort 不稳定，OrderBy 稳定。实测 2000 条记录时前者完全打乱、后者严格保持。
小数据测不出不稳定性 —— 小数组下 Array.Sort 退化为插入排序。这是最危险的"测试通过但生产出错"类型。
性能实测（200 万）：Array.Sort 96.4 ms、OrderBy 297.8 ms（慢 3.1 倍）、手写快排 160.6 ms（慢 1.7 倍）。
小数组上官方实现依然快 2～3 倍 —— "理解算法"和"写出生产级实现"是两件事。
决策顺序：先问"要不要稳定"→ 再问"有没有特殊数据特征"（值域小/只要 Top-K/数据在磁盘）。99% 的情况直接 Array.Sort 或 OrderBy。
用"决胜关键字"实现稳定 —— 兼顾 Array.Sort 的性能和 OrderBy 的正确性。
排序大对象时排下标数组 —— 把 4 GB 的内存搬运降到 80 MB。

本章小结：第 8 章把排序这件事讲完了。

8.1 归并排序：最"老实"的算法。稳定、可预测，但需要 $O(n)$ 空间。实测中它在已排序数据上输给插入排序 8.5 倍 —— 提醒我们"渐进复杂度更优 ≠ 任何情况都更快"。
8.2 快速排序：平均最快，但最坏情况会退化到 $O(n^2)$（实测 376 倍），甚至栈溢出。"已排序的数据"这个最常见的输入恰好会触发它。
8.3 堆排序：唯一同时做到最坏 $O(n \log n)$ 和 $O(1)$ 空间的算法。内省排序的兜底方案。
8.4 非比较排序：跳出比较模型，用"数数"代替"比较"。实测快 447 倍，但前提条件严格。
8.5 工程实践：内省排序是怎么把它们拼起来的，以及真实工作中到底该怎么选。

贯穿全章的一条主线："最坏情况"比"平均情况"更重要。

从 8.2 的退化、8.3 的兜底、到 8.5 的内省排序 —— 整个第 8 章都在回答同一个问题：怎么让算法在任何人给的任何数据上，都不会崩掉。

下一章衔接：排序这一大块结束了。从第 9 章开始进入树 —— 它是本书后半部分最核心的数据结构。

树解决的是排序和哈希表都解决不好的问题：既要保持有序，又要支持快速的插入、删除、查找。哈希表查找快但无序（6.4 节讲过它的遍历顺序完全不可依赖），有序数组可以二分查找但插入是 $O(n)$。树把两者的优点结合了起来。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "8.5",
  "title": "工程中如何选排序",
  "covered": [
    "三种 O(n log n) 算法的短板与互补",
    "内省排序的三部分构成与流程图",
    "三条保险丝各自解决的问题",
    ".NET 四种排序 API 的对比（原地/稳定/返回类型）",
    "稳定性差异实测（Array.Sort 打乱 vs OrderBy 保持）",
    "「小数据测不出不稳定性」的陷阱（6 元素时 Array.Sort 显示稳定）",
    "性能实测：Array.Sort 96.4ms / OrderBy 297.8ms / 手写快排 160.6ms",
    "小数组上官方实现仍快 2-3 倍的实测与解释",
    "三步决策流程与完整决策表",
    "用决胜关键字实现稳定（兼顾性能与正确性）",
    "排序大对象时排下标数组（4GB 降到 80MB）",
    "抗退化的测试用例设计（含锯齿形对抗输入）"
  ],
  "unresolved": [
    "树结构留到第 9 章",
    "并发排序超出本书范围",
    "外部排序的完整实现超出本书范围"
  ],
  "canonical_terms": {
    "内省排序": "快排为主，深度超标切堆排、小数组切插入的混合排序",
    "混合排序": "根据数据规模或特征在多个算法间切换的排序"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 8.1-8.4 的全部排序算法",
    "读者会用 C# 的 LINQ 与 lambda 比较函数"
  ],
  "word_count_actual": 3080,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch08/Sec85/",
    "稳定性实测（2000 条 Array.Sort 打乱 / OrderBy 保持）、性能对比、小数组对比均为实测",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版稳定性实验只用 6 个元素，Array.Sort 因退化为插入排序而显示「稳定 ✓」，测不出问题；已改为 2000 条记录并把这个陷阱写成正文要点",
    "实验四的结论原写「插入排序在小数组上更快」，与实测（Array.Sort 全胜）相反；已修正说明并解释原因"
  ],
  "next": "9.1 树的术语与二叉树的形态"
}

8.5　工程中如何选排序