生成基数排序的c语言实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 1000 // 数据范围为0~999

// 获取数字的第d位数字（从右往左数）
int getDigit(int num, int d) {
int i;
for (i = 1; i < d; i++) {
num /= 10;
}
return num % 10;
}

// 基数排序
void radixSort(int *arr, int n) {
int i, j, d, max = 0;
int *count, *tmp; // 用于计数和存储临时结果的数组

// 获取最大值
for (i = 0; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}

// 从低位到高位依次进行排序
for (d = 1; max / d > 0; d *= 10) {
count = (int*)calloc(10, sizeof(int)); // 初始化计数数组为0
tmp = (int*)calloc(n, sizeof(int)); // 初始化临时数组为0

// 统计每个桶中的元素个数
for (i = 0; i < n; i++) {
count[getDigit(arr[i], d)]++;
}

// 将元素个数转化为索引
for (i = 1; i < 10; i++) {
count[i] += count[i - 1];
}

// 将元素放入对应的桶中
for (i = n - 1; i >= 0; i--) {
j = getDigit(arr[i], d);
tmp[count[j] - 1] = arr[i];
count[j]--;
}

// 将临时数组赋值给原数组
for (i = 0; i < n; i++) {
arr[i] = tmp[i];
}

// 释放内存
free(count);
free(tmp);
}
}

// 测试
int main() {
int arr[] = { 53, 3, 542, 748, 14, 214, 154, 63, 616 };
int n = sizeof(arr) / sizeof(arr[0]);
int i;

printf("原数组：");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

radixSort(arr, n);

printf("排序后：");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}