用C语言实现基数排序,输入任意10个数后,能够按从大到小排序输出。
时间: 2024-10-11 19:04:26 浏览: 32
c语言之基数排序.pdf
基数排序是一种非比较整数排序算法,它通过将整数按照位数切割成不同的数字,然后对每个位分别进行排序,最终达到整个序列有序的目的。以下是使用C语言实现基数排序的基本步骤:
1. 定义最大值和最小值,找到待排序数组中的最大数和最小数,确定排序需要的最大位数。
2. 对于每一位(从最低位开始),创建10个辅助数组(假设十进制,所以10个桶),将当前位上等于0-9的元素放入对应的桶中。
3. 分别对每个桶内的元素进行原地排序(例如,可以递归进行下一位的基数排序)。
4. 将所有桶中的元素依次合并回原数组,完成这一位的排序。
5. 重复以上过程,直到最高位,这时数组已经按照从低位到高位的顺序排列好了。
6. 最后反转整个数组,因为最后一步排序是从高到低,所以结果是从大到小。
下面是一个简单的示例代码(这里简化了输入处理和数组处理部分):
```c
#include <stdio.h>
#include <stdlib.h>
void countingSort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
void radixsort(int arr[], int n) {
int max_value = *max_element(arr, arr + n);
int exp = 1;
while (max_value / exp > 0) {
countingSort(arr, n, exp);
exp *= 10;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {/* 10个输入数值 */};
int n = sizeof(arr) / sizeof(arr[0]);
radixsort(arr, n);
printf("Sorted array in descending order: \n");
printArray(arr, n);
return 0;
}
```
阅读全文