Hello 算法排序章节练习题精讲：模拟推演、稳定性辨析与归并、计数排序实战

本篇指南围绕《Hello 算法》繁中版排序章節練習題展开，逐题解析「知識鞏固」中的手动模拟与稳定性推演，并给出「程式設計練習」中归并排序与计数排序的完整解题思路、参考实现与复杂度分析。读完本文，你将不仅会算出每一轮排序后的数组状态，更能从源码级视角理解稳定性差异、计数排序的空间代价，以及基數排序在固定位数场景下的优势。

一、知識鞏固：用手推演理解排序的本质

练习题的第一部分并不要求写代码，而是要求对「選擇排序」和「泡沫排序」进行逐轮模拟。这种推演能力之所以重要，是因为它能直观暴露排序算法每一步的不变式（invariant）：每一轮结束后，数组中哪一段已经确定、哪一段仍在变化。

1.1 選擇排序前兩輪模擬

给定数组 [4, 2, 5, 1, 3]，从小到大排序。选择排序的核心是：每轮从未排序区间选出最小元素，与未排序区间的首元素交换（参见选择排序原理与源码实现）。

• 第 1 轮：未排序区间为 [0, 4]，最小元素是 1（位于索引 3），与索引 0 处的 4 交换，得到 [1, 2, 5, 4, 3]。此时索引 0 已确定。
• 第 2 轮：未排序区间为 [1, 4]，其中最小元素是 2，而它恰好已经位于索引 1，无需交换，数组保持 [1, 2, 5, 4, 3]。此时索引 0、1 均已确定。

輪次	陣列狀態	說明
1	[1, 2, 5, 4, 3]	最小元素 1 與首位交換
2	[1, 2, 5, 4, 3]	數值 2 已位於索引 1，無須交換

后续只需在 [5, 4, 3] 中继续选择最小元素。对照源码 selectionSort 的双层循环可以确认：外循环 i 每推进一轮，[0, i] 区间就整体有序，这正是选择排序每轮「确定一个位置」的不变式。

1.2 泡沫排序第一輪模擬

泡沫排序通过反复比较并交换相邻元素，将最大元素一步步「冒泡」到右端（参见泡沫排序原理）。对 [4, 2, 5, 1, 3] 执行第一轮：

比較	動作	陣列狀態
4 vs 2	交換	[2, 4, 5, 1, 3]
4 vs 5	不換	[2, 4, 5, 1, 3]
5 vs 1	交換	[2, 4, 1, 5, 3]
5 vs 3	交換	[2, 4, 1, 3, 5]

第一轮共发生 3 次交换，最大元素 5 被移动到末尾，因此最后一个位置已经确定。

一个值得注意的对比：选择排序每轮确定未排序区间的最小值放最前，冒泡排序每轮确定最大值放最后；前者完成 $n-1$ 轮后排序完毕，后者同样需要 $n-1$ 轮，但可以通过 flag 标志位在数组提前有序时立即退出（见bubble_sort.c 中的 bubbleSortWithFlag），使最佳时间复杂度降至 $O(n)$。

1.3 稳定性实验：相等元素的次序会变吗

给定数组 $[2_a, 2_b, 1]$（下标用于区分两个数值相同的 2），分别考察两种排序：

1. 选择排序第一轮：选出最小元素 1 并与首位 $2_a$ 交换，得到 $[1,2_b,2_a]$。$2_a$ 被换到 $2_b$ 之后，相对次序被改变了。这正是选择排序被称为「非穩定排序」的原因——元素 nums[i] 可能被交换到与其相等元素的右边（参见选择排序稳定性分析）。

2. 冒泡排序第一轮：先比较 $2_a$ 与 $2_b$，因两者相等不交换；再比较 $2_b$ 与 1 并交换，得到 $[2_a, 1, 2_b]$。$2_a$ 仍在 $2_b$ 之前，相对次序保持不变。

结论：稳定性取决于交换策略。冒泡排序只在「左元素 > 右元素」时交换相邻元素，相等元素之间从不交换，因此是稳定排序；而选择排序跨越式地把远处的最小元素交换到前方，可能越过相等元素，因此不稳定。

1.4 计数排序还是基数排序：8 位学号的选择题

学校要对大量固定为 8 位的学号排序，练习题给出了三个关键问题：

1. 基数排序需要几轮？ 学号有 8 个数字位，从最低位（第 1 位）到最高位（第 8 位）共需 8 轮，每轮只按 0~9 分桶。
2. 为什么直接计数排序会浪费大量位置？ 8 位学号的取值范围是 $0 \sim 10^8 - 1$（$m = 10^8$），而实际学生数量 $n$ 远小于 $m$。若把整个学号当作整数下标做计数排序，需要为几乎所有不会出现的数值预留计数位置，绝大多数 counter 槽位恒为 0。
3. 应选哪一种？ 应选择基数排序。它利用「位数固定、每位只有 10 种取值」的结构，只需重复 8 轮稳定的按位计数排序即可（参见基数排序原理）。

这一问考查的是两种非比较排序的适用边界，正是计数排序文档所强调的局限：计数排序适用于数据量大但数据范围小的场景；当 $n \ll m$ 时，$O(m)$ 的时间开销甚至可能劣于 $O(n \log n)$ 的比较排序。

二、程式設計練習：不调用库函数实现两种排序

2.1 用归并排序排列数组（LeetCode 912）

题目要求：给定整数数组 nums，自行实现归并排序，按非递减顺序排列并返回，禁止调用语言自带排序函数（对应 LeetCode 912. 排序数组）。

解题提示拆解：

1. 递归终止：区间长度不超过 1 时已经有序，直接返回；
2. 划分阶段：从中点把区间 [left, right] 分成 [left, mid] 与 [mid+1, right] 两半，分别递归排序；
3. 合并阶段：用两个指针同时扫描两个有序半区，每次取较小者写入临时数组 tmp，最后将 tmp 写回原数组对应区间。

这是典型的分治策略：划分产生高度为 $\log n$ 的递归树，每层合并的总操作数为 $n$，故时间复杂度为 $O(n \log n)$；空间复杂度 $O(n)$（归并需要辅助数组，递归栈深 $\log n$）。合并排序也是稳定排序——合并时 nums[i] <= nums[j] 才取左半区元素，相等元素保持原有次序。

参考仓库中的完整实现（C 版见merge_sort.c，Python 版见merge_sort.py），其核心 merge 逻辑如下：

void merge(int *nums, int left, int mid, int right) {
    // 左子数组区间为 [left, mid]，右子数组区间为 [mid+1, right]
    int tmpSize = right - left + 1;
    int *tmp = (int *)malloc(tmpSize * sizeof(int));
    int i = left, j = mid + 1, k = 0;
    // 两半都还有元素时，取较小者写入 tmp
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // 将剩余元素复制到 tmp
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= right) tmp[k++] = nums[j++];
    // 写回原数组
    for (k = 0; k < tmpSize; ++k)
        nums[left + k] = tmp[k];
    free(tmp);
}

编码要点：中点建议用 mid = left + (right - left) / 2 防止溢出；合并时注意 tmp 的索引 k 与 nums 区间起点 left 的偏移关系（nums 区间为 [left, right]，tmp 区间为 [0, right - left]，参见合并排序文档）。若熟悉链表，归并排序还可将空间复杂度优化到 $O(1)$：划分阶段用迭代替代递归省去栈帧，合并阶段仅靠改指针完成。

2.2 用计数排序排列整数数组

题目要求：给定整数数组 nums 和非负整数 $K$，数组中每个元素都在 $0 \sim K$ 之间。实现计数排序，按非递减顺序写回 nums 并返回，禁止用元素间的大小比较决定顺序，也不能调用库函数。

解题提示拆解：

1. 元素值可直接作为计数数组的索引——这正是「不比较大小」的关键：用元素值做下标，天然有序；
2. 第一遍扫描 nums，令 counter[nums[i]]++ 统计每个数值的出现次数；
3. 从 0 到 $K$ 扫描计数数组，数值 x 出现多少次，就向 nums 中连续写入多少个 x。

这一步得到的其实已经是有序结果，其正确性源于计数数组的索引天然有序。参考counting_sort.c 中的 countingSortNaive：

void countingSortNaive(int nums[], int size) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int i = 0; i < size; i++)
        if (nums[i] > m) m = nums[i];
    // 2. 统计各数字的出现次数
    int *counter = calloc(m + 1, sizeof(int));
    for (int i = 0; i < size; i++)
        counter[nums[i]]++;
    // 3. 遍历 counter，按出现次数依次填入 nums
    int i = 0;
    for (int num = 0; num < m + 1; num++)
        for (int j = 0; j < counter[num]; j++, i++)
            nums[i] = num;
    free(counter);
}

进阶思考：若输入是对象（例如按价格排序的商品），上述「简单实现」只能得到价格序列，丢失了对象本身。仓库还提供了完整实现 countingSort：先对 counter 求前缀和，令 prefix[num] - 1 表示 num 在结果数组 res 中最后一次出现的位置，再倒序遍历原数组，每放置一个元素就将对应前缀和减 1。倒序遍历保证相等元素按原有先后次序进入 res，因此完整版是稳定排序，而正序遍历虽结果相同但不稳定。

复杂度与局限：计数排序时间复杂度 $O(n+m)$、空间复杂度 $O(n+m)$。使用前须确认：数据必须是非负整数（负数可先整体加常数平移，排完再移回）；且数据范围 $m$ 不能过大，否则空间开销失控（详见计数排序文档）。本题给定 $K$，正好把 $m$ 限制在 $K$ 以内，可直接用 counter 数组长度为 $K+1$。

三、从练习题到源码：验证与深化

练习题与章节正文、仓库源码形成了完整的「理论 — 习题 — 实现」闭环，建议按以下路径对照学习：

1. 先读排序章節練習題自测，再看各章正文：選擇排序、泡沫排序、合併排序、計數排序、基數排序；
2. 对照 C 语言源码验证推演结果：selection_sort.c、bubble_sort.c、merge_sort.c、counting_sort.c、radix_sort.c；
3. 仓库在 codes/ 下为 Python、Java、C++、Go、Rust、TypeScript 等十余种语言提供了对应实现，可在本地运行 Driver Code 观察排序过程，例如直接运行 merge_sort.c 或 counting_sort.c 的主函数观察输出。

记忆要点速查：

算法	时间复杂度	空间复杂度	稳定性	一轮结束后的「确定位」
选择排序	$O(n^2)$	$O(1)$	不稳定	未排序区间最小值置于前端
冒泡排序	$O(n^2)$，带 flag 可至 $O(n)$	$O(1)$	稳定	最大值冒泡至末尾
归并排序	$O(n \log n)$	$O(n)$	稳定	两个有序半区合并
计数排序	$O(n + m)$	$O(n + m)$	可稳定（倒序填充）	全部元素一次归位
基数排序	$O((n + d)k)$	$O(n + d)$	依赖内层计数排序	按当前位有序

其中基数排序之所以要求「从最低位开始逐位排序」，是因为后一轮会覆盖前一轮的结果，而数字的高位优先级高于低位（参见基数排序文档）。

四、总结

本练习集覆盖了排序学习的三个核心层次：手动推演（理解每轮不变式）、性质辨析（稳定性的成因与差异）、动手实现（分治与统计两种非比较思路）。掌握了这些，你不仅能独立完成 LeetCode 912 这类题目，还能在真实场景中根据数据特征（是否含负数、范围大小、是否要求稳定）正确选择排序算法——这正是排序章节期望达成的能力目标。