计数排序C++代码：高效排序算法的实现与应用

计数排序是一种非常高效的排序算法，特别适用于数据范围有限且数据量较大的情况。今天我们将深入探讨计数排序C++代码的实现方法，并介绍其应用场景。

计数排序的基本原理

计数排序的核心思想是通过统计每个元素出现的次数来确定其在排序后的位置。具体步骤如下：

确定数据范围：找到数组中的最大值和最小值，计算出数据的范围。
初始化计数数组：创建一个辅助数组，其长度为数据范围加1，用于记录每个元素的出现次数。
统计元素出现次数：遍历原始数组，将每个元素在计数数组中对应的位置加1。
累加计数数组：将计数数组中的每个元素与前一个元素相加，得到每个元素在排序后的位置。
构建排序数组：根据累加后的计数数组，将原始数组中的元素按顺序放入新的数组中。

C++代码实现

下面是一个简单的计数排序C++代码示例：

#include <iostream>
#include <vector>

void countingSort(std::vector<int>& arr) {
    if (arr.empty()) return;

    int max = *std::max_element(arr.begin(), arr.end());
    int min = *std::min_element(arr.begin(), arr.end());
    int range = max - min + 1;

    std::vector<int> count(range), output(arr.size());

    // 统计每个元素出现的次数
    for (int num : arr) {
        count[num - min]++;
    }

    // 累加计数数组
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    // 构建排序数组
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    // 将排序结果复制回原数组
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = output[i];
    }
}

int main() {
    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

计数排序的应用场景

数据范围有限：当数据范围较小时，计数排序的效率非常高。例如，学生成绩排序、评分系统等。
数据量大：对于大数据量但数据范围有限的情况，计数排序可以显著减少时间复杂度。
稳定性要求：计数排序是稳定的排序算法，保持了原始数据的相对顺序，这在某些应用中非常重要。
负载均衡：在分布式系统中，计数排序可以用于负载均衡，确保任务分配的均匀性。
图像处理：在图像处理中，计数排序可以用于像素值的排序和统计。

优点与局限性

优点：

时间复杂度低：计数排序的时间复杂度为O(n+k)，其中n是元素个数，k是数据范围。
稳定性：保持元素的相对顺序。
适用于大数据量：在数据范围有限的情况下，处理速度非常快。

局限性：

空间复杂度高：需要额外的空间来存储计数数组和输出数组。
数据范围限制：当数据范围很大时，计数排序的效率会大大降低。

总结

计数排序C++代码提供了一种简单而高效的排序方法，特别适用于数据范围有限且数据量较大的场景。通过理解其原理和实现，我们可以更好地应用这种算法来解决实际问题。希望本文能帮助大家更好地理解和应用计数排序，提升编程和算法设计的水平。