C++计数排序详解（小白也能学会的线性时间排序算法）

计数排序的适用条件

• 待排序的元素必须是整数（或可映射为整数）
• 元素的取值范围不能太大（例如 0 到 k，k 不宜过大）
• 适用于数据分布较为集中的情况

算法步骤详解

1. 找出最大值和最小值：确定计数数组的大小
2. 创建计数数组：长度为 max - min + 1，初始化为0
3. 统计频次：遍历原数组，对每个元素在计数数组中对应位置加1
4. 累加计数数组（可选，用于稳定排序）：使计数数组存储的是小于等于当前值的元素个数
5. 构建输出数组：从后往前遍历原数组，根据计数数组确定每个元素的位置

C++代码实现

下面是一个完整的、易于理解的C++排序教程示例代码：

#include <iostream>#include <vector>#include <algorithm>void countingSort(std::vector<int>& arr) {    if (arr.empty()) return;    // 1. 找出最大值和最小值    int minVal = *std::min_element(arr.begin(), arr.end());    int maxVal = *std::max_element(arr.begin(), arr.end());    // 2. 创建计数数组    std::vector<int> count(maxVal - minVal + 1, 0);    // 3. 统计每个元素出现的次数    for (int num : arr) {        count[num - minVal]++;    }    // 4. 重构原数组（非稳定版本，简单直观）    int index = 0;    for (int i = 0; i < count.size(); ++i) {        while (count[i]-- > 0) {            arr[index++] = i + minVal;        }    }}// 测试函数int main() {    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};    std::cout << "排序前: ";    for (int x : arr) std::cout << x << " ";    std::cout << std::endl;    countingSort(arr);    std::cout << "排序后: ";    for (int x : arr) std::cout << x << " ";    std::cout << std::endl;    return 0;}

时间与空间复杂度分析

• 时间复杂度：O(n + k)，其中 n 是元素个数，k 是数据范围（max - min + 1）
• 空间复杂度：O(k)，需要额外的计数数组
• 当 k 远小于 n 时，计数排序效率极高，是真正的线性时间排序

总结

通过本篇C++计数排序教程，你应该已经掌握了这种高效排序算法的基本原理与实现方法。虽然它有使用限制，但在合适场景下（如成绩排序、年龄排序等小范围整数排序），它是最佳选择之一。希望这篇C++排序教程能帮助你夯实算法基础！

关键词回顾：C++计数排序、计数排序算法、C++排序教程、线性时间排序。