描述: 用基数排序算法,对-100000000 ~100000000以内的整数,进行升序排序。 输入描述: 输入一组整数,数字之间以空格隔开。 输出描述: 按照升序顺序输出结果,数字之间以空格隔开。
时间: 2024-04-16 14:29:19 浏览: 13
```c
#include <stdio.h>
#include <stdlib.h>
int getMaxValue(int* arr, int length) {
int maxValue = arr[0];
for (int i = 1; i < length; i++) {
if (maxValue < arr[i]) {
maxValue = arr[i];
}
}
return maxValue;
}
void countingSort(int* arr, int length, int exp) {
int output[length];
int count[10] = {0};
for (int i = 0; i < length; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = length - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < length; i++) {
arr[i] = output[i];
}
}
void radixSort(int* arr, int length) {
int maxValue = getMaxValue(arr, length);
for (int exp = 1; maxValue / exp > 0; exp *= 10) {
countingSort(arr, length, exp);
}
}
int main() {
int arr[200000];
int length = 0;
printf("请输入一组整数,数字之间以空格隔开:");
while (scanf("%d", &arr[length]) != EOF) {
length++;
}
radixSort(arr, length);
for (int i = 0; i < length; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
以上代码使用基数排序算法对输入的一组整数进行升序排序。
首先,程序定义了一个长度为200000的整数数组 `arr` 和一个变量 `length`,用于存储输入的整数和记录数组长度。
然后,程序通过循环使用 `scanf` 函数从控制台输入一组整数,并将其存储到数组中,直到输入结束(`EOF`)。
接下来,程序调用 `radixSort` 函数对数组进行基数排序。在基数排序中,我们首先找到数组中的最大值,然后根据每个位上的数字进行计数排序。通过多次计数排序,按照个位、十位、百位...的顺序进行排序,最终实现整个数组的升序排序。
最后,程序使用循环打印排序后的数组元素,以空格分隔。
请注意,为了适应输入范围 -100000000 ~ 100000000,我们将数组长度设置为200000,并假设输入的整数个数不会超过该长度。如果输入的整数个数超过该限制,则可能导致数组越界。