1. 项目概述为什么我们需要计数排序在算法世界里排序是基础中的基础。我们熟知冒泡、选择、插入也仰望快速、归并、堆排序。但当你面对一个特定场景比如给全校一万名学生的考试成绩假设满分100从高到低排名或者统计一段文本中每个字母出现的频率并排序你会选择哪种算法用快速排序平均O(n log n)确实不错但总觉得有点“杀鸡用牛刀”而且不稳定。用归并排序稳定是稳定但需要额外的O(n)空间代码也相对复杂。这时计数排序Counting Sort就该登场了。它不是一种基于比较的排序算法而是利用数组下标本身的有序性通过统计每个元素出现的次数直接确定元素在最终序列中的位置。听起来有点抽象简单说它就像投票唱票有一堆选票待排序数组我们事先知道候选人只有固定的几位比如0到100分然后我们拿一个计票板计数数组给每个候选人画“正”字最后根据“正”字的多少从高到低或从低到高把候选人的名字写出来排序就完成了。它的核心价值在于极致的高效。对于数据范围最大值与最小值的差值不大且是整数的数据集它的时间复杂度可以达到惊人的O(n k)其中n是元素个数k是数据范围。这比任何基于比较的排序算法的理论下限O(n log n)还要快前提是k不能太大。它还是稳定排序这意味着值相同的元素在排序后能保持它们原有的相对顺序这个特性在排序复杂对象比如先按分数排再按学号排时至关重要。然而网上很多教程对计数排序的讲解要么过于理论化要么实现的代码有缺陷比如不处理负数、不体现稳定性、或者对数据范围k过大时的场景避而不谈。今天我们就从原理到实践彻底拆解计数排序并用C给出一个工业级强度、考虑边界条件的完整实现。无论你是正在刷题准备面试还是在实际项目中遇到需要非比较排序的场景这篇文章都能让你不仅“会用”更能“懂为什么这么用”。2. 计数排序的核心原理与思想拆解计数排序的精髓在于“用空间换时间”和“利用数据的有限离散性”。它彻底跳出了“比较大小决定次序”的传统思维开辟了一条新的路径。理解其思想是写出正确代码的第一步。2.1 算法基本思想与流程计数排序的流程可以清晰地分为三个步骤统计、累加、回写。我们通过一个具体例子来理解。假设我们要排序的数组是[4, 2, 2, 8, 3, 3, 1]。第一步找出数据范围并创建计数数组。首先遍历一遍数组找出最大值max 8和最小值min 1。那么数据的范围k max - min 1 8 - 1 1 8。这意味着所有可能的值都落在[1, 8]这个连续的整数区间内。 我们创建一个长度为k即8的计数数组count所有元素初始化为0。这个数组的下标0对应最小值1下标7对应最大值8。即count[i]将用来存储值(i min)出现的次数。第二步统计每个元素出现的次数。再次遍历原数组。遇到元素4它对应的计数数组下标是4 - min 4 - 1 3所以count[3]。遇到第一个2下标是2-11count[1]。依次类推遍历完成后count数组变为[1, 2, 2, 1, 0, 0, 0, 1]分别对应值1到8的出现次数。注意这里有一个关键优化——通过min进行偏移。直接创建长度为max1的数组下标0到8在min很大时会浪费大量空间。比如数据是[1000, 1001, 1002]如果创建长度1003的数组前1000个位置全是0是巨大的浪费。使用偏移后只需创建长度3的数组极大地节省了空间。第三步将计数数组转换为前缀和数组位置索引数组。这是实现稳定排序的关键一步。我们不再简单地将count数组理解为“次数”而是将其转换为“最后一个该元素应该放入的位置索引从1开始计”。 具体操作从count数组的第二个元素开始将每一个位置的值加上前一个位置的值。即count[i] count[i] count[i-1]。 经过计算我们的count数组变为[1, 3, 5, 6, 6, 6, 6, 7]。 这个新数组的含义是count[0]1值1的最后一个元素应该放在排序后数组的第1个位置索引0。count[1]3值2的最后一个元素应该放在排序后数组的第3个位置索引2。count[2]5值3的最后一个元素应该放在排序后数组的第5个位置索引4。以此类推。第四步从后向前遍历原数组根据前缀和数组放置元素到输出数组。创建一个和原数组等长的输出数组output。 我们从原数组的最后一个元素开始向前遍历这是保持稳定性的关键。当前元素是1其值对应count[0]。count[0]当前是1这意味着值1应该放在output数组的第1位索引1-10。所以我们将1放入output[0]。然后将count[0]的值减1变为0表示下一个如果还有值1应该放在第0位但索引已无实际表示已无位置逻辑上理解是前移一位。 接着前一个元素是3对应count[2]值为5。将3放入output[4]第5位索引4然后将count[2]减为4。 继续这个过程直到遍历完原数组所有元素。最终得到的output数组[1, 2, 2, 3, 3, 4, 8]就是排序后的稳定结果。实操心得为什么从后往前遍历能保证稳定性因为前缀和数组count[i]存储的是“最后一个该元素应放的位置”。从后往前遍历原数组当遇到一个重复元素时我们总是将它放在当前count值指示的位置然后count减1。这样原数组中靠后的重复元素在输出数组中也会被放在靠后的位置因为先被放置从而保持了原始的相对顺序。这是理解计数排序稳定性的核心。2.2 时间复杂度与空间复杂度分析理解了流程我们就能精确分析其复杂度。时间复杂度 O(n k)第一步找出最大值和最小值需要遍历数组O(n)。第二步统计频率遍历数组O(n)。第三步计算前缀和遍历计数数组O(k)。第四步回写排序结果遍历原数组O(n)。总时间O(n) O(n) O(k) O(n) O(3n k) O(n k)。当 k 与 n 处于同一数量级或更小时效率极高。空间复杂度 O(n k)需要额外的计数数组大小为 k即 O(k)。需要额外的输出数组大小为 n即 O(n)。总空间O(n k)。这是典型的空间换时间。如果允许修改原数组理论上可以将输出直接写回原数组但通常保留输出数组的概念更清晰。适用场景与局限性最佳场景数据范围k较小且为整数或可映射为整数。例如年龄排序0-150、分数排序0-100、枚举值排序。局限性数据必须是整数因为数组下标是整数。对于浮点数需要先进行离散化乘以一个倍数转换为整数会引入精度和范围问题。数据范围k不能过大如果待排序数组是[1, 1000000]虽然只有两个数但 k 接近100万需要巨大的计数数组空间消耗无法接受。不是原地排序需要额外的内存空间。在实际工程中计数排序很少单独使用但它常常作为基数排序的一个关键子过程用于对每一位数字进行排序。3. 计数排序的C实现与细节剖析理论讲透了我们动手实现。一个健壮的实现需要处理好负数、大范围数据、泛型支持可选以及稳定性。我们将实现一个函数countingSort并逐步完善它。3.1 基础版本实现处理非负整数我们先从最简单的场景开始假设输入数组arr中的所有元素都是非负整数。#include vector #include algorithm #include iostream void countingSort(std::vectorint arr) { if (arr.empty()) return; // 1. 找出数组中的最大值 int maxVal *std::max_element(arr.begin(), arr.end()); // 对于非负整数最小值默认为0 int minVal 0; // 2. 创建计数数组大小为范围长度并初始化为0 int range maxVal - minVal 1; std::vectorint count(range, 0); // 3. 统计每个元素出现的次数 for (int num : arr) { // 直接使用num作为索引因为minVal0 count[num]; } // 4. 将计数数组转换为前缀和数组位置索引 // 此时count[i]表示值等于i的元素其最后一个应该放在排序序列中的位置从1开始计 for (int i 1; i range; i) { count[i] count[i - 1]; } // 5. 创建临时输出数组 std::vectorint output(arr.size()); // 6. 从后向前遍历原数组根据count数组放置元素到output保证稳定性 for (int i arr.size() - 1; i 0; --i) { int num arr[i]; // count[num] 现在是“位置”需要转换为数组索引减1 output[count[num] - 1] num; // 放置后将该值对应的计数减1为前一个相同元素腾出位置 count[num]--; } // 7. 将排序结果拷贝回原数组 arr std::move(output); }这个版本清晰易懂但它有两个明显问题1) 无法处理负数2) 当maxVal很大时例如INT_MAXcount数组会大到内存爆炸。3.2 增强版本支持负数与偏移量优化要支持负数关键就在于引入minVal并使用偏移量将原始值映射到计数数组的索引。void countingSort(std::vectorint arr) { if (arr.empty()) return; // 1. 同时找出最大值和最小值 int maxVal *std::max_element(arr.begin(), arr.end()); int minVal *std::min_element(arr.begin(), arr.end()); // 2. 计算数据范围创建计数数组 int range maxVal - minVal 1; // 范围过大时直接退回使用std::sort避免内存耗尽 if (range 1e7) { // 设置一个阈值例如1000万 std::cout 数据范围过大( range )退回到std::sort std::endl; std::sort(arr.begin(), arr.end()); return; } std::vectorint count(range, 0); // 3. 统计频率使用偏移量 for (int num : arr) { count[num - minVal]; // 关键将值映射到从0开始的索引 } // 4. 计算前缀和 for (int i 1; i range; i) { count[i] count[i - 1]; } // 5. 构建输出数组 std::vectorint output(arr.size()); // 6. 反向遍历填充稳定排序 for (int i arr.size() - 1; i 0; --i) { int num arr[i]; int indexInCount num - minVal; // 获取在count数组中的索引 output[count[indexInCount] - 1] num; count[indexInCount]--; } // 7. 写回原数组 arr std::move(output); // 使用移动语义避免不必要的拷贝 }关键改进点解析偏移量num - minVal这是处理负数的核心。无论num是正是负num - minVal一定是一个非负整数且范围在[0, range-1]内完美适配数组下标。范围过大保护增加了阈值判断。当range超过一个合理值如1000万时直接调用std::sort。这是一个非常重要的工程实践防止因极端输入例如[INT_MIN, INT_MAX]导致程序瞬间申请数十GB内存而崩溃。std::sort在最坏情况下是 O(n log n)但空间是 O(1)在这种场景下是更安全的选择。移动语义std::move在最后将output赋值给arr时使用std::move可以避免整个数组元素的深层拷贝直接将output的内存所有权转移给arroutput变为空。这对于大型数组能提升效率。3.3 泛化版本支持自定义键值提取有时我们排序的不是简单的整数而是一个结构体或对象我们需要根据其中的某个整型字段键来排序。我们可以通过模板和函数对象或Lambda来泛化计数排序。#include functional // for std::function templatetypename T void countingSort( std::vectorT arr, std::functionint(const T) keyExtractor, int minKey, int maxKey) { if (arr.empty()) return; int range maxKey - minKey 1; if (range 1e7) { std::cout 键值范围过大建议使用其他排序算法。 std::endl; // 此处可以改为用std::sort并传入自定义比较器这里简单返回 return; } std::vectorint count(range, 0); std::vectorT output(arr.size()); // 统计频率 for (const T item : arr) { int key keyExtractor(item); count[key - minKey]; } // 计算前缀和 for (int i 1; i range; i) { count[i] count[i - 1]; } // 反向遍历填充 for (int i arr.size() - 1; i 0; --i) { const T item arr[i]; int key keyExtractor(item); int pos count[key - minKey]; // 注意这里是引用 output[pos - 1] item; pos--; } arr std::move(output); } // 使用示例按年龄排序Person对象 struct Person { std::string name; int age; }; int main() { std::vectorPerson people {{Alice, 25}, {Bob, 20}, {Charlie, 25}, {David, 22}}; // 找出年龄的最小最大值实际应用中可能需要单独遍历一次 int minAge 20, maxAge 25; // 这里简写实际应计算 // 使用Lambda表达式提取键值 countingSortPerson(people, [](const Person p) { return p.age; }, minAge, maxAge); for (const auto p : people) { std::cout p.name : p.age std::endl; } // 输出将是稳定的Bob(20), David(22), Alice(25), Charlie(25) // Alice和Charlie保持了输入时的相对顺序 return 0; }这个泛化版本赋予了计数排序更大的灵活性使其可以应用于更广泛的数据类型排序场景只要排序键是离散的整型即可。4. 实战应用场景与性能对比理解了原理和实现我们来看看计数排序在哪些地方能大显身手以及它和主流排序算法的对比。4.1 典型应用场景成绩排名系统如前所述百分制分数范围0-100k101。即使有百万考生计数排序也能在O(n)时间内完成排名效率远超任何比较排序。年龄统计与排序在人口普查或用户分析中年龄通常集中在0-120之间范围很小适合计数排序。字符频率统计与排序ASCII字符集共128个或256个扩展ASCII范围固定且小。可以用一个大小为256的数组快速统计一篇文章中每个字符出现的次数并按频率排序。基数排序的子过程基数排序从最低位到最高位或反之依次排序每一位的排序都要求是稳定的且该位数字范围固定例如十进制是0-9。计数排序完美契合因此常被用作基数排序的“位排序器”。有限枚举值排序比如订单状态0:待支付1:已支付2:已发货3:已完成直接用计数排序可以快速将相同状态的订单归类。4.2 与快速排序、归并排序的性能对比我们设计一个简单的测试来感受差异。假设我们有一个包含100万个整数的数组数据范围分别是[0, 100]小范围和[0, 1000000]大范围。#include chrono #include random #include algorithm void testPerformance() { const int n 1000000; std::vectorint arr1(n), arr2(n), arr3(n); // 场景1小范围数据 [0, 100] std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution dis1(0, 100); for (int i 0; i n; i) { arr1[i] arr2[i] arr3[i] dis1(gen); } auto start std::chrono::high_resolution_clock::now(); std::sort(arr1.begin(), arr1.end()); // 快速排序内省排序 auto end std::chrono::high_resolution_clock::now(); auto duration std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout 小范围数据 std::sort 耗时: duration.count() ms std::endl; start std::chrono::high_resolution_clock::now(); countingSort(arr2); // 我们的计数排序 end std::chrono::high_resolution_clock::now(); duration std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout 小范围数据 countingSort 耗时: duration.count() ms std::endl; // 场景2大范围数据 [0, 1000000] std::uniform_int_distribution dis2(0, 1000000); for (int i 0; i n; i) { arr1[i] arr2[i] arr3[i] dis2(gen); } start std::chrono::high_resolution_clock::now(); std::sort(arr1.begin(), arr1.end()); end std::chrono::high_resolution_clock::now(); duration std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout 大范围数据 std::sort 耗时: duration.count() ms std::endl; start std::chrono::high_resolution_clock::now(); countingSort(arr2); end std::chrono::high_resolution_clock::now(); duration std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout 大范围数据 countingSort 耗时: duration.count() ms std::endl; }预期结果分析小范围场景计数排序耗时将远低于std::sort。因为 O(nk) 中的 k101而std::sort是 O(n log n)当 n100万时log n 约等于20理论计算量相差一个数量级。大范围场景std::sort的耗时与小范围场景相比可能略有增加但幅度不大依然是 O(n log n)。而计数排序因为 k1000001需要创建巨大的计数数组内存分配和初始化O(k)的开销会变得非常巨大甚至可能因为内存不足而触发我们代码中的保护机制退回到std::sort或者即使能运行其耗时也将远超std::sort。这个测试清晰地展示了计数排序的优势边界当数据范围 k 远小于数据量 n 时它是王者当 k 与 n 相仿或更大时它就不如传统的比较排序了。5. 常见问题、陷阱与调试技巧即使理解了算法在实现和使用时还是会遇到各种坑。这里总结几个最常见的问题和解决方法。5.1 下标越界与偏移量错误这是实现计数排序时最容易出错的地方尤其是在处理负数或自定义最小值时。问题表现程序运行时出现std::vector的at或下标访问错误提示访问了无效位置。根本原因在将原数组元素num映射到计数数组下标时公式错误。正确的公式是index num - minVal。如果你错误地写成了index num当minVal不为0时或者index num minVal都会导致计算出的索引超出count数组的范围[0, range-1]。调试技巧打印关键变量在统计频率的循环开始前打印minVal,maxVal,range。在循环内对于前几个元素打印num和计算出的index确保index在[0, range-1]内。std::cout minVal minVal , maxVal maxVal , range range std::endl; for (int i 0; i std::min(5, (int)arr.size()); i) { int num arr[i]; int idx num - minVal; std::cout arr[ i ] num , idx idx std::endl; if (idx 0 || idx range) { std::cerr ERROR: Index out of bounds! std::endl; } }使用at()方法进行调试在开发阶段可以将count[num - minVal]改为count.at(num - minVal)。at()方法会进行边界检查如果索引无效会抛出std::out_of_range异常能帮你快速定位问题行。确定无误后为了性能再改回下标操作符[]。5.2 稳定性丢失问题问题表现排序后值相同的元素其原始相对顺序被打乱了。这在某些应用场景如多关键字排序下是不可接受的。根本原因在算法的第四步“回写”时从前向后遍历了原数组。让我们分析为什么这会导致不稳定。 假设原数组为[(A, 2), (B, 2)]括号内第一个是标识第二个是排序键值。前缀和数组count计算后对于键值2假设count[2] 2表示最后一个2应放在第2位。如果从前向后遍历第一个元素(A, 2)count[2]是2所以放在output[1]第2位然后count[2]减为1。第二个元素(B, 2)count[2]现在是1放在output[0]第1位。结果输出为[(B, 2), (A, 2)]A和B的顺序颠倒了。解决方案严格从后向前遍历原数组。这样原数组中靠后的元素在输出时也会先被放置但由于count数组记录的是“最后位置”后放置的会占据更靠后的位置从而保持了稳定性。这是必须遵守的固定步骤。5.3 内存消耗过大与优化策略问题表现程序在分配count数组时卡住或崩溃尤其是在处理数据范围很大的数组时。解决方案范围检查与回退正如我们在增强版代码中做的在计算range后立即判断其大小。如果超过一个预设的合理阈值例如1e7就果断放弃计数排序转而使用std::sort、std::stable_sort或其他通用排序算法。这是一种防御性编程。使用std::vectorint并预留空间std::vector在分配大块内存时比C风格数组更安全方便。使用std::vectorint count(range, 0)可以一次性初始化为0。如果担心初始化大数组的耗时可以考虑使用std::vectorint count; count.resize(range); std::fill(count.begin(), count.end(), 0);但差别不大。考虑稀疏数据场景如果数据范围k很大但实际出现的不同数值并不多即数据是稀疏的使用std::unordered_map来替代大数组可能更节省内存。但这会牺牲一些速度并且实现稳定排序的逻辑会变得更复杂需要额外的步骤来对键进行排序。这通常不是计数排序的典型用法仅在极端稀疏场景下可以考虑。5.4 处理非整型数据计数排序要求排序键必须是整数。对于浮点数或字符串需要转换。浮点数可以将浮点数乘以一个倍数如1e6转换为整数但要注意精度损失和转换后的范围可能非常大。例如对小数点后两位的金额单位元排序可以乘以100转换为分整数再进行计数排序。字符串无法直接使用。但如果是固定长度的字符串并且只考虑一个字符位置如姓氏首字母可以提取该字符的ASCII码作为键值。更通用的字符串排序需要使用比较排序如快速排序或基数排序将字符串看作多个字符位的组合。一个实用的建议当你不确定是否该用计数排序时问自己两个问题1) 排序键是否是或可映射为整数2) 键值的范围是否足够小如果两个答案都是“是”那么计数排序很可能是一个高效的选择。否则就老老实实用std::sort。在C中std::sort的实现通常是内省排序IntroSort已经高度优化对于通用数据而言它往往是综合性能最好的选择。计数排序是一把锋利的“特种手术刀”要在合适的“手术台”数据场景上使用。