c语言实现计数排序算法,包含累计数组,并标有详细的注释
时间: 2024-05-22 19:16:13 浏览: 12
#include <stdio.h>
// 计数排序函数
void counting_sort(int arr[], int n) {
// 找出最大值
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 创建计数数组
int count[max + 1];
for (int i = 0; i <= max; i++) {
count[i] = 0;
}
// 统计每个元素出现的次数
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// 计算累计数组
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// 输出累计数组
printf("累计数组:\n");
for (int i = 0; i <= max; i++) {
printf("%d ", count[i]);
}
printf("\n");
// 创建临时数组存放排序结果
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];
}
}
int main() {
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序前:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
counting_sort(arr, n);
printf("排序后:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)