计数排序（Counting Sort）是一种非比较性的排序算法，适用于一定范围内的整数排序。计数排序的基本原理是统计每个元素出现的次数，然后根据元素的值将其放置到正确的位置上。
计数排序的基本原理如下：
1. **统计元素出现次数**：遍历待排序数组，统计每个元素出现的次数，通常需要额外的辅助数组来记录这些计数。
2. **累加计数**：对计数数组进行累加操作，得到每个元素在排序后的数组中的位置。
3. **排序**：遍历原始数组，根据元素的值和计数数组中的位置信息，将元素放置到正确的位置上。
4. **输出排序结果**：将排序后的结果输出为有序数组。
计数排序的特点：
- 计数排序是稳定的排序算法，相同元素的相对位置不会改变。
- 时间复杂度为 O(n + k)，其中 n 是待排序元素的个数，k 是元素的范围。
- 计数排序适用于元素范围不大的情况，当范围较大时，空间复杂度会较高。
计数排序在某些特定情况下具有较高的效率，例如对整数进行排序且范围不大的情况下。然而，由于需要额外的空间来存储计数数组，因此在某些情况下可能不适用。以下是用 C++ 实现计数排序的示例代码：
```cpp #include <iostream> #include <vector> void countingSort(std::vector<int>& arr) { int n = arr.size(); // 找出数组中的最大值 int max = *std::max_element(arr.begin(), arr.end()); // 创建计数数组并初始化为0 std::vector<int> count(max + 1, 0); // 统计每个元素出现的次数 for (int i = 0; i < n; i++) { count[arr[i]]++; } // 对计数数组进行累加操作 for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } // 创建临时数组存储排序结果 std::vector<int> output(n); // 根据计数数组的信息将元素放置到正确的位置上 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]; } } void printArray(const std::vector<int>& arr) { for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; } int main() { std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1}; int n = arr.size(); std::cout << "Original array: "; printArray(arr); countingSort(arr); std::cout << "Sorted array: "; printArray(arr); return 0; } ```
在这段代码中，`countingSort` 函数实现了计数排序算法，包括统计元素出现次数、累加计数、排序和输出排序结果。`printArray` 函数用于打印数组的元素。在 `main` 函数中定义了一个整型数组并对其进行计数排序。
