Hello 算法排序篇习题精解稳定性推演与归并/计数排序编程实战【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇以《Hello 算法》英文版排序章配套练习 exercises.md 为骨架逐一拆解其四组核心习题选择排序与冒泡排序的前几轮轨迹推演、相等元素的相对次序稳定性辨析、面向固定长度 8 位学号的计数排序与基数排序选型以及归并排序与受限整数区间计数排序两道编程上机题。文章在保留全部习题与参考答案的同时结合仓库 en/codes 中 Python 等多语言的真实实现与测试代码讲清每一步的底层机制与复杂度依据。读完后你将能独立完成这类“手写排序算法 手推排序过程 判断稳定性与适用场景”的综合练习并把抽象结论落实到可运行的代码上。一、习题文件定位与阅读方法练习文件位于 en/docs/chapter_sorting/exercises.md它与同目录下的 selection_sort.md、bubble_sort.md、merge_sort.md、counting_sort.md、radix_sort.md 等正文页面配套属于“习题 参考解答”型文档正文里用可折叠块??? success Answer/??? tip Hints隐藏答案先做后看效果最佳。练习涉及的所有算法都在仓库中提供了对应实现与驱动代码例如 Python 版位于 en/codes/python/chapter_sorting/含selection_sort.py、bubble_sort.py、merge_sort.py、counting_sort.py、radix_sort.py同一目录下的章节代码还同步覆盖 Java、C、C、Go、JS、TS、C#、Swift、Rust 等语言Go 额外带有*_test.go单元测试如 merge_sort_test.go、counting_sort_test.go可用于对照验证手写实现的结果。二、概念演练一排序前几轮的“轨迹推演”题目给定数组[4, 2, 5, 1, 3]要求分别推演升序排序下的选择排序与冒泡排序过程。2.1 选择排序前两轮选择排序的核心策略是每轮从“未排序区间”中选出最小元素与未排序区间的首个元素交换。参考实现见 selection_sort.py 中的selection_sort()外层循环维护未排序区间[i, n-1]内层循环用k记录最小元素下标结束后与nums[i]交换。轮次数组说明1[1, 2, 5, 4, 3]最小元素 1原下标 3与首元素 4 交换2[1, 2, 5, 4, 3]未排序区间内最小值为 2它恰好位于下标 1无需交换因此前两轮之后下标 0 与下标 1 两个位置被固定后续轮次只需在[5, 4, 3]范围内继续找最小元素。这与正文 selection_sort.md 中“进行 $n-1$ 轮选择与交换后前 $n-1$ 个元素有序剩余一个必为最大元素”的描述一致。2.2 冒泡排序第一轮冒泡排序的核心策略是每轮从左到右比较相邻元素左 右则交换使本轮区间内的最大元素“冒泡”到右端。参考实现见 bubble_sort.py 中的bubble_sort()其判断条件严格为nums[j] nums[j1]。对[4, 2, 5, 1, 3]从头依次比较4 与 24 2交换→[2, 4, 5, 1, 3]4 与 54 5不交换5 与 15 1交换→[2, 4, 1, 5, 3]5 与 35 3交换→[2, 4, 1, 3, 5]第一轮共发生3 次交换最大元素 5 已到达数组末尾最后一个位置被固定。冒泡排序这种“相邻逆序才交换”的行为正是它天然具备稳定性的根源详见下一节。延伸仓库中还提供了加入flag标志的优化版本bubble_sort_with_flag()——若某一轮未发生任何交换则提前结束。依据 bubble_sort.md该优化可将已有序输入的最佳时间复杂度从 $O(n^2)$ 降为 $O(n)$这种“提前退出”思想值得在练习中对比验证。三、概念演练二相等元素能否保持相对次序稳定性题目给定数组 $[2_a, 2_b, 1]$其中 $2_a$ 与 $2_b$ 数值相等下标标记其原始先后次序考查两算法第一轮后二者相对次序是否改变。3.1 选择排序相对次序被破坏第一轮选择排序选出最小元素 1下标 2将其与首元素 $2_a$ 交换得到 $[1, 2_b, 2_a]$。因为 $2_a$ 越过 $2_b$ 移到了后方相等元素的相对次序发生了改变。根源在于选择排序的交换并非“相邻对调”当最小元素位于某个相等元素右侧时交换会把左侧的相等元素整体向右搬移。正文 selection_sort.md 用下图给出了这一不稳定性的直观示例即元素nums[i]可能被交换到与其相等元素的右侧。从算法特性表selection_sort.md可知选择排序时间复杂度 $O(n^2)$ 且非自适应无论输入有序与否轮数不变、空间复杂度 $O(1)$、不稳定。3.2 冒泡排序相对次序被保留冒泡排序第一轮先比较 $2_a$ 与 $2_b$二者相等由于交换条件为“左 右”相等元素不交换随后比较 $2_b$ 与 1 并交换得到 $[2_a, 1, 2_b]$。$2_a$ 仍位于 $2_b$ 之前相对次序未变。因此结论是冒泡排序只把“左严格大于右”的相邻对交换相等元素保持原次序是稳定排序。对应特性见 bubble_sort.md$O(n^2)$、自适应带 flag 版本、$O(1)$ 空间、稳定。3.3 两问连起来说明了什么这个例子直观揭示了两点“效率”与“稳定”是独立维度同为 $O(n^2)$ 的简单排序选择排序不稳定而冒泡排序稳定差异完全由“是否仅相邻比较交换”决定。稳定性在真实业务中的价值正文总结 summary.md 的 QA 举了多级排序的例子——先按姓名排序得到(A,180) (B,185) (C,170) (D,170)再按身高排序时若算法不稳定可能把两名同身高学生的次序打乱破坏第一级的姓名顺序。因此在需要“主键 次键”复合排序的场景如先班级后学号必须选用稳定算法归并排序、插入排序、完整版计数排序等。四、概念演练三8 位学号的计数排序与基数排序选型题目设定某校需为大量“恰好 8 位数字”的学号排序考查两种非比较排序的差异。4.1 从最低位开始需要多少轮基数排序从最低有效位LSD向最高位逐位进行“稳定分组”。8 位学号即8 轮每轮仅按当前位的取值 0–9 归组。参考实现见 radix_sort.pyradix_sort()通过exp从 1 倍增到 $10^7$覆盖最高位每一轮调用counting_sort_digit(nums, exp)digit()用(num // exp) % 10取出指定位数字传exp而非位数 $k$ 可避免重复的幂运算。关键在于counting_sort_digit内部只为十进制数字开辟长度为 10 的计数桶且通过“反向遍历 前缀和”保证每轮分组是稳定的这是多轮叠加后整体有序的前提。4.2 直接按 8 位整数做计数排序为何浪费计数排序用“元素值直接作下标”。若把完整 8 位学号当作整数索引计数数组需覆盖 $[0, 10^8)$即约1 亿个条目而实际在校学生只是其中极小一部分取值绝大多数计数条目恒为 0内存与初始化开销极大。这对应正文 counting_sort.md 的核心前提计数排序适合“数据量大但取值范围小”的情形。4.3 选型结论基数排序更合适学号满足两个关键特征——位数固定8、每位取值空间小0–9这恰好是基数排序的理想输入只需8 轮、每轮处理 $n$ 个元素与 10 个桶复杂度约为 $O(8 \times (n 10))$而直接按完整学号计数则需为大量“从不出现”的取值预留条目。正如正文 summary.md 所归纳计数排序适用于数据量大但取值区间有限、且数据可转为非负整数的场景它是桶排序在整数数据上的特例基数排序要求数据可表示为定长数字通过逐位排序完成整体排序。工程化提醒若数据为等长字符串/定长编码数字基数排序同样适用若学号位数不固定则需先补齐前导零这是使用基数排序时必须在代码中保证的前提。五、上机编程一手写归并排序排序数组题目给定整数数组nums不使用语言内置排序函数自行实现归并排序将元素按非递减序排列后返回。提示原文档给出长度不超过 1 的区间天然有序取区间中点将数组二分递归排序左右两半用双指针合并两个有序子区间并将结果写回原数组。5.1 参考答案对照仓库实现下面实现与 en/codes/python/chapter_sorting/merge_sort.py 中的merge()与merge_sort()完全同构def merge(nums: list[int], left: int, mid: int, right: int): 合并左子区间 [left, mid] 与右子区间 [mid1, right] tmp [0] * (right - left 1) # 临时数组存放合并结果 i, j, k left, mid 1, 0 # 双指针每次取较小者放入 tmp while i mid and j right: if nums[i] nums[j]: tmp[k], i nums[i], i 1 else: tmp[k], j nums[j], j 1 k 1 # 拷贝左右区间各自剩余的元素 while i mid: tmp[k], i, k nums[i], i 1, k 1 while j right: tmp[k], j, k nums[j], j 1, k 1 # 将临时数组写回原数组对应区间 for k in range(len(tmp)): nums[left k] tmp[k] def merge_sort(nums: list[int], left: int, right: int): 归并排序分治 if left right: # 子数组长度为 1 时终止递归 return mid (left right) // 2 # 计算中点 merge_sort(nums, left, mid) # 递归排序左半 merge_sort(nums, mid 1, right) # 递归排序右半 merge(nums, left, mid, right) # 合并两半仓库中对应驱动代码以nums [7, 3, 2, 6, 0, 1, 5, 4]为例调用并打印结果若把答案函数按此方式封装成sort_array(nums)并返回nums即可直接承接“排序后返回数组”的题目要求。5.2 关键机制与自检要点取等号保稳定合并时比较条件为nums[i] nums[j]相等时优先取左半元素因此归并排序是稳定排序左子区间元素不会跑到相等右子区间元素之后。复杂度依据依据正文 merge_sort.md 及总结 summary.md归并排序体现分治策略时间复杂度稳定为 $O(n \log n)$每次合并需辅助数组空间复杂度 $O(n)$对链表可优化至 $O(1)$。验证手段Go 版提供了单元测试 merge_sort_test.go可对照其断言检查边界输入空数组、单元素、含重复值等。六、上机编程二限定区间 [0, K] 的手写计数排序题目给定整数数组nums与非负整数 $K$nums中每个元素均位于 $[0, K]$。实现计数排序将结果按非递减序写回nums并返回nums。禁止通过比较确定次序也禁止调用内置排序函数。提示原文档给出元素取值均在 0 到 K 之间可直接用元素值作为计数数组下标遍历nums一次在对应计数位置自增随后从 0 扫到 K若某值 $x$ 出现若干次就向nums连续写入若干次 $x$。6.1 参考答案一朴素直写版该思路对应 counting_sort.py 中的counting_sort_naive()直接把“计数结果按序回填”适合题目“元素为整数、只需按值排序”的约束def counting_sort_exercise(nums: list[int], K: int): # 1. 统计每个取值出现的次数counter[x] 表示 x 的出现次数 counter [0] * (K 1) for num in nums: counter[num] 1 # 2. 扫描取值 0..K按出现次数连续回填 nums i 0 for num in range(K 1): for _ in range(counter[num]): nums[i] num i 1 return nums题面直接给出上界 $K$因此无需像仓库版本那样先m max(nums)探测上界再建counter [0] * (m 1)若 $K$ 未知可自行补一步求最大值。整段代码没有任何元素间的大小比较满足“禁止通过比较排序”的要求也没有调用内置排序。6.2 参考答案二前缀和稳定版进阶朴素版无法处理“对象/记录”输入只输出值的有序排列。若需要保持相等元素的相对次序例如按成绩排序学生记录则要用仓库中counting_sort()的完整实现先求counter的前缀和把“出现次数”转为“末位下标”再倒序遍历nums把元素放入结果数组res最后用res覆盖原数组。依据正文 counting_sort.mdprefix[num] - 1恰是元素num在结果中的最后一个下标倒序放置 前缀和递减使其成为稳定排序。6.3 复杂度与适用前提时间复杂度 $O(n K)$建计数与回填各一次空间复杂度 $O(K)$计数数组均不依赖元素间比较。适用前提取值必须是非负整数且范围 $K$ 相对 $n$ 不大若 $K$ 远大于 $n$如 $10^8$ 量级计数数组会大量闲置——这正是上一节“8 位学号直接计数”被否定的原因。用 counting_sort_test.go 一类测试即可覆盖含大量重复值与 0 的输入验证回填逻辑不越界、不遗漏。七、把练习扩展到多语言与后续学习路径《Hello 算法》仓库的特点是多语言一致中文版 codes、docs 与英文版 en/codes、en/docs 目录结构一一对应。本练习涉及的排序算法在每个语言目录下都有同名文件算法仓库相对路径以英文版 Python 为例语言覆盖选择排序en/codes/python/chapter_sorting/selection_sort.pyPython/Java/C/C/C#/Go/JS/TS/Swift/Rust/Kotlin/Dart/Ruby 等冒泡排序en/codes/python/chapter_sorting/bubble_sort.py同上均含 flag 优化版归并排序en/codes/python/chapter_sorting/merge_sort.py同上Go 附merge_sort_test.go计数排序en/codes/python/chapter_sorting/counting_sort.py朴素版 前缀和稳定版基数排序en/codes/python/chapter_sorting/radix_sort.py内部复用按位计数排序运行验证方式多数文件自带__main__驱动代码直接在本地解释器执行该文件即可观察排序前后输出如python en/codes/python/chapter_sorting/merge_sort.py。学习建议先在纸上完成第一节的概念推演并对比参考答案再对照源码手写实现最后用第 2 节练习 3计数 vs 基数的选型结论到 sorting_algorithm.md 与 summary.md 的对比表中验证“时间复杂度、空间复杂度、稳定性、是否原地、是否自适应”五个维度完成从单点习题到算法全景的知识闭环。核心结论回顾稳定性的关键在“是否相邻对调”而非“是否 $O(n^2)$”计数排序以值域换时间、基数排序以位数为轮数二者用“取值范围/位数”这类非比较信息打破 $\Omega(n \log n)$ 的比较排序下界而上机题的两份参考答案直接复用仓库中 merge_sort.py 与 counting_sort.py 的成熟写法可放心对照扩展。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Hello 算法排序篇习题精解：稳定性推演与归并/计数排序编程实战
Hello 算法排序篇习题精解稳定性推演与归并/计数排序编程实战【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇以《Hello 算法》英文版排序章配套练习 exercises.md 为骨架逐一拆解其四组核心习题选择排序与冒泡排序的前几轮轨迹推演、相等元素的相对次序稳定性辨析、面向固定长度 8 位学号的计数排序与基数排序选型以及归并排序与受限整数区间计数排序两道编程上机题。文章在保留全部习题与参考答案的同时结合仓库 en/codes 中 Python 等多语言的真实实现与测试代码讲清每一步的底层机制与复杂度依据。读完后你将能独立完成这类“手写排序算法 手推排序过程 判断稳定性与适用场景”的综合练习并把抽象结论落实到可运行的代码上。一、习题文件定位与阅读方法练习文件位于 en/docs/chapter_sorting/exercises.md它与同目录下的 selection_sort.md、bubble_sort.md、merge_sort.md、counting_sort.md、radix_sort.md 等正文页面配套属于“习题 参考解答”型文档正文里用可折叠块??? success Answer/??? tip Hints隐藏答案先做后看效果最佳。练习涉及的所有算法都在仓库中提供了对应实现与驱动代码例如 Python 版位于 en/codes/python/chapter_sorting/含selection_sort.py、bubble_sort.py、merge_sort.py、counting_sort.py、radix_sort.py同一目录下的章节代码还同步覆盖 Java、C、C、Go、JS、TS、C#、Swift、Rust 等语言Go 额外带有*_test.go单元测试如 merge_sort_test.go、counting_sort_test.go可用于对照验证手写实现的结果。二、概念演练一排序前几轮的“轨迹推演”题目给定数组[4, 2, 5, 1, 3]要求分别推演升序排序下的选择排序与冒泡排序过程。2.1 选择排序前两轮选择排序的核心策略是每轮从“未排序区间”中选出最小元素与未排序区间的首个元素交换。参考实现见 selection_sort.py 中的selection_sort()外层循环维护未排序区间[i, n-1]内层循环用k记录最小元素下标结束后与nums[i]交换。轮次数组说明1[1, 2, 5, 4, 3]最小元素 1原下标 3与首元素 4 交换2[1, 2, 5, 4, 3]未排序区间内最小值为 2它恰好位于下标 1无需交换因此前两轮之后下标 0 与下标 1 两个位置被固定后续轮次只需在[5, 4, 3]范围内继续找最小元素。这与正文 selection_sort.md 中“进行 $n-1$ 轮选择与交换后前 $n-1$ 个元素有序剩余一个必为最大元素”的描述一致。2.2 冒泡排序第一轮冒泡排序的核心策略是每轮从左到右比较相邻元素左 右则交换使本轮区间内的最大元素“冒泡”到右端。参考实现见 bubble_sort.py 中的bubble_sort()其判断条件严格为nums[j] nums[j1]。对[4, 2, 5, 1, 3]从头依次比较4 与 24 2交换→[2, 4, 5, 1, 3]4 与 54 5不交换5 与 15 1交换→[2, 4, 1, 5, 3]5 与 35 3交换→[2, 4, 1, 3, 5]第一轮共发生3 次交换最大元素 5 已到达数组末尾最后一个位置被固定。冒泡排序这种“相邻逆序才交换”的行为正是它天然具备稳定性的根源详见下一节。延伸仓库中还提供了加入flag标志的优化版本bubble_sort_with_flag()——若某一轮未发生任何交换则提前结束。依据 bubble_sort.md该优化可将已有序输入的最佳时间复杂度从 $O(n^2)$ 降为 $O(n)$这种“提前退出”思想值得在练习中对比验证。三、概念演练二相等元素能否保持相对次序稳定性题目给定数组 $[2_a, 2_b, 1]$其中 $2_a$ 与 $2_b$ 数值相等下标标记其原始先后次序考查两算法第一轮后二者相对次序是否改变。3.1 选择排序相对次序被破坏第一轮选择排序选出最小元素 1下标 2将其与首元素 $2_a$ 交换得到 $[1, 2_b, 2_a]$。因为 $2_a$ 越过 $2_b$ 移到了后方相等元素的相对次序发生了改变。根源在于选择排序的交换并非“相邻对调”当最小元素位于某个相等元素右侧时交换会把左侧的相等元素整体向右搬移。正文 selection_sort.md 用下图给出了这一不稳定性的直观示例即元素nums[i]可能被交换到与其相等元素的右侧。从算法特性表selection_sort.md可知选择排序时间复杂度 $O(n^2)$ 且非自适应无论输入有序与否轮数不变、空间复杂度 $O(1)$、不稳定。3.2 冒泡排序相对次序被保留冒泡排序第一轮先比较 $2_a$ 与 $2_b$二者相等由于交换条件为“左 右”相等元素不交换随后比较 $2_b$ 与 1 并交换得到 $[2_a, 1, 2_b]$。$2_a$ 仍位于 $2_b$ 之前相对次序未变。因此结论是冒泡排序只把“左严格大于右”的相邻对交换相等元素保持原次序是稳定排序。对应特性见 bubble_sort.md$O(n^2)$、自适应带 flag 版本、$O(1)$ 空间、稳定。3.3 两问连起来说明了什么这个例子直观揭示了两点“效率”与“稳定”是独立维度同为 $O(n^2)$ 的简单排序选择排序不稳定而冒泡排序稳定差异完全由“是否仅相邻比较交换”决定。稳定性在真实业务中的价值正文总结 summary.md 的 QA 举了多级排序的例子——先按姓名排序得到(A,180) (B,185) (C,170) (D,170)再按身高排序时若算法不稳定可能把两名同身高学生的次序打乱破坏第一级的姓名顺序。因此在需要“主键 次键”复合排序的场景如先班级后学号必须选用稳定算法归并排序、插入排序、完整版计数排序等。四、概念演练三8 位学号的计数排序与基数排序选型题目设定某校需为大量“恰好 8 位数字”的学号排序考查两种非比较排序的差异。4.1 从最低位开始需要多少轮基数排序从最低有效位LSD向最高位逐位进行“稳定分组”。8 位学号即8 轮每轮仅按当前位的取值 0–9 归组。参考实现见 radix_sort.pyradix_sort()通过exp从 1 倍增到 $10^7$覆盖最高位每一轮调用counting_sort_digit(nums, exp)digit()用(num // exp) % 10取出指定位数字传exp而非位数 $k$ 可避免重复的幂运算。关键在于counting_sort_digit内部只为十进制数字开辟长度为 10 的计数桶且通过“反向遍历 前缀和”保证每轮分组是稳定的这是多轮叠加后整体有序的前提。4.2 直接按 8 位整数做计数排序为何浪费计数排序用“元素值直接作下标”。若把完整 8 位学号当作整数索引计数数组需覆盖 $[0, 10^8)$即约1 亿个条目而实际在校学生只是其中极小一部分取值绝大多数计数条目恒为 0内存与初始化开销极大。这对应正文 counting_sort.md 的核心前提计数排序适合“数据量大但取值范围小”的情形。4.3 选型结论基数排序更合适学号满足两个关键特征——位数固定8、每位取值空间小0–9这恰好是基数排序的理想输入只需8 轮、每轮处理 $n$ 个元素与 10 个桶复杂度约为 $O(8 \times (n 10))$而直接按完整学号计数则需为大量“从不出现”的取值预留条目。正如正文 summary.md 所归纳计数排序适用于数据量大但取值区间有限、且数据可转为非负整数的场景它是桶排序在整数数据上的特例基数排序要求数据可表示为定长数字通过逐位排序完成整体排序。工程化提醒若数据为等长字符串/定长编码数字基数排序同样适用若学号位数不固定则需先补齐前导零这是使用基数排序时必须在代码中保证的前提。五、上机编程一手写归并排序排序数组题目给定整数数组nums不使用语言内置排序函数自行实现归并排序将元素按非递减序排列后返回。提示原文档给出长度不超过 1 的区间天然有序取区间中点将数组二分递归排序左右两半用双指针合并两个有序子区间并将结果写回原数组。5.1 参考答案对照仓库实现下面实现与 en/codes/python/chapter_sorting/merge_sort.py 中的merge()与merge_sort()完全同构def merge(nums: list[int], left: int, mid: int, right: int): 合并左子区间 [left, mid] 与右子区间 [mid1, right] tmp [0] * (right - left 1) # 临时数组存放合并结果 i, j, k left, mid 1, 0 # 双指针每次取较小者放入 tmp while i mid and j right: if nums[i] nums[j]: tmp[k], i nums[i], i 1 else: tmp[k], j nums[j], j 1 k 1 # 拷贝左右区间各自剩余的元素 while i mid: tmp[k], i, k nums[i], i 1, k 1 while j right: tmp[k], j, k nums[j], j 1, k 1 # 将临时数组写回原数组对应区间 for k in range(len(tmp)): nums[left k] tmp[k] def merge_sort(nums: list[int], left: int, right: int): 归并排序分治 if left right: # 子数组长度为 1 时终止递归 return mid (left right) // 2 # 计算中点 merge_sort(nums, left, mid) # 递归排序左半 merge_sort(nums, mid 1, right) # 递归排序右半 merge(nums, left, mid, right) # 合并两半仓库中对应驱动代码以nums [7, 3, 2, 6, 0, 1, 5, 4]为例调用并打印结果若把答案函数按此方式封装成sort_array(nums)并返回nums即可直接承接“排序后返回数组”的题目要求。5.2 关键机制与自检要点取等号保稳定合并时比较条件为nums[i] nums[j]相等时优先取左半元素因此归并排序是稳定排序左子区间元素不会跑到相等右子区间元素之后。复杂度依据依据正文 merge_sort.md 及总结 summary.md归并排序体现分治策略时间复杂度稳定为 $O(n \log n)$每次合并需辅助数组空间复杂度 $O(n)$对链表可优化至 $O(1)$。验证手段Go 版提供了单元测试 merge_sort_test.go可对照其断言检查边界输入空数组、单元素、含重复值等。六、上机编程二限定区间 [0, K] 的手写计数排序题目给定整数数组nums与非负整数 $K$nums中每个元素均位于 $[0, K]$。实现计数排序将结果按非递减序写回nums并返回nums。禁止通过比较确定次序也禁止调用内置排序函数。提示原文档给出元素取值均在 0 到 K 之间可直接用元素值作为计数数组下标遍历nums一次在对应计数位置自增随后从 0 扫到 K若某值 $x$ 出现若干次就向nums连续写入若干次 $x$。6.1 参考答案一朴素直写版该思路对应 counting_sort.py 中的counting_sort_naive()直接把“计数结果按序回填”适合题目“元素为整数、只需按值排序”的约束def counting_sort_exercise(nums: list[int], K: int): # 1. 统计每个取值出现的次数counter[x] 表示 x 的出现次数 counter [0] * (K 1) for num in nums: counter[num] 1 # 2. 扫描取值 0..K按出现次数连续回填 nums i 0 for num in range(K 1): for _ in range(counter[num]): nums[i] num i 1 return nums题面直接给出上界 $K$因此无需像仓库版本那样先m max(nums)探测上界再建counter [0] * (m 1)若 $K$ 未知可自行补一步求最大值。整段代码没有任何元素间的大小比较满足“禁止通过比较排序”的要求也没有调用内置排序。6.2 参考答案二前缀和稳定版进阶朴素版无法处理“对象/记录”输入只输出值的有序排列。若需要保持相等元素的相对次序例如按成绩排序学生记录则要用仓库中counting_sort()的完整实现先求counter的前缀和把“出现次数”转为“末位下标”再倒序遍历nums把元素放入结果数组res最后用res覆盖原数组。依据正文 counting_sort.mdprefix[num] - 1恰是元素num在结果中的最后一个下标倒序放置 前缀和递减使其成为稳定排序。6.3 复杂度与适用前提时间复杂度 $O(n K)$建计数与回填各一次空间复杂度 $O(K)$计数数组均不依赖元素间比较。适用前提取值必须是非负整数且范围 $K$ 相对 $n$ 不大若 $K$ 远大于 $n$如 $10^8$ 量级计数数组会大量闲置——这正是上一节“8 位学号直接计数”被否定的原因。用 counting_sort_test.go 一类测试即可覆盖含大量重复值与 0 的输入验证回填逻辑不越界、不遗漏。七、把练习扩展到多语言与后续学习路径《Hello 算法》仓库的特点是多语言一致中文版 codes、docs 与英文版 en/codes、en/docs 目录结构一一对应。本练习涉及的排序算法在每个语言目录下都有同名文件算法仓库相对路径以英文版 Python 为例语言覆盖选择排序en/codes/python/chapter_sorting/selection_sort.pyPython/Java/C/C/C#/Go/JS/TS/Swift/Rust/Kotlin/Dart/Ruby 等冒泡排序en/codes/python/chapter_sorting/bubble_sort.py同上均含 flag 优化版归并排序en/codes/python/chapter_sorting/merge_sort.py同上Go 附merge_sort_test.go计数排序en/codes/python/chapter_sorting/counting_sort.py朴素版 前缀和稳定版基数排序en/codes/python/chapter_sorting/radix_sort.py内部复用按位计数排序运行验证方式多数文件自带__main__驱动代码直接在本地解释器执行该文件即可观察排序前后输出如python en/codes/python/chapter_sorting/merge_sort.py。学习建议先在纸上完成第一节的概念推演并对比参考答案再对照源码手写实现最后用第 2 节练习 3计数 vs 基数的选型结论到 sorting_algorithm.md 与 summary.md 的对比表中验证“时间复杂度、空间复杂度、稳定性、是否原地、是否自适应”五个维度完成从单点习题到算法全景的知识闭环。核心结论回顾稳定性的关键在“是否相邻对调”而非“是否 $O(n^2)$”计数排序以值域换时间、基数排序以位数为轮数二者用“取值范围/位数”这类非比较信息打破 $\Omega(n \log n)$ 的比较排序下界而上机题的两份参考答案直接复用仓库中 merge_sort.py 与 counting_sort.py 的成熟写法可放心对照扩展。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
