c语言实现计数排序算法
时间: 2023-09-23 21:11:34 浏览: 109
计数排序是一种简单的排序算法,可以对整数进行排序。具体实现如下:
1. 找出待排序的数组中最大和最小的元素。
2. 统计数组中每个值为i的元素出现的次数,存入数组C的第i项。
3. 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)。
4. 反向填充目标数组:将每个元素i放在新数组的第C[i]项,每放一个元素就将C[i]减去1。
C语言实现:
```c
#include <stdio.h>
void countingSort(int *arr, int n) {
int i, j, k;
int max = arr[0], min = arr[0]; // 找到最大值和最小值
for (i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
int len = max - min + 1; // 统计计数数组的长度
int *countArr = (int *) malloc(len * sizeof(int)); // 动态分配计数数组
for (i = 0; i < len; i++) {
countArr[i] = 0;
}
for (i = 0; i < n; i++) { // 统计每个元素出现的次数
countArr[arr[i] - min]++;
}
k = 0;
for (i = 0; i < len; i++) { // 将计数数组中的元素依次填入原数组
for (j = 0; j < countArr[i]; j++) {
arr[k++] = i + min;
}
}
free(countArr); // 释放计数数组的内存
}
int main() {
int arr[] = {5, 3, 8, 6, 4, 1, 2, 7};
int n = sizeof(arr) / sizeof(arr[0]);
countingSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
运行结果:
```
1 2 3 4 5 6 7 8
```
相关推荐
![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)