描述 用基数排序算法,对100000000以内的正整数,进行降序排序。 输入描述 输入一组正整数,数字之间以空格隔开。 输出描述 按照降序顺序输出结果,数字之间以空格隔开。
时间: 2024-04-16 07:29:04 浏览: 20
你可以使用以下的 C 代码来实现对输入的正整数进行基数排序,并按照降序输出结果:
```c
#include <stdio.h>
#include <stdlib.h>
// 获取数字的某个位上的值
int getDigit(int number, int digit) {
int divisor = 1;
for (int i = 0; i < digit; i++) {
divisor *= 10;
}
return (number / divisor) % 10;
}
// 获取数组中最大的数
int getMax(int array[], int n) {
int max = array[0];
for (int i = 1; i < n; i++) {
if (array[i] > max) {
max = array[i];
}
}
return max;
}
// 使用基数排序算法进行排序
void radixSort(int array[], int n) {
int max = getMax(array, n); // 获取最大的数
// 对每个位数进行计数排序
for (int digit = 1; max / digit > 0; digit *= 10) {
int count[10] = {0}; // 计数数组,用于记录每个位上每个数字的个数
int output[n]; // 输出数组,用于存储排序结果
// 统计每个位上每个数字的个数
for (int i = 0; i < n; i++) {
count[getDigit(array[i], digit)]++;
}
// 将计数数组转换为前缀和数组
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 根据计数数组将元素放入输出数组中,同时更新计数数组
for (int i = n - 1; i >= 0; i--) {
output[count[getDigit(array[i], digit)] - 1] = array[i];
count[getDigit(array[i], digit)]--;
}
// 将结果复制回原始数组
for (int i = 0; i < n; i++) {
array[i] = output[i];
}
}
}
int main() {
int n; // 数组的长度
int array[100]; // 数组
printf("请输入正整数数组的长度:");
scanf("%d", &n);
printf("请输入正整数数组:");
for (int i = 0; i < n; i++) {
scanf("%d", &array[i]);
}
radixSort(array, n); // 使用基数排序算法进行排序
// 按照降序顺序输出结果
for (int i = n - 1; i >= 0; i--) {
printf("%d ", array[i]);
}
printf("\n");
return 0;
}
```
你可以按照输入描述的格式输入正整数数组的长度和数组元素,程序将使用基数排序算法对数组进行降序排序,并输出结果。输出的数字之间以空格进行分隔。