写一个c语言的基数计数排序
时间: 2023-09-09 14:07:10 浏览: 50
基数计数排序(Radix Counting Sort)是一种基于桶排序的排序算法,它是一种非比较排序,适用于排序的元素为非负整数的情况。基数计数排序的时间复杂度为O(d(n+k)),其中d为最大位数,k为基数,n为排序元素的个数。
以下是基数计数排序的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 获取数字的某一位数字,例如getDigit(123, 0)返回3
int getDigit(int num, int d) {
int i;
for (i = 0; i < d; i++) {
num /= 10;
}
return num % 10;
}
void radixCountingSort(int arr[], int n) {
int i, j, k;
int max = arr[0]; // 找到元素中的最大值
for (i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 对每一位进行计数排序
int exp = 1;
int *count = (int *)malloc(sizeof(int) * 10);
int *output = (int *)malloc(sizeof(int) * n);
while (max / exp > 0) {
for (i = 0; i < 10; i++) {
count[i] = 0;
}
for (i = 0; i < n; i++) {
count[getDigit(arr[i], exp)]++;
}
for (i = 1; i < 10; i++) {
count[i] += count[i-1];
}
for (i = n-1; i >= 0; i--) {
j = getDigit(arr[i], exp);
output[count[j]-1] = arr[i];
count[j]--;
}
for (i = 0; i < n; i++) {
arr[i] = output[i];
}
exp *= 10;
}
free(count);
free(output);
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
radixCountingSort(arr, n);
int i;
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
这个实现过程中,我们先找到数组中的最大值,然后对于每一位进行计数排序。在计数排序的过程中,我们需要先把数字按照位数进行分类,然后根据每个数字的位数,把数字按照计数数组中的位置进行排序。最后,我们把排序好的数组复制回原数组即可。
在这个实现中,我们用了两个辅助数组:count和output。count用于记录每个数字出现的次数,output用于存储排序好的数字。在每一轮排序结束后,我们把output中的数据复制回原数组,并释放掉count和output数组的内存。