排序是 C 语言学习里绕不开的一关但很多初学者一看到“计数排序”四个字就直接劝退又是计数、又是累加、又是反向填充光听名字就头疼。这次我们把它拆开揉碎不绕弯子直接看它到底在干什么、代码怎么写、为什么能比冒泡排序快一个量级。计数排序不是比较排序它不靠元素之间比大小来排顺序而是靠“数数”直接确定每个元素的位置。核心思想一句话如果我知道数组里比某个数小的元素有几个那这个数应该放在哪个下标就确定了。对于取值范围有限、数据量大的场景计数排序的速度非常夸张时间复杂度可以做到 O(n k)比快速排序、归并排序这类 O(n log n) 的比较排序还要快。这篇文章会带你完整走一遍计数排序的全过程从算法原理、过程模拟、C 语言代码实现到复杂度分析、常见错误排查再到和冒泡排序、快速排序的横向对比。全程不依赖任何第三方库纯 C 语言实现代码可以直接复制到本地编译运行。适合刚学完数组和循环、想进阶排序算法的读者也适合准备 C语言笔试题、数据结构与算法考试的人做系统性复习。1. 计数排序核心能力速览在写代码之前先把计数排序的关键信息列清楚方便你判断它适不适合当前场景。特性说明排序类型非比较排序基于元素值域统计时间复杂度O(n k)n 为数组长度k 为数据范围空间复杂度O(k)需要额外计数数组稳定性基础版不稳定反向填充版稳定适用数据整数、取值范围有限、数据密集不适用数据浮点数、范围过大的整数、稀疏数据原地排序否需要额外空间语言实现难度低只需要数组和循环基础典型场景成绩排名、年龄统计、0-100 分数排序从这张表可以看到计数排序的核心优势是快核心代价是空间。如果数据范围是 0 到 100那只需要 101 个元素的计数数组非常划算。如果数据范围是 0 到 10 亿那计数数组就需要 10 亿个元素内存直接爆炸这时候计数排序就不合适了。2. 适用场景与使用边界计数排序并不是万能的排序算法它的使用边界非常明显。适合的场景有三类第一类是数据取值范围小的整数排序比如学生成绩排序、年龄统计、100 以内的整数排序。这类场景下 k 很小空间开销可以忽略不计速度优势极其明显。第二类是数据量大的密集整数排序比如 100 万分数的排序。表面看 100 万很大但如果分数范围只有 0 到 100那么 k 101时间复杂度近似 O(n)比快速排序快很多。第三类是稳定性有要求的场景比如按成绩排序后要求相同成绩的人保持原来的相对顺序。这种情况需要使用反向填充版本的计数排序。不适合的场景也有三类数据范围过大的整数。比如对包含 2147483647 的数组排序计数数组根本开不出来。浮点数排序。计数排序的核心是“用数组下标代表数字本身”浮点数无法直接映射到数组下标。字符串或对象排序。如果排序键不是整数计数排序无法直接使用需要先做键值映射复杂度反而上升。另外要强调一个工程习惯计数排序适合教学演示和特定场景但在真实项目里如果数据范围不确定先用快速排序或者系统自带的 qsort 更稳妥。不要为了炫技强行使用计数排序。3. 计数排序算法原理详解3.1 算法思想计数排序的核心思想是利用数组下标的有序性。假设待排序数组中的元素都是非负整数且最大值是 max那么可以创建一个长度为 max 1 的计数数组 count遍历原数组每遇到一个数字 x就让 count[x] 加 1。遍历结束后count 数组里已经记录了每个数字出现的次数。接下来只需要按照下标从小到大遍历 count 数组把下标值输出 count[i] 次就得到了有序数组。这个过程本质上是用一个“哈希表”统计频次再按顺序还原。不需要任何比较操作所以比比较排序快得多。3.2 全过程模拟假设待排序数组为int arr[] {4, 2, 2, 8, 3, 3, 1};第一步扫描数组找到最大值 8确定计数数组长度为 9。第二步初始化计数数组全部赋 0。 下标: 0 1 2 3 4 5 6 7 8 计数: 0 0 0 0 0 0 0 0 0 第三步遍历原数组统计频次数字 4count[4]计数数组变为 0 0 0 0 1 0 0 0 0数字 2count[2]计数数组变为 0 0 1 0 1 0 0 0 0数字 2count[2]计数数组变为 0 0 2 0 1 0 0 0 0数字 8count[8]计数数组变为 0 0 2 0 1 0 0 0 1数字 3count[3]计数数组变为 0 0 2 1 1 0 0 0 1数字 3count[3]计数数组变为 0 0 2 2 1 0 0 0 1数字 1count[1]计数数组变为 0 1 2 2 1 0 0 0 1最终计数数组含义是1 出现 1 次2 出现 2 次3 出现 2 次4 出现 1 次8 出现 1 次。第四步按顺序输出下标 1 出现 1 次输出 1下标 2 出现 2 次输出 2 2下标 3 出现 2 次输出 3 3下标 4 出现 1 次输出 4下标 8 出现 1 次输出 8得到结果1 2 2 3 3 4 8排序完成。这个模拟过程就是计数排序的完整逻辑。动画演示本质上也就是不断更新计数数组和按序输出的过程理解上面这张表就能完全掌握。4. C语言计数排序代码实现4.1 基础版本先写一个最直观的基础版本。假设所有元素都是非负整数。#include stdio.h #include stdlib.h // 获取数组最大值 int getMax(int arr[], int n) { int max arr[0]; for (int i 1; i n; i) { if (arr[i] max) { max arr[i]; } } return max; } // 基础版计数排序 void countingSortBasic(int arr[], int n) { int max getMax(arr, n); // 动态分配计数数组并初始化为 0 int *count (int *)calloc(max 1, sizeof(int)); if (count NULL) { printf(内存分配失败\n); return; } // 统计每个元素出现次数 for (int i 0; i n; i) { count[arr[i]]; } // 按顺序输出到原数组 int index 0; for (int i 0; i max; i) { while (count[i] 0) { arr[index] i; count[i]--; } } free(count); } int main() { int arr[] {4, 2, 2, 8, 3, 3, 1}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前: ); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); countingSortBasic(arr, n); printf(排序后: ); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }这里用 calloc 而不是 malloc原因是 calloc 会自动把内存初始化为 0省去了手动 memset 的步骤。运行程序后可以看到输出排序前: 4 2 2 8 3 3 1 排序后: 1 2 2 3 3 4 8这个版本的逻辑最接近计数排序的原始思想适合零基础理解。但它在两个问题只能处理非负整数且排序不稳定。4.2 优化版本支持负数如果数组里有负数直接使用负数作为数组下标是非法的。解决办法是先找到数组的最小值 min然后把每个元素减去 min 后再统计。这样所有元素都映射到了非负区间。#include stdio.h #include stdlib.h // 获取数组最大值和最小值 void getMinMax(int arr[], int n, int *min, int *max) { *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]; } } } // 支持负数的计数排序 void countingSortWithNegative(int arr[], int n) { int min, max; getMinMax(arr, n, min, max); // 数据范围 int range max - min 1; // 分配计数数组 int *count (int *)calloc(range, sizeof(int)); if (count NULL) { printf(内存分配失败\n); return; } // 统计频次关键是把 arr[i] 映射到 arr[i] - min for (int i 0; i n; i) { count[arr[i] - min]; } // 按顺序填充原数组 int index 0; for (int i 0; i range; i) { while (count[i] 0) { arr[index] i min; count[i]--; } } free(count); } int main() { int arr[] {-5, 3, 0, -2, 4, -5, 1}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前: ); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); countingSortWithNegative(arr, n); printf(排序后: ); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }这个版本的核心修改点是计数器下标用 arr[i] - min回填时再用 i min 还原真实值。运行结果排序前: -5 3 0 -2 4 -5 1 排序后: -5 -5 -2 0 1 3 44.3 稳定版本反向填充基础版虽然能排序但无法保证相同元素的相对顺序不变。如果只是对整数排序稳定性影响不大。但在实际应用里比如按成绩排序同时保留学生链表的信息稳定版本才有实用价值。稳定版本的做法是先对计数数组做前缀和然后从原数组的末尾开始遍历根据计数数组确定当前元素在输出数组中的位置放入后计数减一。#include stdio.h #include stdlib.h void countingSortStable(int arr[], int n) { 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(内存分配失败\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(内存分配失败\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() { int arr[] {4, 2, 2, 8, 3, 3, 1}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前: ); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); countingSortStable(arr, n); printf(排序后: ); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }这里最容易出错的地方是output[count[arr[i]] - 1] arr[i]。为什么减 1因为数组下标从 0 开始。如果 count 的前缀和表示“小于等于当前元素的元素个数为 count[arr[i]]”那么最后一个相同元素的正确位置是 count[arr[i]] - 1。放置完成后 count[arr[i]]--让下一个相同元素排到前一个位置这样就从后向前依次填充保证了稳定性。5. 计数排序复杂度分析5.1 时间复杂度计数排序只需要两次完整的数组遍历一次统计频次一次回填数据。前缀和计算也是循环一次计数数组长度。所以总时间复杂度为统计频次O(n)前缀和O(k)回填数据O(n)整体为 O(n k)。当 k 远小于 n 时时间复杂度近似 O(n)这是计数排序最大的优势。对比其他排序排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(k)取决于实现从数据量角度看1000 个元素的数组用冒泡排序约需要 100 万次操作用计数排序只需要约 1000 k 次操作。数据量越大、数据范围越小计数排序的优势越明显。5.2 空间复杂度计数排序的空间复杂度为 O(k)主要消耗在计数数组上。稳定版本还会额外增加一个 O(n) 的输出数组。如果数据范围 k 是 100那么空间开销几乎可以忽略。如果 k 是 100 万那空间开销就比较大了。所以在使用前先评估 k 的大小再决定是否使用计数排序。5.3 稳定性分析基础版本的计数排序从前往后填充原数组不保证稳定性。稳定版本采用前缀和加反向填充可以保证相同元素的相对顺序不变。这个特性在 C 语言笔试题里经常被拿来提问需要特别记住。6. 计数排序与冒泡排序、快速排序对比6.1 计数排序 vs 冒泡排序冒泡排序每轮比较相邻元素把最大值逐步“冒”到数组末尾。时间复杂度 O(n^2)实现简单但速度慢。计数排序直接基于值域统计时间复杂度 O(n k)。在实际测试中对 10000 个 0 到 1000 的整数排序冒泡排序大约需要数亿次比较耗时可观计数排序只需要遍历数组几次速度差距非常明显。冒泡排序的优势是没有额外空间开销是原地排序对任意数据都能用。计数排序的优势是速度快但只适合整数和小范围数据。6.2 计数排序 vs 快速排序快速排序是原地排序平均时间复杂度 O(n log n)是通用场景的首选。但快速排序有递归调用栈深度有开销最坏情况下退化为 O(n^2)。计数排序在 k 较小的场景下时间复杂度优于快速排序。但快速排序不需要关心数据范围浮点数、字符串、对象都能排通用性更强。工程建议是数据范围明确且较小的整数数组用计数排序数据范围不确定或类型复杂用快速排序或 qsort。7. 计数排序常见错误与调试方法7.1 错误一数组下标越界这是计数排序最常见的错误。比如数组最大值是 100计数数组长度只分配了 100那么 count[100] 就会越界。必须确保长度是 max 1。7.2 错误二忘记处理负数如果把负数作为数组下标会导致程序崩溃或者产生未定义行为。要么先确定数组最小值把元素统一映射到非负区间要么在排序前直接判断数组是否包含负数。7.3 错误三calloc 和 malloc 混用导致未初始化malloc 分配的内存内容是垃圾值必须手动 memset。calloc 自动初始化为 0更安全。建议统一使用 calloc。7.4 错误四内存泄漏动态分配了 count 数组但忘记 free函数每次调用都泄漏内存。可以用 valgrind 检查valgrind --leak-checkfull ./counting_sort7.5 错误五前缀和更新顺序错误稳定版本的代码中必须先完成所有前缀和计算再开始反向填充。如果边算前缀和边回填会导致位置错乱。建议用注释把步骤拆开// 第一次遍历统计频次 // 第二次遍历前缀和 // 第三次遍历反向填充8. 计数排序调试示例用 print 观察中间过程如果在学习过程中发现排序结果不对建议在关键节点打印中间变量。下面是一个带调试输出的示例片段void countingSortDebug(int arr[], int n) { int max getMax(arr, n); printf(最大值: %d\n, max); int *count (int *)calloc(max 1, sizeof(int)); for (int i 0; i n; i) { count[arr[i]]; } printf(频次统计: ); for (int i 0; i max; i) { if (count[i] ! 0) { printf([%d]:%d , i, count[i]); } } printf(\n); int index 0; for (int i 0; i max; i) { while (count[i] 0) { arr[index] i; count[i]--; } } }输出示例最大值: 8 频次统计: [1]:1 [2]:2 [3]:2 [4]:1 [8]:1 排序后: 1 2 2 3 3 4 8看到频次统计是正确的那问题一定出在回填逻辑上。如果频次统计本身是错的就检查原数组遍历有没有越界。9. 计数排序练习题与扩展思路9.1 练习一实现一个函数使用计数排序对 0 到 100 的成绩数组进行排序并统计每个分数段的人数。提示可以用计数数组直接得到分数分布不需要额外遍历排序结果。9.2 练习二实现计数排序的基数排序版本。先按个位排序再按十位排序依次处理到最高位。基数排序可以处理范围很大的整数是计数排序的典型扩展。9.3 练习三给定一个包含大量重复整数的数组使用计数排序统计每个整数的出现次数并输出出现次数最多的前 5 个元素。这个题目考察计数数组和排序的综合应用。9.4 练习四把计数排序改造为可以对 char 类型字符排序的版本。注意 char 的取值范围是 -128 到 127需要正确处理负数下标问题。9.5 练习五比较计数排序和系统 qsort 在 n 1000000、数据范围为 0 到 1000 时的运行时间。先在代码里使用 clock() 计时观察两者差距。#include stdio.h #include time.h #include stdlib.h int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int main() { int n 1000000; int range 1000; int *arr1 (int *)malloc(n * sizeof(int)); int *arr2 (int *)malloc(n * sizeof(int)); for (int i 0; i n; i) { arr1[i] rand() % range; arr2[i] arr1[i]; } // 计时计数排序 clock_t start clock(); // 调用计数排序函数 clock_t end clock(); printf(计数排序耗时: %lf 秒\n, (double)(end - start) / CLOCKS_PER_SEC); // 计时 qsort start clock(); qsort(arr2, n, sizeof(int), cmp); end clock(); printf(qsort 耗时: %lf 秒\n, (double)(end - start) / CLOCKS_PER_SEC); free(arr1); free(arr2); return 0; }在数据范围很小的情况下计数排序的耗时通常远低于 qsort。这个练习可以非常直观地感受到非比较排序的速度优势。10. 总结与下一步计数排序是 C 语言排序算法里结构最清晰、最容易上手的非比较排序。它用“统计频次 按序回填”代替了元素间的比较把时间复杂度做到了 O(n k)。学习计数排序时重点抓住三个关键步骤找最大值确定计数数组长度、遍历原数组统计频次、按序回填数据。这三个步骤理解了后续的稳定版本和负数版本都只是在细节上做扩展。建议收藏这篇文章当作 C语言笔试题复习材料。下一步可以继续学习基数排序和桶排序它们和计数排序同属非比较排序家族思路一脉相承。如果你在本地编译运行代码时遇到问题优先检查计数数组长度是否足够、是否忘记释放内存、负数是否做了映射偏移。把这三处检查完计数排序的代码基本就能稳定跑通了。
