计数排序算法原理与实现详解-云帆数科

1. 计数排序算法概述计数排序Counting Sort是一种非比较型的整数排序算法由Harold H. Seward于1954年提出。与基于比较的排序算法如快速排序、归并排序不同计数排序通过统计元素出现次数来实现排序这使得它在特定场景下能够突破O(nlogn)的时间复杂度下限。1.1 核心思想解析计数排序的核心原理可以概括为三个关键步骤统计数组中每个值为i的元素出现的次数存入计数数组C的第i项对所有的计数累加从C中的第一个元素开始每一项和前一项相加反向填充目标数组将每个元素i放在新数组的第C[i]项每放一个元素就将C[i]减去1这种方法的精妙之处在于利用了输入数据的整数特性通过直接计算元素的位置来实现排序完全避免了元素间的比较操作。关键特性当输入元素是n个0到k之间的整数时计数排序的时间复杂度为O(nk)。由于它不是基于比较的排序算法因此不受Ω(nlogn)下限的限制。2. 算法实现细节2.1 基础实现步骤下面我们用C展示计数排序的标准实现void countingSort(int arr[], int n) { // 1. 找出数组中的最大值 int max_val arr[0]; for (int i 1; i n; i) { if (arr[i] max_val) { max_val arr[i]; } } // 2. 创建计数数组并初始化 int count[max_val 1] {0}; // 3. 统计每个元素出现次数 for (int i 0; i n; i) { count[arr[i]]; } // 4. 累加计数数组 for (int i 1; i max_val; i) { count[i] count[i-1]; } // 5. 创建临时数组存储排序结果 int output[n]; // 6. 反向填充目标数组保证稳定性 for (int i n-1; i 0; i--) { output[count[arr[i]]-1] arr[i]; count[arr[i]]--; } // 7. 将结果拷贝回原数组 for (int i 0; i n; i) { arr[i] output[i]; } }2.2 关键参数分析实现中有几个关键参数需要特别注意计数数组大小必须设置为max_val1因为数组下标从0开始反向填充从后向前遍历原数组可以保证排序的稳定性相同元素的相对位置不变累加计数这一步将计数转换为位置索引是算法的核心所在2.3 边界条件处理实际应用中需要考虑几种特殊情况包含负数的情况可以通过整体偏移处理元素值范围过大的情况当k远大于n时空间效率会很低空数组输入需要单独处理避免越界3. 算法性能分析3.1 时间复杂度分解计数排序的时间复杂度可以从以下几个部分分析找出最大值O(n)初始化计数数组O(k)统计元素出现次数O(n)累加计数数组O(k)反向填充O(n)结果拷贝O(n)总时间复杂度为O(nk)。当kO(n)时算法达到线性时间复杂度。3.2 空间复杂度算法需要额外的计数数组O(k)输出数组O(n)因此空间复杂度为O(nk)。这是计数排序的主要缺点特别是当k很大时。3.3 稳定性分析标准实现的计数排序是稳定的这是因为相同元素的计数是累加的反向填充保证了后出现的元素会被放在更后面的位置每次放置后计数递减确保了位置唯一性4. 实际应用场景4.1 适用场景计数排序在以下场景表现优异数据范围不大k与n在同一数量级元素为非负整数或可映射为非负整数需要稳定排序的情况数据量较大但取值范围集中的场景典型应用包括学生成绩排序百分制年龄统计排序像素值排序小范围整数排序4.2 不适用场景以下情况不适合使用计数排序数据范围很大kn元素为浮点数除非能精确离散化内存受限的环境需要原地排序的情况5. 算法优化与变种5.1 负数处理方案处理包含负数的数组时可以通过偏移将所有数转换为非负数// 找出最小值和最大值 int min_val arr[0], max_val arr[0]; for(int i1; in; i) { if(arr[i] min_val) min_val arr[i]; if(arr[i] max_val) max_val arr[i]; } // 计算偏移量 int offset -min_val; // 调整计数数组大小 int count[max_val offset 1] {0}; // 后续步骤类似访问元素时加上offset5.2 空间优化版本可以通过以下方式减少空间使用不使用输出数组直接修改原数组失去稳定性当k很大但实际不同值很少时使用哈希表代替数组5.3 基数排序中的应用计数排序是基数排序的核心组件。在基数排序中我们按位进行计数排序void radixSort(int arr[], int n) { int max_val *max_element(arr, arrn); // 对每一位进行计数排序 for (int exp 1; max_val/exp 0; exp * 10) { countingSortByDigit(arr, n, exp); } }6. 常见问题与解决方案6.1 内存不足问题当k值很大时计数数组可能占用过多内存。解决方案使用更紧凑的数据结构如位图考虑其他排序算法分批处理数据6.2 浮点数排序处理浮点数时需要特别注意确定合适的小数精度将浮点数转换为整数乘以10^dd为小数位数处理可能的精度损失6.3 稳定性保持如果需要保持稳定性但内存受限可以使用链表存储相同值的元素或记录原始位置信息7. 与其他排序算法对比7.1 与快速排序比较特性计数排序快速排序时间复杂度O(nk)O(nlogn)平均空间复杂度O(nk)O(logn)稳定性稳定不稳定适用数据整数范围小通用7.2 与桶排序关系计数排序可以看作桶排序的特殊情况每个桶只装相同值的元素桶的数量等于数据范围省去了桶内排序的步骤8. 实际编码注意事项边界检查始终验证输入数组是否为空内存分配对于大数组考虑动态内存分配类型安全确保数组元素类型与索引兼容性能测试对于特定数据集实测比理论分析更重要// 改进的安全版本 void safeCountingSort(vectorint arr) { if(arr.empty()) return; // 使用vector避免栈溢出 int max_val *max_element(arr.begin(), arr.end()); vectorint count(max_val 1, 0); // ...其余步骤相同 }9. 扩展应用场景9.1 统计频次计数排序的自然延伸就是频率统计vectorint getFrequency(const vectorint arr) { if(arr.empty()) return {}; int max_val *max_element(arr.begin(), arr.end()); vectorint freq(max_val 1, 0); for(int num : arr) { freq[num]; } return freq; }9.2 数据压缩对于重复值多的数据计数排序的结果可以用于压缩存储(值出现次数)对比原始数据占用更少空间9.3 滑动窗口统计在滑动窗口问题中计数数组可以高效维护窗口内元素的统计信息。计数排序展示了算法设计中的一个重要原则利用问题本身的特殊性质这里是整数特性可以突破通用算法的性能限制。虽然它有其局限性但在适合的场景下它的效率是其他算法难以匹敌的。理解计数排序不仅是为了掌握一种排序方法更是为了培养这种针对问题特性设计专用算法的重要思维方式。

企业数字化 ERP 产品动态

相关推荐

C++核心哲学与内存模型深度解析

1. 从《程序员自我修养》看C的核心哲学作为一本深入探讨编程本质的经典著作，《程序员自我修养》第7章对C语言的剖析让我重新审视了这门已有40年历史的语言。很多人把C视为带类的C，但经过多年实践后我才真正理解——C本质上是一门多范式编程语言&#xff… · 2026/11/5 10:42:33

cpr 1.3.0 工程实践：C++ HTTP 封装与 Session 复用

简介：cpr-1.3.0 是面向 C 开发者的预编译 HTTP 客户端库文件包，基于 C Requests 项目封装 libcurl，适合需要在 VS2015 环境中快速接入网络请求、又不想从源码编译依赖的开发者。包内共 27 个文件，以 21 个头文件和 4 个 lib、2 个… · 2026/11/5 11:03:52

Univer SDK：面向B端的富文档协同引擎与可编辑表格实现

1. 项目概述：Univer 是什么，它解决的不是“又一个表格工具”问题Univer 这个名字乍一听容易让人联想到“universe”（宇宙），但实际它是一个开源的、面向开发者的富文档协同引擎。它不是一款直接面向终端用户销售的 SaaS… · 2026/11/5 7:52:22

基于Hadoop+Spark的民宿智能推荐系统设计与实现

1. 项目概述：大数据时代的民宿智能推荐这个毕业设计项目融合了当前大数据领域最主流的技术栈，构建了一个完整的民宿推荐系统解决方案。作为一名长期从事大数据系统开发的工程师，我认为这个选题非常贴合实际应用场景——随着旅游业的复苏和共享… · 2026/11/5 14:59:25

ADS122U04IPWR+STM32F427ZI工业级温度测量信号链设计

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 14:10:41

UART接口24位ADC搭配RS485，解决远距离温度监控难题

UART接口24位ADC搭配PIC18F46K22的RTD与热电偶测温实践

GD32E10x官方例程入门：从GPIO点灯到串口调试

简介：这份GD32E10x系列官方例程面向嵌入式硬件与单片机开发者，基于ARM Cortex-M3内核，汇集兆易创新GD32E10x的示例代码，适合工业控制、消费电子、通信设备等场景的学习、验证与二次开发。压缩包共935个文件，约11.16MB&… · 2026/11/5 13:52:29

基于Django的运维平台实战：资产、发布、巡检、告警一体化

简介：这份资源是一套基于Django框架开发的运维平台源码，面向具备Python基础、希望了解Web运维系统实现思路的开发者与运维人员，可用于学习主机管理、服务监控、日志查看、任务调度、权限控制、资源统计、脚本执行与故障告警等常见运维模块的落… · 2026/11/5 13:49:27

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时，Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南：从原理到部署微调的全链路路线

提到大模型的系统性入门，我先说个结论：这事真不难，难的是资料太散、路线太多，今天这个框架明天那个工具，新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师，我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码，在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

计数排序算法原理与实现详解

相关推荐

了解更多？预约专属演示