#include "cstdio"
//找到最大值
int GetMax(int arr[], int length){
int res = arr[0];
for(int count = 0; count < length; count++){
if(arr[count] > res){
res = arr[count];
}
}
return res;
}
// 使用计数排序根据有效位置对元素进行排序
void CountSort(int arr[], int length, int place){
int Output[length];
int Count[10] = {0};
// 计算元素
for(int i = 0; i < length; i++){
int index = arr[i] / place;
Count[index % 10]++;
}
// 计算累计计数
for(int j = 1; j < 10; j++){
Count[j] += Count[j - 1];
}
// 将元素按顺序排列
for(int m = length - 1; m >= 0; m--){
int index = arr[m] / place;
Output[Count[index % 10] - 1] = arr[m];
Count[index % 10]--;
}
// 将已排序的元素返回原始数组
for(int n = 0; n < length; n++){
arr[n] = Output[n];
}
}
// 实现基数排序
void Radix_sort(int arr[], int length){
int max_num = GetMax(arr, length);
// 对元素应用计数排序
for(int place = 1; max_num / place > 0; place *= 10){
CountSort(arr, length, place);
}
}
void Display(int arr[], int length) {
for (int count = 0; count < length; count++) {
printf("%d, ", arr[count]);
}
printf("\n");
}
int main() {
int arr[] = {8, 32, 22, 73, 95, 13, 9, 82, 23, 46, 71, 52, 90, 53, 77, 75, 65, 64, 74, 24};
int length = sizeof(arr) / sizeof(arr[0]);
Display(arr, length);
Radix_sort(arr, length);
Display(arr, length);
return 0;
}