计数排序步骤及c++代码
时间: 2023-10-02 13:03:29 浏览: 60
计数排序是一种线性时间复杂度的排序算法,适用于一定范围内的整数排序。下面是计数排序的步骤及C++代码示例:
步骤:
1. 创建一个计数数组count[],大小为待排序数组中的最大值加1。
2. 遍历待排序数组,统计每个元素出现的次数,并将次数存储在count[]中对应的位置。
3. 对count[]进行累加,使得count[i]存储小于等于i的元素个数。
4. 创建一个临时数组result[],大小与待排序数组相同。
5. 遍历待排序数组,根据count[]中存储的元素个数,将元素放入result[]中正确的位置,并将count[]中对应位置的值减1。
6. 将result[]复制回待排序数组。
C++代码示例:
```cpp
#include <iostream>
using namespace std;
void countingSort(int arr[], int n) {
// 找到待排序数组中的最大值
int max_val = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max_val) {
max_val = arr[i];
}
}
// 创建计数数组count[],并将元素初始化为0
int count[max_val + 1] = {0};
// 统计每个元素出现的次数
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// 对count[]进行累加
for (int i = 1; i <= max_val; i++) {
count[i] += count[i - 1];
}
// 创建临时数组result[]
int result[n];
// 将元素放入result[]中正确的位置
for (int i = n - 1; i >= 0; i--) {
result[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// 将result[]复制回原数组
for (int i = 0; i < n; i++) {
arr[i] = result[i];
}
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
countingSort(arr, n);
cout << "排序后的数组:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
这段代码实现了计数排序算法,对给定的数组进行排序。运行后输出排序后的数组:1 2 2 3 3 4 8。