c语言实现计数排序算法
时间: 2023-09-02 22:11:50 浏览: 57
计数排序(Counting Sort)是一种非比较排序算法,它的核心思想是统计每个元素出现的次数,然后根据统计结果将元素排序。
计数排序的时间复杂度为 O(n+k),其中 n 是待排序序列的元素个数,k 是待排序序列中的最大值。
具体实现如下:
```c
#include <stdio.h>
void countingSort(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]]++;
}
int index = 0;
for (int i = 0; i <= max; i++) {
for (int j = 0; j < count[i]; j++) {
arr[index++] = i;
}
}
}
int main() {
int arr[] = {5, 3, 1, 5, 2, 4, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
countingSort(arr, n);
printf("排序后的数组:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
其中,首先遍历一遍待排序序列,找出最大值 max。然后,创建一个计数数组 count,数组大小为 max+1,用来统计每个元素出现的次数。接着,遍历一遍待排序序列,将每个元素的出现次数累加到计数数组 count 中。最后,遍历计数数组 count,根据统计结果将元素排序。
以上代码输出结果为:
```
排序后的数组:1 1 2 3 3 4 5 5
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)