c语言函数实现计数排序
时间: 2023-08-27 12:17:42 浏览: 48
计数排序是一种非基于比较的排序算法,其核心思想是统计待排序数组中每个元素出现的次数,然后依次输出即可。以下是C语言函数实现计数排序的代码:
```c
void counting_sort(int arr[], int n) {
int max = arr[0], min = arr[0];
for (int i = 1; i < n; i++) { // 找到最大值和最小值
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
int k = max - min + 1;
int *count = (int *)calloc(k, sizeof(int)); // 统计元素出现次数
for (int i = 0; i < n; i++) {
count[arr[i] - min]++;
}
for (int i = 1; i < k; i++) { // 累加元素个数
count[i] += count[i - 1];
}
int *temp = (int *)malloc(n * sizeof(int)); // 临时数组
for (int i = n - 1; i >= 0; i--) { // 输出结果
temp[--count[arr[i] - min]] = arr[i];
}
for (int i = 0; i < n; i++) {
arr[i] = temp[i];
}
free(count);
free(temp);
}
```
该函数接收一个整型数组和数组长度作为参数,返回值为void。函数中首先找到数组中的最大值和最小值,然后计算出元素值的取值范围k,创建一个大小为k的计数数组count,并统计每个元素出现的次数。接着,通过累加计数数组中元素的个数,计算出每个元素在有序数组中的位置。最后,创建一个临时数组temp,倒序遍历原始数组,将每个元素放到其在有序数组中的位置上。最后,将有序数组复制回原始数组,并释放临时数组和计数数组的内存空间。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](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)