041计数排序 - O(n+k)的非比较排序

计数排序 - O(nk)的非比较排序041揭秘计数排序停止比较的算法 5W1H 发明者故事Who何人- 发明者是谁发明者哈罗德·西沃德Harold H. Seward背景西沃德是美国计算机工程师在麻省理工学院MIT林肯实验室工作专注于早期数字计算机的软件开发。他在博士论文《数字计算机中的信息排序》“Information Sorting in the Application of Electronic Digital Computers to Business Operations”1954年中首次系统描述了计数排序算法。当时的处境1954年计算机开始进入商业领域。西沃德在研究如何将计算机用于商业数据处理工资单、库存管理等时发现很多实际数据的值域范围有限如年龄0-100、月份1-12、等级A-F可以利用这一特性设计比O(n log n)更快的排序算法。When何时- 什么时候发明的时间1954年发表于MIT技术报告时代背景IBM 701和702商用计算机开始进入企业计算机开始从军事科学计算转向商业数据处理信息论香农1948和运筹学蓬勃发展比较排序的O(n log n)下界已被认识到研究者开始探索绕过它的方法Where何地- 在哪里发明的地点美国麻省理工学院林肯实验室马萨诸塞州列克星敦环境林肯实验室是MIT为美国军方设立的研究机构专注于雷达系统和早期计算机技术。西沃德在此研究计算机在商业和军事数据处理中的应用接触了大量需要排序的实际问题。What何事- 发明了什么算法计数排序Counting Sort核心概念不通过比较而是统计每个值出现的次数再利用计数信息直接确定每个元素在输出中的位置关键变体基础版统计每个值的出现次数然后按顺序输出不稳定但简单稳定版对计数数组做前缀和然后从后往前扫描原数组填入输出稳定适合作为基数排序的子例程Why何因- 为什么发明要解决的问题突破比较排序下界任何基于比较的排序算法最坏情况都需要Ω(n log n)次比较但如果允许使用值的具体信息如整数值域可以做得更快商业数据特性实际商业数据往往值域有限员工等级1-5、月份1-12、考试分数0-100使用O(nk)算法更合适作为基数排序的基础计数排序是实现稳定基数排序的关键子例程当时的挑战需要O(k)额外空间存储计数数组若值域k远大于n则不经济只适用于整数或可映射为整数的数据不适用于浮点数或字符串的直接计数稳定版需要精确的实现从后往前扫描才能保证稳定性动机西沃德的关键洞察是如果我们知道数据的值域就不需要询问元素之间的大小关系——我们可以直接数每个值出现多少次然后按顺序输出。这彻底绕过了比较排序的信息论下界。How何果- 如何实现有什么影响实现思路稳定版扫描数组找出最大值max和最小值min确定值域kmax-min1分配计数数组count[k]统计每个值的出现次数对count做前缀和count[i] count[i-1]此时count[v-min]表示值v的元素总数即v的最后一个位置1从后往前扫描原数组将arr[i]放入输出的count[arr[i]-min]-1处然后count[arr[i]-min]–技术方案原数组: [3, 1, 4, 1, 5, 9, 2, 6, 5] 值域1-9 计数: count[1]2, count[2]1, count[3]1, count[4]1, count[5]2, count[6]1, count[9]1 前缀和: count[1]2, count[2]3, count[3]4, count[4]5, count[5]7, count[6]8, count[7]8, count[8]8, count[9]9 从后往前放置得到: [1,1,2,3,4,5,5,6,9]历史影响计数排序是三大线性排序算法计数、基数、桶排序之一是基数排序实现中必不可少的稳定子排序在计算机图形学中用于直方图计算和颜色量化Linux内核的调度器使用O(1)调度其优先级队列本质上借鉴了计数思想现代编译器对小整数类型如uint8_t数组排序时会自动选择计数排序今天的使用对已知值域的整数数据排序年龄、分数、字符ASCII值基数排序的子例程按每一位进行稳定排序计算词频、字符频率实质上就是计数操作 自然语言需求定义需求名称实现计数排序包含基础版和稳定版两个变体功能需求用精确的中文描述基础计数排序统计各值出现次数按顺序填回原数组输入整数数组、长度、值域最小值min_val、值域最大值max_val操作分配count数组统计每个值的次数然后按从小到大顺序将值重新填入原数组输出原地排序实际使用count数组作为辅助时间O(nk)空间O(k)稳定计数排序通过前缀和确定每个元素的精确位置保证稳定性输入整数数组、长度、值域最小值min_val、值域最大值max_val、输出数组操作统计→前缀和→从后往前放置确保相等元素保持原有相对顺序输出排序结果写入输出数组需要O(nk)辅助空间原数组不变约束条件时间复杂度O(nk)其中k为值域大小max_val - min_val 1空间复杂度O(nk)稳定版O(k)基础版min_val和max_val由调用者提供或函数内部自动扫描确定若k远大于n函数应拒绝执行并返回错误验收标准必须可验证编号测试场景自然语言描述预期结果验证方式1对[3,1,4,1,5,9,2,6,5]进行基础计数排序[1,1,2,3,4,5,5,6,9]memcmp比较结果数组2对同一数组进行稳定计数排序结果与基础版相同memcmp验证3稳定性验证[(3,‘a’),(1,‘b’),(3,‘c’)]值相等时顺序不变(1,‘b’),(3,‘a’),(3,‘c’)检查原始标记顺序4值域检验min1,max9拒绝超出值域的元素函数返回错误码-1检查返回值5全相同元素[5,5,5,5]排序[5,5,5,5]is_sorted检验6单元素[7]排序[7]数组内容检验7大数组1000个范围0-255的随机数排序is_sorted返回true遍历检查AI 生成提示基于以上需求和验收标准用标准C语言实现两种计数排序变体。 要求 1. 使用标准C99gcc -Wall无警告 2. counting_sort_basic(arr, n, min_val, max_val)返回int0成功-1值域过大 3. counting_sort_stable(arr, n, min_val, max_val, output)返回int 4. 完整内存管理malloc/free配对 5. 代码必须有详细中文注释特别是前缀和和从后往前扫描的原理 6. 测试框架使用 tests_passed/tests_failed 计数器 7. main返回 tests_failed 0 ? 1 : 0 核心函数 - counting_sort_basic(arr, n, min_val, max_val) - 基础版 - counting_sort_stable(arr, n, min_val, max_val, output) - 稳定版 - is_sorted(arr, n) - 有序性检验 - print_array(label, arr, n) - 打印数组 C语言实现文件对应文件:counting_sort.c编译运行:gcc-stdc99-Wall-ocounting_sort_test counting_sort.c ./counting_sort_test核心函数:counting_sort_basic(arr, n, min_val, max_val)- 基础计数排序counting_sort_stable(arr, n, min_val, max_val, output)- 稳定计数排序is_sorted(arr, n)- 有序性检验