排序
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| insertion sort/ɪnˈsɜːʃn sɔːt/ | 插入排序 | chā rù pái xù |
| merge sort/mɜːdʒ sɔːt/ | 归并排序 | guī bìng pái xù |
| inversion/ɪnˈvɜːʃn/ | 逆序 | nì xù |
课程数据集
- 对 $[5, 2, 9, 1, 7, 3]$ 排序。插入排序 insertion sort 让有序前缀逐渐长大，每张新牌向后滑；归并排序 merge sort 折半、各排、再并；快排围绕基准分区；冒泡只换相邻逆序——教学用，实战少用。
{exercise:uni-cs0506-families}
练习
只交换相邻元素的排序在固定数据集上的交换次数恰好是——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
每次相邻交换恰好修复一个逆序——逆序数就是账单。
逆序数
- 逆序 inversion 是一对逆置元素；课程数据集有 $8$ 对：$(5,2), (5,1), (5,3), (2,1), (9,1), (9,7), (9,3), (7,3)$。相邻交换一次恰好修复一个逆序，所以任何只换相邻的排序在这里恰好做 $8$ 次交换——插入排序的移动数也等于逆序数。
- 归并排序在合并中顺带数出同样的逆序，而每个元素至多被搬 $\log_2 6 \approx 2.6$ 层：一次移动修复多个逆序，这就是 $O(n \log n)$ 对 $O(n^2)$ 的全部故事。
{exercise:uni-cs0506-inversions}
练习
数据集 [5, 2, 9, 1, 7, 3] 有——个逆序。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
数逆置对：(5,2)、(5,1)、(5,3)、(2,1)、(9,1)、(9,7)、(9,3)、(7,3)。
两手推演
- 插入：$2$ 移一次；$9$ 零次；$1$ 三次；$7$ 一次；$3$ 三次——合计 $8$ 次移动、$11$ 次比较，结果 $[1, 2, 3, 5, 7, 9]$。
- 归并：折半成 $[5, 2, 9]$ 与 $[1, 7, 3]$；递归得 $[2, 5, 9]$ 与 $[1, 3, 7]$；一次合并：$1, 2, 3, 5, 7, 9$，共 $10$ 次比较。$n = 1000$ 时两族相差 $100$ 倍。
例子
有序输入配上首元素基准就是快排的最坏情况 $O(n^2)$——不是罕见，是陷阱。稳定性活在归并与插入里，不在快排与堆排里。
{exercise:uni-cs0506-trace}
练习
同一数据集上归并排序用——次比较。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
实测 10 次，插入为 11——差距随规模拉大。