Lecture 19: 基本排序算法 (Basic Sorting Algorithms)
Lecture 19: 基本排序算法 (Basic Sorting Algorithms)
概述
本讲解决的核心问题是：给定一个数组与一个序关系 (ordering)，如何高效地把它重排成有序序列。 我们依次分析插入排序 (insertion sort)、选择排序 (selection sort)、冒泡排序 (bubble sort)、归并排序 (merge sort) 与快速排序 (quicksort) 的机制、代价与适应场景；随后说明任何基于比较的排序都不可能快过 Ω(n log n)，而整数键可用计数排序/基数排序突破这一下界。 最后引入泛型排序 (generic sorting)：qsort(base, nmemb, size, compar) 用函数指针 (function pointer) 把”比较规则”从算法中剥离出来，使同一份排序代码能处理 int、double、结构体与字符串——这正是 Lecture 12 回调思想最著名的应用。
核心概念与底层机制图解
- 排序问题的形式化与四个评价维度：输入是数组与比较函数，输出是满足序关系的一个排列。
- 直观解释：像给一叠考卷按分数排队，规则可以自己定（升序、降序、先按年龄再按姓名）。
- 底层机制图解：评价排序算法看四件事：时间（最坏/平均/最好）、空间（是否原地 in-place）、稳定性 (stability)（相等元素是否保持原次序）、适应性 (adaptivity)（近乎有序时是否更快）。稳定排序是”多关键字排序”的前提（先按次关键字排，再按主关键字稳定排）。
- 作用域与存储期：所有排序都原地修改调用者数组；辅助数组（归并的
aux）由算法自己malloc/free，属于 allocated storage duration。
- 插入排序 (insertion sort)：把数组看成”左侧已排序 + 右侧待插入”，每次取出一个元素向左找到位置插入——像整理手中的扑克牌，每抓到一张新牌就插进已排好的牌中。
- 底层机制图解：第
i轮把a[i]暂存为key，从i-1向左扫描：只要a[j] > key就右移一格（a[j+1] = a[j]），遇到a[j] <= key即停，把key写入空位。关键性质：内层循环会在第一个不大于key的元素处立即break。因此当数组已经有序时，每轮只做一次比较，总代价O(n)；一般而言代价为O(n + 逆序对数量)——这就是”插入排序在近乎有序的数据上极快”的根本原因。课程的isort.c正是这一算法对任意元素类型的泛型版本。 - 作用域与存储期：只用
key一个 automatic 变量，空间O(1)；把元素”右移”而不是交换，使元素移动次数等于逆序对数量，对”移动代价高的元素”更划算。
- 底层机制图解：第
- 选择排序 (selection sort)：第
i轮在a[i..n-1]中选出最小值并与a[i]交换——像每次从剩下的考卷里挑出分数最低的那张放到队尾。- 底层机制图解：比较次数恒为
n(n-1)/2（实测n = 7时为21），与输入顺序完全无关；交换最多n-1次，是三种O(n²)算法中写内存最少的，但不是稳定排序。 - 作用域与存储期：空间
O(1)，只用一个min下标变量；因为交换次数少，在”写操作昂贵”的存储介质上有历史价值。
- 底层机制图解：比较次数恒为
- 冒泡排序 (bubble sort) 与提前退出 (early exit)：相邻两两比较，大的元素像气泡一样浮到末尾——像一排人比身高，相邻两人矮的往前站，一轮下来最高的被推到队尾。
- 底层机制图解：第
i轮把第i大的元素放到a[n-1-i]；用swapped记录本轮是否发生交换，整轮无交换即有序列退出。加了提前退出后，有序输入只需n-1次比较（实测cmp = 6，与插入排序相同）；退化输入仍是O(n²)，且每次交换要 3 次赋值，实践中几乎总劣于插入排序。 - 作用域与存储期：空间
O(1)；swapped是 automatic 变量，生命周期仅限本轮循环。
- 底层机制图解：第
- 归并排序 (merge sort)：把数组一分为二、各自递归排序、再把两个有序段合并 (merge)。
- 直观解释：两叠已经排好的牌，只要反复比较两叠的顶牌、取走较小的那张，就能合并成一叠有序牌。
- 底层机制图解：递推式
T(n) = 2T(n/2) + O(n)，展开得O(n log n)（每层合并总代价O(n)，共log n层）。必须额外一块O(n)的辅助数组（本讲sorts.c中的aux），因为合并无法在原地安全完成；它是稳定的（相等元素优先取左段），且对链表特别友好（链表合并无需辅助数组）。比较次数几乎与输入无关（实测cmp = 14）。 - 作用域与存储期：递归深度与栈开销均为
O(log n)；辅助数组由merge_sort分配、返回前free。
- 快速排序 (quicksort)、Lomuto 与 Hoare 分区：选一个基准 (pivot)，把数组分成”小于等于 pivot”与”大于 pivot”两段，再递归排序两段——像按身高把队伍分成矮的一队和高的一队，再各自排队。
- 底层机制图解：Lomuto 分区用
a[hi]作 pivot，i指向”小于等于 pivot 区域的末尾”：j从lo扫到hi-1，凡a[j] <= pivot就i++并与a[i]交换；最后把 pivot 换到i+1并返回该下标。Hoare 分区取中间元素作 pivot，i、j两端相向而行，遇到”左边不小于 pivot、右边不大于 pivot”就交换，直到相遇并返回j；递归区间是[lo, j]与[j+1, hi]（不是j-1，否则死循环）。Lomuto 代码简单；Hoare 交换更少（实测随机输入：Lomutocmp=11, swap=9，Hoarecmp=32, swap=5），实践中更常用。 - 作用域与存储期：原地排序，空间只有递归栈
O(log n)（平均），最坏O(n)。
- 底层机制图解：Lomuto 分区用
- 最坏情况与基准选择 (worst case and pivot choice)：当每次划分都极度不平衡时，快速排序退化为
O(n²)。- 直观解释：如果每次挑中的”基准”都恰好是最大或最小的那个，队伍就永远只被分成”一个元素 + 其余全部”。
- 底层机制图解：对已经有序的输入使用”取末尾元素作 pivot”的 Lomuto，每轮刚好分出
0个和n-1个元素，T(n) = T(n-1) + O(n)给出O(n²)。实测有序输入{1..7}：Lomuto 需要cmp = 21 = n(n-1)/2、swap = 27，而 Hoare（中间 pivot）cmp = 26、swap = 0；n越大差距越是n²与n log n之别。三种常用对策：随机化 pivot、取”首/中/尾中位数”、小数组改用插入排序（cutoff）。 - 作用域与存储期：全部元素相等时 Hoare 仍把数组分成两半，避免 Lomuto 退化。
- 五种排序的对比 (comparison table)：
| 算法 | 最好 | 平均 | 最坏 | 额外空间 | 稳定 | 适应性 | n=7 实测比较/交换 |
|---|---|---|---|---|---|---|---|
| 插入排序 insertion | O(n) | O(n²) | O(n²) | O(1) | 是 | 强（逆序对相关） | 15 / 17 |
| 选择排序 selection | O(n²) | O(n²) | O(n²) | O(1)，写最少 | 否 | 无 | 21 / 5 |
| 冒泡排序 bubble | O(n) | O(n²) | O(n²) | O(1) | 是 | 有（提前退出） | 20 / 11 |
| 归并排序 merge | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 | 弱 | 14 / 20 |
| 快速排序 quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) 栈 | 否 | 弱 | 11 / 9（Lomuto） |
- 比较排序的下界
Ω(n log n)：任何只通过”比较两个元素”获取信息的排序算法，最坏情况至少需要Ω(n log n)次比较。- 直观解释：
n个元素共有n!种排列，算法必须能把它们全部区分开；每次比较只能得到”是/否”两种回答，因此至少需要log2(n!)个问题。 - 底层机制图解：把算法执行过程画成一棵决策树 (decision tree)：内部结点是比较、叶子是输出排列。
n个元素有n!种可能排列，所以叶子数 ≥n!，高度 ≥log2(n!)。用 Stirling 近似log2(n!) ≈ n log2 n - 1.44n，因此下界是Ω(n log n)。具体数字：n = 10^6时log2(n!) ≈ 1.9 × 10^7，而冒泡排序的n(n-1)/2 ≈ 5 × 10^11次比较——相差四万倍。 - 作用域与存储期：这条下界只约束基于比较的算法；不比较元素值（而是直接利用键的整数值）的算法不受它限制。
- 直观解释：
- 非比较排序 (non-comparison sorts)：计数排序与基数排序利用”键是小范围整数”这一额外信息——把分数为
k的考卷直接丢进第k号箱子，最后从 0 号箱子依次取走，不用互相比较。- 底层机制图解：计数排序 (counting sort) 用大小为
k（键的取值范围）的计数数组，时间O(n + k)、空间O(n + k)，且稳定（关键是从后往前回写）；基数排序 (radix sort) 对d位数字做d轮稳定排序，时间O(d(n + k))。代价是它们只适用于整数键，k很大时空间爆炸。 - 作用域与存储期：计数/输出数组都是 allocated storage duration，函数返回前必须
free。
- 底层机制图解：计数排序 (counting sort) 用大小为
- 泛型排序与函数指针 (generic sorting and function pointers)：把”如何比较”外置为一个回调函数，排序算法只依赖这个回调。
- 直观解释：像一台”通用分拣机”：机器只负责搬动与比较，至于”A 是否应该排在 B 前面”由你插入的规则卡片决定。
- 底层机制图解：
void qsort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*));。base是首地址、nmemb是元素个数、size是每元素的字节数，三者合起来让qsort能做通用指针算术：第i个元素地址是(char*)base + i * size（必须先转char*，因为void*不能做算术）。compar必须返回三路结果（负/零/正）。这就是 Lecture 12 的回调：qsort里写着(*compar)(p1, p2)，具体调用谁要到运行时才知道（汇编层是一次JSRR）。 - 作用域与存储期：比较函数通常是文件作用域的
static函数，具有 static storage duration，其地址（函数指针值）在整个程序运行期间不变。
代码示例与底层机制分析
示例 1：五种排序算法在同一输入上的比较与交换次数
代码 (C) — /tmp/ece220_l19/sorts.c（节选算法本体；完整文件含计数与打印，已编译运行）：
static void insertion_sort(int32_t a[], int32_t n)
{
int32_t i, j, key;
for (i = 1; n > i; i++) {
key = a[i];
for (j = i - 1; 0 <= j; j--) {
cmp_count++;
if (a[j] <= key) {
break; /* 已有序时立刻退出，这就是适应性 */
}
a[j + 1] = a[j]; /* 右移一格，而不是交换 */
swap_count++;
}
a[j + 1] = key;
swap_count++;
}
}
static void selection_sort(int32_t a[], int32_t n)
{
int32_t i, j, min;
for (i = 0; n - 1 > i; i++) {
min = i;
for (j = i + 1; n > j; j++) {
cmp_count++;
if (a[j] < a[min]) {
min = j;
}
}
if (min != i) {
swap(&a[i], &a[min]);
}
}
}
static void bubble_sort(int32_t a[], int32_t n)
{
int32_t i, j, swapped;
for (i = 0; n - 1 > i; i++) {
swapped = 0;
for (j = 0; n - 1 - i > j; j++) {
cmp_count++;
if (a[j] > a[j + 1]) {
swap(&a[j], &a[j + 1]);
swapped = 1;
}
}
if (!swapped) {
break; /* 提前退出：本轮无交换 => 已有序 */
}
}
}
static void merge(int32_t a[], int32_t lo, int32_t mid, int32_t hi, int32_t aux[])
{
int32_t i = lo, j = mid + 1, k;
for (k = lo; hi >= k; k++) {
aux[k] = a[k]; /* 先把整段拷进辅助数组 */
}
for (k = lo; hi >= k; k++) {
if (i > mid) {
a[k] = aux[j++]; /* 左半用尽 */
} else if (j > hi) {
a[k] = aux[i++]; /* 右半用尽 */
} else {
cmp_count++;
if (aux[j] < aux[i]) { /* 严格小于才取右边 => 稳定 */
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
swap_count++;
}
}
static int32_t partition_lomuto(int32_t a[], int32_t lo, int32_t hi)
{
int32_t pivot = a[hi], i = lo - 1, j;
for (j = lo; hi > j; j++) {
cmp_count++;
if (a[j] <= pivot) {
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i + 1], &a[hi]); /* pivot 归位 */
return i + 1;
}
static int32_t partition_hoare(int32_t a[], int32_t lo, int32_t hi)
{
int32_t pivot = a[lo + (hi - lo) / 2], i = lo - 1, j = hi + 1;
for (;;) {
do {
i++;
cmp_count++;
} while (a[i] < pivot);
do {
j--;
cmp_count++;
} while (a[j] > pivot);
if (i >= j) {
return j; /* 返回 j，递归 [lo,j] 与 [j+1,hi] */
}
swap(&a[i], &a[j]);
}
}
验证到的真实输出（输入 {38, 27, 43, 3, 9, 82, 10}，gcc -g -std=c99 -Wall -Werror sorts.c -o sorts && ./sorts）：
insertion sort : 3 9 10 27 38 43 82 cmp=15 swap=17
selection sort : 3 9 10 27 38 43 82 cmp=21 swap= 5
bubble sort : 3 9 10 27 38 43 82 cmp=20 swap=11
merge sort : 3 9 10 27 38 43 82 cmp=14 swap=20
quicksort (Lomuto) : 3 9 10 27 38 43 82 cmp=11 swap= 9
quicksort (Hoare) : 3 9 10 27 38 43 82 cmp=32 swap= 5
sorted input {3,9,10,27,38,43,82}:
insertion : 3 9 10 27 38 43 82 cmp= 6 swap= 6
bubble : 3 9 10 27 38 43 82 cmp= 6 swap= 0
selection : 3 9 10 27 38 43 82 cmp=21 swap= 0
quicksort Lomuto : 3 9 10 27 38 43 82 cmp=21 swap=27
nearly sorted {3,9,10,27,38,43,82} with 82 moved to front:
insertion : 3 9 10 27 38 43 82 cmp=11 swap=12
bubble : 3 9 10 27 38 43 82 cmp=11 swap= 6
selection : 3 9 10 27 38 43 82 cmp=21 swap= 6
worst case for quicksort, sorted input, n = 7:
Lomuto, last pivot : 1 2 3 4 5 6 7 cmp=21 swap=27
Hoare, middle pivot : 1 2 3 4 5 6 7 cmp=26 swap= 0
【代码做什么？】
- 六种实现各自对同一乱序数组排序，输出全部为
3 9 10 27 38 43 82；右侧是比较次数与交换/移动次数。 - 随机输入下：插入
15/17，选择21/5（比较恒为n(n-1)/2），冒泡20/11，归并14/20，Lomuto 快排11/9（比较最少），Hoare 快排32/5（交换最少）。 - 有序输入下：插入排序只需
6次比较（每轮一次break），冒泡排序也只需6次（第一轮无交换即退出），而选择排序仍然是21——它完全不具备适应性。 - 近乎有序输入（
82移到最前，只有 6 个逆序对）下插入排序cmp = 11，少于随机输入的15；有序输入下 Lomuto 快排的比较次数涨到21 = n(n-1)/2，正是最坏情况的开端，而 Hoare 版（中间 pivot）swap = 0，没有退化成”1 和 n-1”的灾难。
【底层机制透视】 插入排序的内层循环 break 让它具有输入敏感性：运行时间是 O(n + I)，I 为逆序对个数。选择排序的内层循环没有 break，无论输入如何都跑满 n(n-1)/2 次，因此它是”输入无关“的——这在需要可预测延迟的实时系统里反而是优点。 归并排序的 swap_count 高（20）是因为每一次写回都算一次移动，它的比较与移动次数都是 O(n log n) 量级且常数稳定，这也是它在”外部排序”与”链表排序”中不可替代的原因。 partition_hoare 的 do { i++; cmp_count++; } while (a[i] < pivot); 依赖”pivot 一定在区间内”这一事实，因此不会越界；而 partition_lomuto 依赖 a[hi] 本身是 pivot，所以 j 只扫到 hi-1。 两个 partition 都通过 swap 修改变量：由于 int32_t 大小固定，这里直接用了一个 int32_t 临时变量；泛型版本则必须用 memcpy（见示例 4）。
【内存布局图解】（插入排序第 i 轮，i = 4、key = a[4] = 9）
a[0] a[1] a[2] a[3] a[4] a[5] a[6] i = 4，key = a[4] = 9
+----+----+----+----+----+----+----+
| 3 | 27 | 38 | 43 | 9 | 82 | 10 | 排序前：已排序区 a[0..3]，key 暂存于变量
| 3 | 27 | 9 | 38 | 43 | 82 | 10 | ① 43、38、27 依次右移（9 比它们都小）
| 3 | 9 | 27 | 38 | 43 | 82 | 10 | ② a[0]=3 <= 9，break；key 写入空位
+----+----+----+----+----+----+----+
^ 已排序区扩展为 a[0..4]；本轮移动 I_i 个元素，总计 I = 逆序对数量
【与汇编的对应】（a 基址由 LEA 取得，元素偏移按字计算）
; ---- 插入排序内层：while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; } ----
; R1 = key, R2 = j, R3 = 数组基址, R4 = &a[j]
INS_IN ADD R2,R2,#0 ; j >= 0 ?
BRn INS_PLACE
ADD R4,R3,R2 ; R4 = &a[j]
LDR R0,R4,#0 ; R0 = a[j]
NOT R0,R0
ADD R0,R0,#1
ADD R0,R0,R1 ; R0 = key - a[j]
BRzp INS_PLACE ; key >= a[j] ? 停（适应性：有序时立即退出）
LDR R0,R4,#0
STR R0,R4,#1 ; a[j+1] = a[j]
ADD R2,R2,#-1 ; j--
BRnzp INS_IN
INS_PLACE
ADD R2,R2,#1
ADD R4,R3,R2
STR R1,R4,#0 ; a[j+1] = key
示例 2：Lomuto 分区的逐步过程
代码 (C) — /tmp/ece220_l19/partition_trace.c（核心函数，带 verbose 开关打印每一轮）：
static int32_t partition_lomuto(int32_t a[], int32_t lo, int32_t hi, int32_t verbose)
{
int32_t pivot = a[hi];
int32_t i = lo - 1;
int32_t j;
for (j = lo; hi > j; j++) {
comparisons++;
if (a[j] <= pivot) {
i++;
if (i != j) {
swap(&a[i], &a[j]);
}
}
}
swap(&a[i + 1], &a[hi]);
return i + 1;
}
验证到的真实输出（输入 {7, 2, 1, 6, 8, 5, 3, 4}）：
Lomuto trace:
partition(lo=0, hi=7), pivot = a[7] = 4
j=0: a[0]= 7 > 4, keep -> 7 2 1 6 8 5 3 4
j=1: a[1]= 2 <= 4, swap i=0 -> 2 7 1 6 8 5 3 4
j=2: a[2]= 1 <= 4, swap i=1 -> 2 1 7 6 8 5 3 4
j=3: a[3]= 6 > 4, keep -> 2 1 7 6 8 5 3 4
j=4: a[4]= 8 > 4, keep -> 2 1 7 6 8 5 3 4
j=5: a[5]= 5 > 4, keep -> 2 1 7 6 8 5 3 4
j=6: a[6]= 3 <= 4, swap i=2 -> 2 1 3 6 8 5 7 4
place pivot at index 3
after partition: 2 1 3 4 8 5 7 6 (pivot 4 fixed at index 3)
partition(lo=0, hi=2), pivot = 3: -> 2 1 3 | 4 8 5 7 6 (pivot 3 fixed at index 2)
partition(lo=0, hi=1), pivot = 1: -> 1 2 3 | 4 8 5 7 6 (pivot 1 fixed at index 0)
partition(lo=4, hi=7), pivot = 6: -> 1 2 3 4 5 6 7 8 (pivot 6 fixed at index 5)
partition(lo=6, hi=7), pivot = 8: -> 1 2 3 4 5 6 7 8 (pivot 8 fixed at index 7)
sorted : 1 2 3 4 5 6 7 8
comparisons = 14, swaps = 9
【代码做什么？】
- 第一次分区取
a[7] = 4作 pivot，i从-1开始；j从 0 扫到 6，凡a[j] <= 4就把i前移并把该元素换到”小值区”末尾。 - 扫描结束时数组为
2 1 3 6 8 5 7 4、i = 2；把 pivot 与a[i+1]交换得2 1 3 4 8 5 7 6，pivot 4 从此固定在下标 3。 - 递归处理左段
[0,2]（pivot 3）与右段[4,7]（pivot 6），各自重复上述过程；每完成一次分区至少有一个元素归位，最终得到1 2 3 4 5 6 7 8，全程comparisons = 14, swaps = 9（关闭打印后重跑计数完全相同）。
【底层机制透视】 i 的语义是”小于等于 pivot 区域的最后一个下标”，循环不变式为 a[lo..i] <= pivot、a[i+1..j-1] > pivot、a[j..hi-1] 未检查、a[hi] == pivot——理解它就理解了 Lomuto 为什么正确。 分区是原地的，只用三个自动变量；每次分区结束时 pivot 落在最终位置，因此快速排序不需要”合并”步骤，这是它与归并排序最根本的结构差异（quicksort 先分后不管，mergesort 先递归后合并）。从 trace 看每层比较次数为 7、2、1、3、1，总计 14 次，远小于 n(n-1)/2 = 28——因为选到的 pivot 接近中位数。
【内存布局图解】（第一次分区结束时）
下标: 0 1 2 3 4 5 6 7
+----+----+----+----+----+----+----+----+
| 2 | 1 | 3 | 4 | 8 | 5 | 7 | 6 |
+----+----+----+----+----+----+----+----+
<-- <= pivot --> ^ <-- 未处理，> pivot -->
pivot 4 已归位（下标 3，永不再移动）
调用树： [0..7] p=4 -> 分割点 3
/ \
[0..2] p=3 -> 分割点 2 [4..7] p=6 -> 分割点 5
/ \ / \
[0..1] 空区间 空区间 [6..7] p=8 -> 分割点 7
p=1 -> 分割点 0
【与汇编的对应】（Lomuto 内层循环；a 基址在 R3，hi 在 R5+5）
; ---- for (j = lo; j < hi; j++) if (a[j] <= pivot) { i++; swap(a[i], a[j]); } ----
; R1 = pivot, R2 = j, R3 = 数组基址, R4 = i
LOM_LOOP
LDR R0,R5,#5 ; R0 = hi（hi 是本帧参数）
NOT R0,R0
ADD R0,R0,#1
ADD R0,R0,R2 ; R0 = j - hi
BRzp LOM_END ; j >= hi，结束本轮分区
ADD R0,R3,R2
LDR R0,R0,#0 ; R0 = a[j]
NOT R0,R0
ADD R0,R0,#1
ADD R0,R0,R1 ; R0 = pivot - a[j]
BRn LOM_NEXT ; a[j] > pivot，跳过
ADD R4,R4,#1 ; i++；随后用三次 LDR/STR 交换 a[i] 与 a[j]
LOM_NEXT
ADD R2,R2,#1 ; j++
BRnzp LOM_LOOP
LOM_END
; 最后 swap(a[i+1], a[hi]) 让 pivot 归位，并返回 i+1 作为分割点
示例 3：qsort 与三路比较函数
代码 (C) — /tmp/ece220_l19/qsort_demo.c（节选）：
typedef struct player_t {
char name[16];
int32_t age;
int32_t games;
} player_t;
/* 三路比较：负数表示 a < b，0 表示等价，正数表示 a > b */
static int cmp_int(const void* p1, const void* p2)
{
const int32_t* a = p1;
const int32_t* b = p2;
if (*a < *b) {
return -1;
}
if (*a > *b) {
return 1;
}
return 0;
}
static int cmp_age(const void* p1, const void* p2)
{
const player_t* a = p1;
const player_t* b = p2;
if (a->age < b->age) {
return -1;
}
if (a->age > b->age) {
return 1;
}
return 0;
}
static int cmp_age_then_name(const void* p1, const void* p2) /* 多关键字 */
{
const player_t* a = p1;
const player_t* b = p2;
int by_age = cmp_age(p1, p2);
if (0 != by_age) {
return by_age;
}
return strcmp(a->name, b->name);
}
/* 降序只需把两个操作数对调：cmp_games_desc 与 cmp_age 结构相同，
只是把 a->age/b->age 换成 b->games/a->games */
/* qsort 传给比较函数的是"指向数组元素的指针"，元素本身是 char*，所以要再解引用一次 */
static int cmp_cstring(const void* p1, const void* p2)
{
const char* const* s1 = p1;
const char* const* s2 = p2;
return strcmp(*s1, *s2);
}
验证到的真实输出：
integers before: 42 -7 42 0 13 -7 100 5
integers after : -7 -7 0 5 13 42 42 100
strings before: pear Apple fig apple banana Fig
strings after : Apple Fig apple banana fig pear
sorted by age: Ed(19) Bo(25) Al(25) Di(25) Cy(31) <- 25 岁三人次序未定义
sorted by age, then by name:
Ed age=19 games=55
Al age=25 games=12
Bo age=25 games=40
Di age=25 games=90
Cy age=31 games= 7
sorted by name: Al Bo Cy Di Ed（按姓名字符串次序）
sorted by games, descending:
Di age=25 games=90
Ed age=19 games=55
Bo age=25 games=40
Al age=25 games=12
Cy age=31 games= 7
【代码做什么？】
qsort(nums, 8, sizeof(nums[0]), cmp_int)把含重复值的整数数组排成-7 -7 0 5 13 42 42 100，注意两个42的相对次序未定义（qsort不保证稳定）。- 字符串数组用
cmp_cstring排成Apple Fig apple banana fig pear——这是ASCII 次序（大写字母A–Z是 65–90，小写是 97–122），因此Apple与Fig排在小写单词之前，与”字典序（忽略大小写）”不同。 - 同一组
player_t数据用四个不同的比较函数各排一次：按年龄、按年龄再按姓名、按姓名、按场数降序；排序代码一次都没改，改的只是比较函数。”按年龄”与”按年龄再按姓名”的 25 岁组次序不同（Bo, Al, DivsAl, Bo, Di），这是多关键字比较起作用的证据。
【底层机制透视】 qsort 只认识 void* 与字节大小，因此它内部的元素地址计算必然是 (char*)base + i * size；把 void* 转成 char* 是必须的，因为 void* 上的指针算术在 C 标准中没有定义。int32_t 的 size = 4、player_t 的 size = 24（16 字节 name + 4 age + 4 games），qsort 用同一段 memcpy 搬运逻辑处理二者。 比较函数的参数是指向元素的指针，不是元素本身。对 int32_t nums[]，元素是 int32_t，所以参数是 int32_t*；对 char* words[]，元素是 char*，所以参数是 char**——这就是 cmp_cstring 必须写两层解引用 strcmp(*s1, *s2) 的原因，也是学生最常犯的错误。 比较函数必须给出三路结果：写成 return *a - *b; 会在接近 INT32_MIN/MAX 时有符号整数溢出（UB），正确写法是显式 <、> 分支；返回值的大小无关紧要，只有符号有意义。在机器层，qsort 里的 (*compar)(p1, p2) 是一次间接调用（LC-3 的 JSRR），使同一段排序代码获得”多态”能力——与 Lecture 12 的 I/O 通道函数指针表、示例 4 的 is_smaller 完全同源。
【内存布局图解】（player_t team[5] 与 qsort 眼中的它）
team（栈上 5 × 24 = 120 字节）
+----------------+----------------+----------------+
| name[0..15] | age (4 字节) | games (4 字节) | 每个元素 24 字节
+----------------+----------------+----------------+
^
第 0 个元素 = cmp_age 的 p1：qsort 传的是"指向这 24 字节的指针"，
函数内转成 player_t* 后按偏移访问 age；调用链 qsort -> (*compar) -> cmp_age
【与汇编的对应】（(*compar)(p1, p2) 的一次间接调用）
; ---- qsort 内部：p1 在 R5+4，p2 在 R5+5，compar 在 R5+6 ----
LDR R0,R5,#6 ; R0 = 函数指针（被调用函数的第一条指令地址）
ADD R6,R6,#-1
LDR R1,R5,#5
STR R1,R6,#0 ; 参数从右向左压栈：先 p2
ADD R6,R6,#-1
LDR R1,R5,#4
STR R1,R6,#0 ; 再 p1
JSRR R0 ; *** 间接调用：目标地址来自变量（多态）***
LDR R1,R6,#0 ; R1 = 比较结果
ADD R6,R6,#3 ; 弹出返回值与两个参数
ADD R1,R1,#0
BRnz Q_NO_SWAP ; compar <= 0 已就绪，不交换
示例 4：课程的泛型插入排序 isort.c
代码 (C) — 课程公开源码 Ccode/isort.c（核心函数；为符合 ECE 220 编码规范，原文件的制表符缩进已规范化为 4 空格，代码逻辑逐字未改）：
static int32_t
isort (void* base, int32_t n_elts, size_t size,
int32_t (*is_smaller) (void* t1, void* t2))
{
char* array = base; /* array pointer (used for pointer arithmetic) */
void* current; /* current element being placed into sorted subarray */
int32_t sorted; /* outer loop index; number of elements sorted */
int32_t index; /* inner loop index for placing current element */
if (NULL == (current = malloc (size))) {
return 0;
}
for (sorted = 2; n_elts >= sorted; sorted++) {
memcpy (current, array + (sorted - 1) * size, size);
for (index = sorted - 1; 0 < index; index--) {
if ((*is_smaller) (current, array + (index - 1) * size)) {
memcpy (array + index * size,
array + (index - 1) * size, size);
} else {
break;
}
}
memcpy (array + index * size, current, size);
}
free (current);
return 1;
}
验证到的真实输出（gcc -g -std=c99 -Wall -Werror isort.c -o isort && ./isort）：
integer sort -> 1: -10 22 30 50 73 99 104
double sort -> 1: -222.0000 -17.0000 3.1415 5.0000 33.0000 39.0000 60.0000 109.0000
string sort -> 1: ASCII Be Please alphabetical in instead. list not of order order. sort sure this to use words
【代码做什么？】
- 启动时
malloc(size)申请恰好一个元素大小的临时空间current——这是泛型排序无法把元素放进int32_t变量时的通用解法；分配失败返回 0。 - 外层
for (sorted = 2; n_elts >= sorted; sorted++)把已排序区从长度 1 逐步扩展到n。 - 每轮用
memcpy把array[(sorted-1)*size]拷进current，然后内层从右向左比较：若current更小就把左边的元素整体右移size字节。 - 一旦
is_smaller返回假（current不再更小）就break，把current拷回空位；这正是插入排序的适应性来源。 main用同一个isort分别排序int32_t、double、char*三种数组，打印结果与返回值 1（成功）。
【底层机制透视】 char* array = base; 是泛型指针算术的关键字：void* 不能做算术，转成 char* 后 array + index * size 就精确表示”第 index 个元素的起始字节地址”。若误写成 int32_t*，则 + index * size 会再乘 4 倍，导致越界写。 元素搬运用 memcpy(dest, src, size) 而不是赋值：编译期不知道类型，只能按字节复制。memcpy 要求源与目标不重叠——本例右移时目标比源高恰好 size，属于相邻不重叠，安全；若整段搬移可能重叠则必须用 memmove。 is_smaller 的签名是 int32_t (*)(void*, void*)，非零表示第一个更小——注意它与 qsort 的三路 compar 不同：isort 只需二路的”小于”判断（return ((*int1) < (*int2));）。字符串版本 string_is_smaller 的参数是 char**（strcmp(*s1, *s2) < 0），输出 ASCII Be Please alphabetical ... 是 strcmp 的 ASCII 次序（大写在前）而非字母表次序。
【内存布局图解】（isort 处理 int32_t 数组时的字节视图）
调用者数组 base（栈上） isort 的 current（堆上，size 字节）
+----+----+----+----+----+----+----+ +----+
| 38 | 27 | 43 | 3 | 9 | 82 | 10 | | 27 | <- 当前要插入的元素
+----+----+----+----+----+----+----+ +----+
^ ^ ^
base + 0*size base + 2*size（char* 算术） malloc(size) 返回的独立块
memcpy(array + index*size, array + (index-1)*size, size)：每次搬动一个元素
【与汇编的对应】（元素地址计算与 memcpy 调用）
; ---- 泛型元素地址计算：array + index * size，必须按字节加 ----
; R1 = array（char* 基址）, R2 = index, R3 = size
ADD R0,R2,#0 ; R0 = index
JSR MULT ; R0 = index * size（LC-3 无乘法指令，用子程序）
ADD R0,R1,R0 ; R0 = (char*)base + index * size
; 把 R0 作为参数压栈后调用 MEMCPY，即可复制任意 size 字节的元素
常见错误与调试技巧
- 比较函数参数类型写错：把
char*数组的比较函数写成const char*而非const char**，导致strcmp把字符串内容当成指针使用，段错误。 调试：gcc -std=c99 -Wall -Werror会给出 incompatible pointer type 警告；GDB 中p *(char**)p1与p (char*)p1对比看哪个是合法地址。 - 比较函数返回差值导致溢出：
return *a - *b;在int32_t极值附近溢出（UB），排序结果错乱。 调试：gcc -fsanitize=signed-integer-overflow -g（或-ftrapv）在溢出处中止；改用显式</>分支返回-1/0/1。 - 分区边界写错造成死循环 / 辅助数组未检查：Hoare 分区若递归写成
quick(a, lo, p - 1);，当p == lo时左半区间不缩小而死循环；归并排序的aux = malloc(...)失败后直接使用则对NULL解引用。调试：前者用gdb的Ctrl-C+bt看递归深度爆炸，并打印lo/hi/p确认每次分割至少缩减一个元素（Hoare 必须递归[lo,p]与[p+1,hi]）；后者用valgrind -q ./prog看 “Invalid write”。 memcpy处理重叠区域 / 递归爆栈：泛型排序中整段搬移若源与目标重叠必须改用memmove；快速排序对有序输入的最坏递归深度为O(n)，会耗尽 8 MB 栈。调试：前者用valgrind -q ./prog看 “overlapping” 或用x/8xb array逐字节核对；后者用ulimit -s查栈上限、gdb捕获SIGSEGV后bt看是否成千上万个同名帧，再用随机/中位数 pivot 降低深度。- 误以为
qsort稳定：想用”先按次关键字排、再按主关键字排”实现多关键字排序时，若qsort不稳定，结果是错的（本讲示例中两个42的次序确实未定义）。 调试：改用稳定的归并排序，或用”比较函数里直接比较全部关键字”（如cmp_age_then_name）——这是最实用的修正。
关键要点
O(n²)三种算法里，插入排序对近乎有序输入最好（代价O(n + 逆序对数)），选择排序不具备适应性但写内存最少，冒泡排序加提前退出后最好情况可到O(n)。- 归并排序以
O(n)辅助空间换取最坏情况O(n log n)与稳定性；快速排序原地、常数小、平均最快，但最坏O(n²)，必须靠随机化或中位数 pivot 规避。比较排序的下界Ω(n log n)来自决策树叶子数n!；计数/基数排序用”键可枚举”这一额外信息突破下界，但只适用于整数键。 - 泛型排序是把比较规则外置为函数指针回调：
qsort(base, nmemb, size, compar)用(char*)base + i * size做通用指针算术，比较函数必须返回三路结果；其参数是”指向元素的指针”（int数组给int*，char*数组给char**），这一层解引用是最常见的错误来源。
思考题（带答案）
问题 1：为什么插入排序对”近乎有序”的数组极快，而选择排序无论输入如何都同样慢？请用比较次数说明。
答案：插入排序第 i 轮把 key 与左侧元素比较，遇到第一个不大于它的元素就 break，因此总比较次数为 n - 1 + I（I 为逆序对个数）；近乎有序时 I 很小，总代价接近 O(n)（实测 7 个元素的有序输入只用 6 次比较）。选择排序第 i 轮必须扫描 a[i+1..n-1] 找最小值，没有提前退出的依据，比较次数恒为 n(n-1)/2（实测恒为 21）。
问题 2：下面的比较函数在什么输入下会出错？如何修正？
static int cmp(const void* p1, const void* p2)
{
const int32_t* a = p1;
const int32_t* b = p2;
return *a - *b;
}
答案：当 *a - *b 超出 int32_t 范围时发生有符号整数溢出（UB）：例如 *a = 2000000000、*b = -2000000000 的差值为 4 × 10^9，超出 INT32_MAX，可能回绕成负数使排序颠倒。修正为显式三分支：if (*a < *b) { return -1; } if (*a > *b) { return 1; } return 0;。