c++计数排序（c++计数排序算法代码）

# C++计数排序## 简介 计数排序是一种非比较类的整数排序算法，它通过统计输入数组中每个元素出现的次数来完成排序。计数排序的时间复杂度为O(n + k)，其中n是输入数组的长度，k是输入数组中的最大值。虽然计数排序对数据范围有限制，但它在处理特定范围内的整数时效率非常高。## 计数排序的基本原理 计数排序的核心思想是利用一个辅助数组来记录输入数组中每个元素出现的次数。通过遍历这个辅助数组，可以按照顺序生成排序后的数组。计数排序适用于数据范围较小且为整数的情况。### 1. 辅助数组的构建 首先创建一个大小为最大值加一的辅助数组count[]，用于记录输入数组中每个元素出现的次数。例如，如果输入数组中有3个元素值为5，则count[5]的值将增加到3。### 2. 统计频率 遍历输入数组，统计每个元素出现的次数，并将其存储在辅助数组中。### 3. 生成排序结果 根据辅助数组的值，依次生成排序后的数组。这一步骤可以通过累加的方式实现，确保相同值的元素按原顺序排列。## C++代码实现 以下是一个完整的C++实现计数排序的示例：```cpp #include #include void countingSort(std::vector& arr) {if (arr.empty()) return;// 找出数组中的最大值和最小值int maxVal = arr[0];int minVal = arr[0];for (int num : arr) {if (num > maxVal) maxVal = num;if (num < minVal) minVal = num;}// 创建计数数组int range = maxVal - minVal + 1;std::vector count(range, 0);// 统计每个元素的频率for (int num : arr) {count[num - minVal]++;}// 根据计数数组生成排序结果int index = 0;for (int i = 0; i < range; ++i) {while (count[i] > 0) {arr[index++] = i + minVal;count[i]--;}} }void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl; }int main() {std::vector arr = {4, 2, 2, 8, 3, 3, 1};std::cout << "Original array: ";printArray(arr);countingSort(arr);std::cout << "Sorted array: ";printArray(arr);return 0; } ```### 代码解析 1.

最大值与最小值的确定

：在计数排序之前，我们需要知道输入数组的最大值和最小值，以便创建合适的计数数组。 2.

计数数组的初始化

：计数数组的大小为`maxVal - minVal + 1`，并初始化为零。 3.

频率统计

：遍历输入数组，更新计数数组中对应元素的计数。 4.

生成排序结果

：再次遍历计数数组，根据计数数组中的值重构原始数组，生成排序后的结果。## 计数排序的特点 -

时间复杂度

：计数排序的时间复杂度为O(n + k)，其中k是计数数组的大小。 -

空间复杂度

：计数排序需要额外的空间来存储计数数组，其空间复杂度为O(k)。 -

适用场景

：计数排序适合处理数据范围较小且为整数的排序问题。如果数据范围较大或包含负数，则需要进行适当的调整。## 总结 计数排序是一种简单而高效的排序算法，尤其适用于整数排序且数据范围有限的情况。通过使用辅助数组来统计频率，计数排序能够以线性时间完成排序任务。然而，由于其依赖于数据范围，计数排序并不适用于所有场景，但对于特定问题，它是极佳的选择。

C++计数排序

简介 计数排序是一种非比较类的整数排序算法，它通过统计输入数组中每个元素出现的次数来完成排序。计数排序的时间复杂度为O(n + k)，其中n是输入数组的长度，k是输入数组中的最大值。虽然计数排序对数据范围有限制，但它在处理特定范围内的整数时效率非常高。

计数排序的基本原理 计数排序的核心思想是利用一个辅助数组来记录输入数组中每个元素出现的次数。通过遍历这个辅助数组，可以按照顺序生成排序后的数组。计数排序适用于数据范围较小且为整数的情况。

1. 辅助数组的构建 首先创建一个大小为最大值加一的辅助数组count[]，用于记录输入数组中每个元素出现的次数。例如，如果输入数组中有3个元素值为5，则count[5]的值将增加到3。

2. 统计频率 遍历输入数组，统计每个元素出现的次数，并将其存储在辅助数组中。

3. 生成排序结果 根据辅助数组的值，依次生成排序后的数组。这一步骤可以通过累加的方式实现，确保相同值的元素按原顺序排列。

C++代码实现 以下是一个完整的C++实现计数排序的示例：```cpp

include

include void countingSort(std::vector& arr) {if (arr.empty()) return;// 找出数组中的最大值和最小值int maxVal = arr[0];int minVal = arr[0];for (int num : arr) {if (num > maxVal) maxVal = num;if (num < minVal) minVal = num;}// 创建计数数组int range = maxVal - minVal + 1;std::vector count(range, 0);// 统计每个元素的频率for (int num : arr) {count[num - minVal]++;}// 根据计数数组生成排序结果int index = 0;for (int i = 0; i < range; ++i) {while (count[i] > 0) {arr[index++] = i + minVal;count[i]--;}} }void printArray(const std::vector& arr) {for (int num : arr) {std::cout << num << " ";}std::cout << std::endl; }int main() {std::vector arr = {4, 2, 2, 8, 3, 3, 1};std::cout << "Original array: ";printArray(arr);countingSort(arr);std::cout << "Sorted array: ";printArray(arr);return 0; } ```

代码解析 1. **最大值与最小值的确定**：在计数排序之前，我们需要知道输入数组的最大值和最小值，以便创建合适的计数数组。 2. **计数数组的初始化**：计数数组的大小为`maxVal - minVal + 1`，并初始化为零。 3. **频率统计**：遍历输入数组，更新计数数组中对应元素的计数。 4. **生成排序结果**：再次遍历计数数组，根据计数数组中的值重构原始数组，生成排序后的结果。

计数排序的特点 - **时间复杂度**：计数排序的时间复杂度为O(n + k)，其中k是计数数组的大小。 - **空间复杂度**：计数排序需要额外的空间来存储计数数组，其空间复杂度为O(k)。 - **适用场景**：计数排序适合处理数据范围较小且为整数的排序问题。如果数据范围较大或包含负数，则需要进行适当的调整。

总结 计数排序是一种简单而高效的排序算法，尤其适用于整数排序且数据范围有限的情况。通过使用辅助数组来统计频率，计数排序能够以线性时间完成排序任务。然而，由于其依赖于数据范围，计数排序并不适用于所有场景，但对于特定问题，它是极佳的选择。