教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载计数排序Counting Sort是一种基于键值范围而非比较的线性时间排序算法它以空间换时间在输入元素取值范围 k 远小于元素个数 n 时极具效率。本文以 code/sorting/src/counting_sort/README.md 为核心骨架结合 Cosmos 仓库中 11 种语言的源码实现系统讲解计数排序的算法思想、运行步骤、复杂度分析以及各语言实现中的关键细节读完即可理解并复现完整可运行的计数排序代码。计数排序的核心思想根据 README 的定义计数排序是一种时间上非常高效、空间上相对低效的算法它基于键值落在特定范围内这一前提。其基本思路是计数统计数组中具有不同键值key value的对象个数——这一步类似于哈希hashing的思想把元素值当作下标直接映射到计数数组定位通过一些算术运算前缀和累加计算每个对象在输出序列中应处的位置输出根据位置信息将元素回填到输出数组得到有序序列。与传统基于比较的排序如快速排序、归并排序不同计数排序全程不进行任何元素之间的比较这正是它能突破比较排序 O(n log n) 理论下界的原因时间复杂度可以达到 O(nk)。算法步骤与伪代码解析README 中给出了经典的教科书式伪代码。为便于理解这里将伪代码展开为带注释的完整流程Counting_sort(A, k) n length[A] // 输入数组长度 创建数组 B[n] 与 C[k1] // B 为输出数组C 为计数数组 for i 0 to k C[i] 0 // 第一步计数数组全部初始化为 0 for i 1 to n C[A[i]] // 第二步统计每个键值出现的次数 for i 1 to k C[i] C[i] C[i-1] // 第三步前缀和C[i] 变为小于等于 i 的元素个数 for i n to 1 B[C[A[i]]] A[i] // 第四步从后向前扫描把元素放到正确位置 C[A[i]]-- // 第五步相同键值递减保证稳定性其中 k 表示输入元素的最大键值即取值范围A 是输入数组B 是输出数组C 是长度为 k1 的计数数组。上述流程可以归纳为四个阶段初始化将计数数组 C 全部置 0频次统计遍历输入数组C[A[i]]记录每个值出现的次数哈希映射的核心步骤前缀和C[i] C[i] C[i-1]使 C[i] 变为值小于等于 i 的元素总数从而确定每个元素在输出数组中的最终落点区间回填从后向前遍历输入数组利用 C 中保存的位置信息将元素写入输出数组 B每次写入后递减对应计数——从后向前扫描这一细节保证了排序的稳定性相同元素的相对顺序在排序前后保持一致。时间复杂度与空间复杂度README 明确给出了计数排序的复杂度结论时间复杂度O(nk)其中 n 是输入数组的元素个数k 是输入元素的值域范围。由于算法只有三轮线性扫描初始化、统计、累加与回填每轮都是 O(n) 或 O(k)总复杂度为 O(nk)。空间复杂度O(nk)需要额外的计数数组 C大小 k1和输出数组 B大小 n。从复杂度公式可以推导出一个重要特性当k O(n)时计数排序的时间复杂度退化为 O(n)是名副其实的线性排序算法。需要特别强调的是k 与 n 的相对关系直接决定了算法的实用价值——如果 k 远大于 n例如对 [0, 10⁹] 范围的少量元素排序计数数组本身就会消耗巨大的内存此时计数排序反而劣于比较排序。复杂度之外的特性稳定性与适用边界除了 README 明示的复杂度结合源码实现可以进一步确认计数排序的两个关键特性稳定性采用前缀和 从后向前回填的经典实现是稳定排序如 README 伪代码所示即值相等的元素在排序后保持原有相对顺序。这一性质使其成为**基数排序Radix Sort**内部子过程的理想选择。而仓库中部分以频次回写方式实现的版本见下节 C/Go/JS 实现直接按值从小到大重写原数组则不具备稳定性属于去稳定化的简化写法。适用边界计数排序只能处理整数或可映射为整数的离散键值如 ASCII 字符码无法直接排序浮点数、字符串或自定义对象同时值域 k 不宜过大否则空间开销不可接受。仓库源码级实现解析Cosmos 仓库的 counting_sort 目录 提供了 11 种语言的实现分别是 C、C、C#、Go、Java、JavaScript、Objective-C、PHP、Python、Swift。这些实现风格可以归纳为两类经典前缀和 回填实现面向字符/整型数组counting_sort.c以#define RANGE 255定义计数数组大小用memset(count, 0, sizeof(count))初始化随后统计字符频次、做前缀和、从后向前回填到output数组最后拷贝回原数组。测试数据为字符串opengenus。counting_sort.py针对字符串不可变场景用 256 长度的列表作为计数数组count[ord(i)] 1以字符的 ASCII 码为下标统计频次最终拼接为有序字符串返回测试用例同样为opengenus。counting_sort.javaint count[] new int[256]对 char 数组计数count[anArr1]直接以字符为下标char 自动提升为 int最后用System.arraycopy将输出数组拷贝回原数组测试数据为geeksforgeeks的字符数组。这类实现的共同点是计数数组大小预先固定如 256适合字符或小范围整数场景但若值域很大需要先扫描出最大值来动态决定计数数组大小。动态值域 原地重写实现面向任意整数counting_sort.cpp先遍历一次求出数组最大值m据此动态声明int freq[m1]统计频次后用双指针i/j按下标从小到大把每个值按出现次数原地重写到sortedA测试数据为{1, 4, 12, 34, 16, 11, 9, 1, 3, 33, 5}。counting_sort.go额外处理了负数场景——先求出maxNumber与minNumber计数数组大小取max-min1下标统一做x-minNumber偏移再原地重写回列表测试数据包含负数{-5, 12, 3, 4, 1, 2, 3, 5, 42, 34, 61, 2, 3, 5}。counting_sort.js通过函数参数显式传入min与max界定值域初始化count[i] 0后统计频次再按区间内每个值while (count[i]-- 0)原地回写测试数据为[3, 0, 2, 5, 4, 1]。counting_sort.swift先求max/minrange max - min 1动态分配position数组既做了前缀和又用while index position[i]原地回写是偏移 前缀和结合的完整实现。counting_sort.mObjective-C 版本使用NSNumber封装整数calloc(range, sizeof(int))动态分配计数空间同样支持负数值域测试数据由arc4random() % 20 - 10生成范围 -109。Counting_sort.php先扫描求最大值$max按$max1大小创建$freq数组统计后双指针原地重写测试数据为{9, 1, 2, 5, 9, 9, 2, 1, 3, 3}。counting_sort.csC# 实现采用了基于SortedDictionaryint, int的频次映射思路以元素为键、出现次数为值依赖字典的有序性直接按键升序遍历并展开回填测试数据为 10 个rand.Next(10)随机数——这展示了计数思想在键值稀疏场景下的一种优雅变体。从上述源码可以清晰看出两种实现路线的差异C/Python/Java 版本验证了 README 伪代码的固定值域 前缀和 稳定回填范式而 Go/Swift/Objective-C 版本则通过min偏移把值域压缩到[min, max]在支持负数的同时降低了空间占用C/JS/PHP/Go 的频次展开重写写法则以牺牲稳定性换取了代码简洁。如何运行与验证仓库中所有实现均自带可独立运行的测试驱动main函数或__main__块可直接编译执行验证。以几个代表为例# C 版本gcc 编译运行输出排序后的 opengenus gcc counting_sort.c -o counting_sort_c ./counting_sort_c # C 版本 g counting_sort.cpp -o counting_sort_cpp ./counting_sort_cpp # Python 版本 python3 counting_sort.py # Go 版本 go run counting_sort.go各版本测试数据覆盖了字符数组、含负数的整数数组、随机数数组等场景运行输出即为排序结果可作为自测与教学演示使用。小结计数排序通过频次统计 前缀和定位绕开了比较操作实现了 O(nk) 的线性时间复杂度是理解以空间换时间思想的经典案例。本文以 README 的伪代码为主线剖析了其计数、定位、回填三阶段流程与稳定性来源并通过 Cosmos 仓库中 counting_sort 目录 下 11 种语言的实现对比了固定值域动态值域偏移字典频次映射等不同工程化写法。对于取值范围小、数据量大的整数排序场景计数排序及其衍生出的基数排序依然是最值得优先考虑的高效方案。赞分享教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载相关推荐《Hello 算法》计数排序Counting Sort完全指南从非负整数到稳定排序的实现原理《Hello 算法》计数排序Counting Sort完全指南从非负整数到稳定排序的实现原理 计数排序Counting Sort是一种不依赖元素比较、教程文档示例工程教育基数排序Radix Sort详解以《Hello 算法》学号排序场景为例从逐位计数原理到多语言代码实现基数排序Radix Sort详解以《Hello 算法》学号排序场景为例从逐位计数原理到多语言代码实现 本篇技术指南以《Hello 算法》hello a教程文档示例工程教育计数排序Counting Sort深度解析《Hello 算法》源码级实战指南计数排序Counting Sort深度解析《Hello 算法》源码级实战指南 计数排序counting sort是一种不基于元素比较的整数排序算法它教程文档示例工程教育上一篇终极猫抓扩展使用指南快速掌握浏览器资源嗅探技巧下一篇TensorForce 开源项目教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
企业数字化 ERP 产品动态
相关推荐
华为PCB设计规范：高速电路设计的关键工程实践 简介：《华为PCB设计规范.pdf》是一份依据国家标准编制的企业级PCB设计规范，面向PCB设计工程师、电子工程师、项目经理等相关人员，系统规定了印制电路板从设计任务受理、理解设计要求、创建网络表，到布局、布线、工艺设计及设计评审… · 2026/9/23 11:32:39
Yii 2 REST 错误处理完全指南：异常抛出、HTTP 状态码与自定义错误响应 后端Web框架 【免费下载链接】yii2 Yii 2: The Fast, Secure and Professional PHP Framework 项目地址： https://gitcode.com/gh_mirrors/yi/yii2 点击查看 免费下载 导读
在 Yii 2 的 RESTful API 开发中，如何规范地通知客户端"请求出了什么问题… · 2026/9/23 11:32:38
LLaMA-Factory：大语言模型微调的高效开源框架 1. 项目概述LLaMA-Factory是一个专注于大语言模型（LLM）微调的开源框架，它让研究人员和开发者能够高效地对LLaMA系列模型进行定制化训练。这个项目特别适合那些想要在自己的数据集上微调大语言模型，但又不想从头开始构建整个训练管… · 2026/9/23 11:32:26
迅游加速器海外版高频面试题：3个坑让你避开项目搭建难题 迅游加速器海外版高频面试题：3个坑让你避开项目搭建难题 学会语法却不知怎么搭项目，这是很多开发者的通病。面试时，考官常拿【迅游加速器海外版】这种实际工具切入，问你怎么处理网络延迟和连接稳定性。高频面试题里，这类场景题占比超40%，但90%的… · 2026/9/23 12:13:18
一文搞懂中国十大富豪排行榜技术选型避坑指南 一文搞懂中国十大富豪排行榜技术选型避坑指南 官方文档往往厚达数百页，翻半天找不到核心逻辑，代码示例还经常跑不通。别慌，今天带你一文搞懂如何用编程思维构建“中国十大富豪排行榜”的底层数据流。… · 2026/9/23 12:13:06
面试必问离心泵的扬程：3个坑让你避开选型雷区 面试必问离心泵的扬程：3个坑让你避开选型雷区 版本升级后 API 全变了，这种痛感在流体机械领域同样存在。很多刚入行的工程师或者准备面试的候选人，面对【面试必问】的离心泵扬程问题，往往只背下了公式 \(H = \frac{P}{\rho… · 2026/9/23 12:12:59
Java学生成绩管理系统课设源码解析：Gradle构建与MySQL实战 简介：这份资源是基于Java与MySQL的学生成绩管理分析系统项目源码，面向学习Java Web开发、数据库应用或课程设计的学生与开发者，帮助理解教育信息化场景下成绩管理系统的完整实现思路。压缩包共18个文件，约62KB，以xml配… · 2026/9/23 12:12:59
薄膜技术应用全解析：从光学镀膜到半导体制造的核心工艺 1. 薄膜技术到底能用在哪些地方聊到薄膜，很多人第一反应是手机贴膜或者保鲜膜，这误会可太大了。我在材料行业摸爬滚打十来年，每次跟新入行的朋友聊起薄膜，都会先纠正这个刻板印象：薄膜是一门涉及真空、等离子体、材料科… · 2026/9/23 12:12:59
Go Context 并发控制实战：从 goroutine 泄漏到 Gin 超时取消 1. 从一个真实场景说起：为什么你的 goroutine 关不掉刚写 Go 那会儿，我做过一个定时同步数据的小服务。主流程很简单：起一个 goroutine 每隔几秒拉一次接口，把结果写进数据库。上线跑了一周，某天运维告诉我内存一直在涨… · 2026/9/23 12:12:59
3招搞定手机怎么下载微信面试难题实战项目解析 3招搞定手机怎么下载微信面试难题实战项目解析 面试被问“手机怎么下载微信”背后的原理，90%的人答不上来。别笑，这看似弱智的问题，实则是考察你对移动应用分发机制、安全校验及网络协议理解的试金石。我带过不少校招新人，他们背了八股文，却连一个A… · 2026/9/23 0:00:03
你有新短消息请注意查收：3个新手避坑指南搞定消息系统选型 你有新短消息请注意查收：3个新手避坑指南搞定消息系统选型 面试被问“高并发下如何保证消息不丢失”，你张口就是“用Redis”，结果面试官追问“如果Redis宕机了怎么办”，你瞬间卡壳。这种场景太常见了，很多新手在背八股文时，只记住了技术名词… · 2026/9/23 0:00:29
