在实际项目中所谓“排序算法”并不一定都是靠元素之间比较大小来完成的。C语言计数排序Counting Sort就是一类不依赖关键字比较、而是借助数组下标直接统计元素出现次数的线性排序算法。它在整数、成绩、年龄、状态码这类取值范围有限的数据上能够做到比快速排序更快的排序效果同时也是理解桶排序、基数排序等进阶线性排序算法的前提。这篇文章会从计数排序的适用场景讲起再手动推演一遍完整过程最后给出可直接运行的 C 语言实现、边界分析和排查清单。需要提前说明计数排序不是通用排序。它只适合“数据范围小但数据量可能很大”的场景。如果数据范围极大比如排序 10 个取值在 0 到 1 亿之间的随机数计数排序反而会浪费大量内存。理解这个前提比记住代码更重要。1. 计数排序到底在解决什么问题1.1 为什么需要计数排序从比较排序的局限说起冒泡排序、插入排序、快速排序、归并排序都有一个共同点它们通过比较元素之间的大小关系来确定顺序。比较排序的最优时间复杂度下界是 O(n log n)也就是说在“只能通过比较判断大小”这个限制下不管算法写得多精致都不可能突破这个理论下界。但很多实际问题并不需要比较。例如统计一个班级 60 名学生的成绩成绩范围是 0 到 100 分。此时可以采用另一种思路开一个长度为 101 的数组下标对应分数数组值对应“这个分数出现了几次”。遍历成绩后再按分数从小到大的顺序把对应次数的成绩输出。整个过程没有任何一次比较却得到了有序结果。这个思路就是计数排序的核心用元素的值作为数组下标用下标天然的顺序代替比较。对数据范围可控的整数来说它比任何比较排序都快。1.2 计数排序的基本思想用空间换时间计数排序执行时依赖两个关键数组计数数组 count下标表示“值”值表示“该值出现了多少次”。输出数组 output保存排序结果长度和原数组相同。第一遍遍历原数组统计每个值出现的次数第二遍对计数数组进行前缀和计算让 count[i] 表示“小于等于 i 的元素有多少个”第三遍从原数组末尾开始倒序回填把每个元素放到它在输出数组中应处的位置。这里提到的“前缀和”是计数排序区别于普通统计的核心。没有前缀和的版本只能按值从小到大“依次输出”这样排序结果不稳定。加上前缀和之后每个相同值的元素都能知道自己的精确落点算法才能保持稳定性。1.3 计数排序适合什么数据不适合什么数据用一张表直观对比计数排序和常见比较排序。排序方式是否比较大小时间复杂度空间复杂度稳定性适用典型数据冒泡排序是O(n^2)O(1)稳定小规模、教学理解快速排序是O(n log n)O(log n)不稳定通用数据归并排序是O(n log n)O(n)稳定需要稳定的通用数据计数排序否O(n k)O(k n)稳定范围小的整数、非负整数计数排序适合以下场景元素是非负整数或者可以通过偏移映射为非负整数。数据范围 k 相对数据量 n 来说不大。相同元素需要保持原始先后顺序也就是对稳定性有要求。不适合以下场景浮点数排序。浮点数取值范围太广无法用整数下标直接映射。字符串排序或结构体按字符串字段排序。字符串没有天然连续可用的整数下标。数据范围极大但数据量很小。例如排序 5 个数范围是 0 到 1 亿分配计数数组会白白消耗大量内存。数据范围未知且不可预估比如从文件中读入大量未限制的 long long 整数。注意先判断数据特征再决定是否上计数排序。不要把计数排序当作替代快排的通用方案。2. 先理解计数排序的三个关键阶段2.1 第一阶段统计每个元素的出现次数假设原数组为int arr[] {4, 2, 2, 8, 3, 3, 1};最大值是 8因此计数数组需要分配下标 0 到 8长度 9。先用 calloc 分配内存保证每个元素初始为 0。然后遍历原数组arr[0] 4所以 count[4] 加 1。arr[1] 2所以 count[2] 加 1。arr[2] 2所以 count[2] 再加 1。复制得到第 1 阶段的结果下标 i012345678count[i]012210001这说明数组中有 1 个 1、2 个 2、2 个 3、1 个 4、1 个 8其余值没有出现。2.2 第二阶段计算前缀和确定元素位置把 count 数组从下标 1 开始逐个累加。代码是这样的for (int i 1; i max; i) { count[i] count[i - 1]; }计算后 count[i] 的含义从“值 i 出现次数”变成“小于等于 i 的元素个数”。下标 i012345678count[i]013566667例如 count[3] 5表示整个数组中值小于等于 3 的元素共有 5 个也就是 1、2、2、3、3。从 1 开始这 5 个元素在排序后会占据输出数组的前 5 个位置也就是下标 0 到 4。2.3 第三阶段倒序回填保证稳定性回填时从原数组末尾开始往 output 数组中放元素。当前元素是 arr[6] 3它的落点是 output[count[3] - 1] output[4]。放完后 count[3] 减 1这样下一次遇到 3 时落点会向前移动一个位置。这个过程的关键在于倒序处理可以理解为让相同值中“靠后的原元素”先落到靠后的位置之后“靠前的原元素”再落到靠前的位置顺序和原来一致。每次放完元素后要执行 count[arr[i]]--否则下一次同一个值会覆盖同一个位置。手工逐步推演结果如下处理下标 i当前值count[当前值] - 1output 落点写入了什么635 - 1 4output[4]3534 - 1 3output[3]3423 - 1 2output[2]2387 - 1 6output[6]8222 - 1 1output[1]2146 - 1 5output[5]4011 - 1 0output[0]1最终得到output[] {1, 2, 2, 3, 3, 4, 8}2.4 为什么要分成三个步骤不能一步到位如果跳过前缀和直接按 count 数组的频次输出比如 count[1] 是 1 就输出一个 1count[2] 是 2 就输出两个 2排序结果看起来也是正确的。但这种方式丢失了原数组中相同元素的相对顺序。假设原数组第 1 个 3 和第 5 个 3 是有业务含义的例如两个学生成绩相同但学号不同直接按频次输出后学号顺序可能反转。前缀和的核心价值是为每个相同值的“最后一次出现”计算出精确位置倒序回填又保证同一值内部保持原来的先后次序。这个设计不是炫技而是为了让算法具备稳定性。3. C 语言环境准备与项目结构3.1 需要准备的环境学习计数排序不需要复杂工具只要具备一个能编译 C 语言的环境即可。本机没有编译环境时也可以使用在线编译平台快速验证。环境说明编译器GCC 或 Clang推荐 GCC 5.0 以上编辑器VS Code、CLion、Dev-C、Code::Blocks 均可标准C99 即可本文代码没有使用 C11 专属特性调试工具GDB 可选用于观察 count 和 output 数组变化在 Linux 或 macOS 下确认 GCC 是否可用gcc --version在 Windows 下如果安装了 Dev-C 或 MinGW-w64也可以直接在命令行运行 gcc。建议学习时使用命令行编译这样可以更清楚地看到编译过程。3.2 项目文件结构计数排序示例建议拆成两个文件便于区分核心算法和数据演示。counting_sort_demo/ ├── counting_sort.c // 计数排序算法实现 ├── counting_sort.h // 函数声明 ├── main.c // 主函数准备数据并打印结果 └── Makefile // 可选简化编译命令如果只是练习也可以把全部代码写在一个 main.c 中。为了文章阅读方便下面的核心演示保持单文件结构后续扩展版本的代码则单独列出。3.3 先准备一个观察中间过程的调试版函数学习阶段不能只关心最终输出最好能看到 count 数组在统计阶段和前缀和阶段的变化。这里给出一个打印 count 数组的辅助函数它不影响排序结果只用于调试#include stdio.h void print_count(int count[], int len) { for (int i 0; i len; i) { printf(%d , count[i]); } printf(\n); }这个函数的价值在于当排序结果不符合预期时可以在计数排序代码的中间插入打印快速定位是“统计阶段错了”还是“前缀和阶段错了”。4. 从零实现一个可运行的计数排序程序4.1 第一步寻找数组中的最大值和最小值经典计数排序假设数组元素都是非负整数因此只需要找最大值计数数组长度是 max 1。#include stdio.h #include stdlib.h void counting_sort(int arr[], int n) { if (arr NULL || n 0) { return; } int max arr[0]; for (int i 1; i n; i) { if (arr[i] max) { max arr[i]; } } printf(数据范围[0, %d]\n, max); }找最大值这一步决定了后续分配内存的大小所以必须放在分配计数数组之前。4.2 第二步分配计数数组并统计频次使用 calloc 分配计数数组原因是 calloc 会把内存初始化为 0。如果使用 malloc 却不 memset计数数组中的随机值会导致统计结果完全错乱。int *count (int *)calloc(max 1, sizeof(int)); if (count NULL) { printf(计数数组分配失败\n); return; } for (int i 0; i n; i) { count[arr[i]]; }这段代码中arr[i] 直接作为 count 数组的下标。例如 arr[i] 5就执行 count[5]。这一步隐藏着一个常见问题如果 arr[i] 是负数就会产生负下标程序访问非法内存。稍后的扩展版本会通过 min 偏移解决这个问题。4.3 第三步通过前缀和计算位置统计完成后的 count 数组每个下标表示“出现的次数”。改造为前缀和后每个下标表示“小于等于该值的元素个数”。for (int i 1; i max; i) { count[i] count[i - 1]; }前缀和计算完成后不要再用 count[arr[i]] 表示“出现次数”它的语义已经变了。后面回填时使用的是位置信息。4.4 第四步倒序回填输出数组这一步是计数排序最核心、最容易写错的部分。需要额外申请一个与原数组等长的 output 数组然后从原数组末尾开始向前遍历。int *output (int *)malloc(n * sizeof(int)); if (output NULL) { printf(输出数组分配失败\n); free(count); return; } for (int i n - 1; i 0; i--) { output[count[arr[i]] - 1] arr[i]; count[arr[i]]--; } for (int i 0; i n; i) { arr[i] output[i]; } free(count); free(output); }解释一下回填逻辑count[arr[i]] 表示“小于等于 arr[i] 的元素个数”。count[arr[i]] - 1 是这个元素在输出数组中最后出现的位置。写入后必须让 count[arr[i]]--防止下一个相同值覆盖同一个位置。倒序回填保证稳定性正序回填虽然结果看起来一致但会破坏相同元素的相对顺序。4.5 第五步完整可运行代码下面是完整例子包含主函数和测试数据#include stdio.h #include stdlib.h void counting_sort(int arr[], int n) { if (arr NULL || n 0) { return; } int max arr[0]; for (int i 1; i n; i) { if (arr[i] max) { max arr[i]; } } int *count (int *)calloc(max 1, sizeof(int)); if (count NULL) { printf(memory alloc failed\n); return; } for (int i 0; i n; i) { count[arr[i]]; } for (int i 1; i max; i) { count[i] count[i - 1]; } int *output (int *)malloc(n * sizeof(int)); if (output NULL) { printf(memory alloc failed\n); free(count); return; } for (int i n - 1; i 0; i--) { output[count[arr[i]] - 1] arr[i]; count[arr[i]]--; } for (int i 0; i n; i) { arr[i] output[i]; } free(count); free(output); } int main(void) { int arr[] {4, 2, 2, 8, 3, 3, 1}; int n sizeof(arr) / sizeof(arr[0]); printf(before: ); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); counting_sort(arr, n); printf(after: ); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }4.6 编译运行与预期输出在命令行进入代码所在目录执行gcc -g -Wall -o counting_sort_demo main.c ./counting_sort_demoWindows 下如果使用 MinGW命令类似gcc -g -Wall -o counting_sort_demo.exe main.c counting_sort_demo.exe预期输出如下before: 4 2 2 8 3 3 1 after: 1 2 2 3 3 4 8注意代码中的提示信息使用英文是为了避免 Windows 控制台中文编码不同导致的乱码。实际项目里如果需要中文提示建议统一使用 UTF-8 编码并确认终端的代码页一致。4.7 关键参数与边界说明参数或变量含义示例值错误影响arr待排序数组{4,2,2,8,3,3,1}传 NULL 会崩溃需做空判断n元素个数7传 0 或负数时提前返回max数组最大值8找错会导致数组越界或排序不完整count计数数组长度 max1长度 9长度不足会越界output排序结果临时数组长度 7为 NULL 时需释放 count 后返回count[arr[i]]--回填后的位置递减每次减 1遗漏会造成相同值覆盖注意上面的示例只支持非负整数。实际项目如果确定所有元素都非负可以保持这种写法如果不确定必须看向下方的负数扩展版本。5. 支持负数的工程化版本5.1 负数为什么会导致崩溃经典写法中count[arr[i]] 要求 arr[i] 必须是一个合法下标。C 语言数组下标必须大于等于 0一旦 arr[i] 是 -1程序就会访问 count[-1]这个地址落在数组起始位置之前属于未定义行为。轻则读到垃圾值重则段错误。5.2 通过最小值偏移解决负数问题解决思路是不直接用元素的值作为下标而是用“元素值 - 最小值”作为下标。这样最小元素映射到下标 0所有元素映射后都不会小于 0。数据范围也由 max 1 变成 max - min 1。#include stdio.h #include stdlib.h void counting_sort_ext(int arr[], int n) { if (arr NULL || n 0) { return; } int min arr[0], max arr[0]; for (int i 1; i n; i) { if (arr[i] min) { min arr[i]; } if (arr[i] max) { max arr[i]; } } int range max - min 1; int *count (int *)calloc(range, sizeof(int)); int *output (int *)malloc(n * sizeof(int)); if (count NULL || output NULL) { free(count); free(output); return; } for (int i 0; i n; i) { count[arr[i] - min]; } for (int i 1; i range; i) { count[i] count[i - 1]; } for (int i n - 1; i 0; i--) { int index arr[i] - min; output[count[index] - 1] arr[i]; count[index]--; } for (int i 0; i n; i) { arr[i] output[i]; } free(count); free(output); }测试负数数据int main(void) { int arr[] {-5, 10, 0, -5, 3, 10, 7}; int n sizeof(arr) / sizeof(arr[0]); counting_sort_ext(arr, n); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }输出结果为-5 -5 0 3 7 10 105.3 扩展版本的代价引入最小值偏移后count 数组长度变成 max - min 1。数据范围由原来的“最大值 1”变为“最大值 - 最小值 1”。当数值跨度极大时仍然会面临空间浪费问题。例如排序 {-1000000, 1000000}只需要 2 个元素但 range 是 2000001依然会分配约 8 MB 内存。因此在工程中使用计数排序前一定要先统计数据的实际范围而不是只关心数据量。6. 复杂度分析与算法特性6.1 时间复杂度为什么是 O(n k)记 n 为待排序元素个数k 为数据范围即 max - min 1。计数排序的执行步骤包括查找最大值和最小值遍历一次数组耗时 O(n)。统计频次遍历一次数组耗时 O(n)。前缀和遍历 count 数组范围长度为 k耗时 O(k)。倒序回填遍历一次数组耗时 O(n)。拷贝回原数组遍历一次数组耗时 O(n)。总时间复杂度为 O(n k)。当 k 明显小于 n 时可以近似看作 O(n)这就是它被称为线性排序的原因。当 k 远大于 n 时算法会变得不划算。6.2 空间复杂度计数排序需要两个额外数组count 数组长度为 k。output 数组长度为 n。因此额外空间为 O(n k)。它不是原地排序算法。如果需要排序的数组本身非常大同时数据范围也很大内存压力会比较明显。6.3 稳定性来源于倒序回填稳定性指的是值相同的元素排序后相对顺序和排序前一致。计数排序只要在回填时从原数组末尾向前处理并配合前缀和位置递减就能保持稳定。如果直接按计数数组频次从 count 数组开头扫描并连续输出得到的排序结果在值上是正确的但相同值之间无法保证原始顺序。这在处理结构体数组时尤其关键因此标准计数排序推荐使用前缀和加倒序回填的写法。6.4 与有序数据的表现对比指标冒泡排序快速排序计数排序平均时间O(n^2)O(n log n)O(n k)最好时间O(n)O(n log n)O(n k)最坏时间O(n^2)O(n^2)O(n k)空间O(1)O(log n)O(n k)稳定稳定不稳定稳定适用数据小规模任意数据通用任意数据小范围整数从表中可以看出计数排序最坏时间复杂度也是 O(n k)不会因为输入数据恰好完全逆序而退化。这是它对比较排序的一大优势。7. 常见错误与排查路径7.1 现象一程序运行直接崩溃或报段错误可能原因没有处理负数arr[i] 是负值后直接作为 count 下标。最大值计算错误导致 count 数组长度过小。调用函数时传入 NULL 指针。排查方式打印数组最大值和最小值确认数据范围。在统计循环前打印每个 arr[i]检查是否有负数。使用 GDB 运行程序查看崩溃位置gdb ./counting_sort_demo run bt解决方式使用支持 min 偏移的 counting_sort_ext 版本。函数入口增加 NULL 和 n 0 判断。7.2 现象二排序结果全部是垃圾值且差异巨大可能原因使用 malloc 分配 count 数组但没有初始化。分配后发现所有计数都基于随机初始值累加前缀和自然也错。排查方式检查分配 count 时是否使用 calloc或者是否手动 memset。在统计完成后打印 count 数组观察频次是否为 0 加出现次数。解决方式int *count (int *)calloc(max 1, sizeof(int));或在使用 malloc 后执行memset(count, 0, (size_t)(max 1) * sizeof(int));7.3 现象三数组中存在大值但排序结果缺少该值可能原因前缀和只遍历到某个错误边界没有覆盖到 max。最大值计算时初始值取错例如写成了 0而原始数组全部是负数。回填时 count[index] 减一操作放错位置导致大值写入被覆盖。排查方式打印前缀和后的 count[max]结果必须等于 n。检查回填循环的条件确保从 n - 1 到 0 全部处理。解决方式如果 count[max] ! n说明统计或前缀和少算了元素。在回填前打印 count 数组逐个核对。7.4 现象四相同元素的相对顺序被改变可能原因回填时使用正序遍历而不是倒序遍历。回填时没有执行 count[index]--导致相同值写入同一个位置。排查方式给数组元素绑定序号例如使用结构体数组中一个 int id 字段。排序后检查相同 value 的 id 顺序是否保持不变。解决方式回填循环写成 for (int i n - 1; i 0; i--)。写入 output 后立即执行 count[index]--。7.5 排查清单总结现象优先检查项为什么先查这里段错误数据是否为负数、是否数组越界负下标是 C 语言崩溃常见根因结果随机count 数组是否清零统计必须从 0 开始累加缺少大值或小值max 和 min 计算是否正确范围错误直接影响分配长度相同值顺序乱是否倒序回填、是否递减位置稳定性依赖这两点内存占用异常range 是否过大范围过大可能耗尽内存或导致分配失败8. 最佳实践与扩展方向8.1 学习环境的调试建议初学时不要只验证一次排序成功建议增加调试手段在统计阶段打印 count 数组。在前缀和完成后再次打印 count 数组。在回填阶段打印每次写入 output 的位置。这种方法能把抽象过程变成可见的数据变化避免“代码好像对了但原理没懂”的学习陷阱。建议把这套调试体力放在学习和笔试准备阶段。8.2 生产环境的额外考虑在生产环境使用计数排序时至少要关注以下几点数据范围来自哪里是否可能动态变化。如果范围不稳定建议先采样估算 max 和 min。是否允许使用额外内存。内存受限的嵌入式环境需要慎用 O(n k) 空间。排序对象是 int 还是结构体。结构体排序要求稳定性时建议使用标准的前缀和加倒序回填版本。分配结果是否判断为空。calloc 或 malloc 失败后要立即释放已经分配的资源避免内存泄漏。是否可以将排序封装成接口。实际项目中不要只写一个裸函数建议封装为 sort.h 和 sort.c并传入比较字段的提取函数。8.3 扩展方向结构体排序当排序对象是结构体数组时可以先按业务需要提取排序关键字。例如学生结构体按成绩排序#include stdio.h #include stdlib.h #include string.h typedef struct { int id; int score; char name[32]; } Student; void counting_sort_students(Student arr[], int n) { if (arr NULL || n 0) { return; } int min arr[0].score, max arr[0].score; for (int i 1; i n; i) { if (arr[i].score min) min arr[i].score; if (arr[i].score max) max arr[i].score; } int range max - min 1; int *count (int *)calloc(range, sizeof(int)); Student *output (Student *)malloc(n * sizeof(Student)); if (count NULL || output NULL) { free(count); free(output); return; } for (int i 0; i n; i) { count[arr[i].score - min]; } for (int i 1; i range; i) { count[i] count[i - 1]; } for (int i n - 1; i 0; i--) { int idx arr[i].score - min; output[count[idx] - 1] arr[i]; count[idx]--; } for (int i 0; i n; i) { arr[i] output[i]; } free(count); free(output); }这个版本保持了稳定性成绩相同的学生在排序后依然按照原数组中的顺序排列。8.4 扩展方向从计数排序到桶排序和基数排序计数排序本质上是一种特殊的桶排序每个值对应一个桶。理解了这一点后可以继续学习基数排序。基数排序把整数拆成多个数位每个数位执行一次计数排序从而处理范围更大的整数。学到这里计数排序就不只是一个小算法而是一系列线性排序算法的基础。建议的学习路径是先手工推演非负数计数排序。再实现支持负数的扩展版本。用结构体数组验证稳定性。对比同样数据的冒泡排序和快速排序耗时。最后扩展到桶排序和基数排序。刚开始学这一章时最值得花时间的地方不是背代码而是亲自在纸上写一遍前缀和和回填过程。能够准确回答“count[3] - 1 代表什么”“为什么必须倒序”这两个问题才算真正掌握了计数排序的底层逻辑。