用C实现:描述 用基数排序算法,对1000000以内的正整数,进行升序排序。 输入描述 输入一组正整数,数字之间以空格隔开。 输出描述 按照升序顺序输出结果,数字之间以空格隔开。
时间: 2024-02-17 21:02:22 浏览: 52
基数排序C语言实现
以下是使用C语言实现基数排序算法对1000000以内的正整数进行升序排序的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 1000000
#define BASE 10
// 获取数字的某位数,如 get_digit(123, 0) 返回 3,get_digit(123, 1) 返回 2,get_digit(123, 2) 返回 1
int get_digit(int number, int digit) {
int i;
for (i = 0; i < digit; i++) {
number /= BASE;
}
return number % BASE;
}
// 基数排序
void radix_sort(int *arr, int n) {
int i, j, k;
int *count = (int*) malloc(sizeof(int) * BASE); // 计数数组
int *tmp = (int*) malloc(sizeof(int) * n); // 临时数组
// 从个位开始,对每一位进行排序
for (i = 0; i < 9; i++) {
// 初始化计数数组
for (j = 0; j < BASE; j++) {
count[j] = 0;
}
// 统计每个桶中的记录数
for (j = 0; j < n; j++) {
k = get_digit(arr[j], i);
count[k]++;
}
// 将各个桶中的数字个数,转化为各个桶中最后一个数字的下标索引
for (j = 1; j < BASE; j++) {
count[j] += count[j-1];
}
// 将所有桶中记录依次收集到临时数组中,保证是稳定排序
for (j = n-1; j >= 0; j--) {
k = get_digit(arr[j], i);
tmp[count[k]-1] = arr[j];
count[k]--;
}
// 将临时数组中的内容复制到arr中
for (j = 0; j < n; j++) {
arr[j] = tmp[j];
}
}
free(count);
free(tmp);
}
int main() {
int n, i, *arr;
// 读入数字
scanf("%d", &n);
arr = (int*) malloc(sizeof(int) * n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// 进行基数排序
radix_sort(arr, n);
// 输出结果
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
free(arr);
return 0;
}
```
这段代码使用基数排序算法对输入的正整数进行升序排序。具体来说,基数排序先按照个位数字进行排序,再按照十位数字进行排序,以此类推,直到最高位。在每一位上,将数字分配到不同的桶中,然后按照桶的顺序依次收集数字,保证排序的稳定性。
阅读全文