基数排序算法 c语言

基数排序算法是一种稳定排序算法，适用于数值比较大的数据之间的排序。它不涉及元素之间的比较，而是根据基数将数据存放到相应的“桶”里，经过多趟排序过程，最终实现对一组散乱数据的排序。

基数排序的实现思路如下：
1. 首先确定待排序数组中最大值的位数，记为max_digits。
2. 创建10个桶，对每个桶进行计数初始化。
3. 从低位到高位，依次对待排序数组中的元素进行入桶操作。
4. 将桶中的元素按顺序依次取出，得到新的排序结果。
5. 重复第3和第4步，直到所有元素中的最高位已经处理完毕。
6. 最终得到的排序结果就是基数排序的结果。

下面是基数排序的C语言实现示例：

#include <stdio.h>

// 获取数组中最大值的位数
int getMaxDigits(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int digits = 0;
    while (max > 0) {
        max /= 10;
        digits++;
    }
    return digits;
}

// 对数组进行基数排序
void radixSort(int arr[], int n) {
    int max_digits = getMaxDigits(arr, n);
    int count[10];
    int bucket[n];
    int divisor = 1;
    
    for (int i = 0; i < max_digits; i++) {
        // 初始化计数数组和桶
        for (int j = 0; j < 10; j++) {
            count[j] = 0;
        }
        
        // 统计每个桶中的元素个数
        for (int j = 0; j < n; j++) {
            int digit = (arr[j] / divisor) % 10;
            count[digit]++;
        }
        
        // 计算每个桶中元素的起始位置
        for (int j = 1; j < 10; j++) {
            count[j] += count[j - 1];
        }
        
        // 将元素按照当前位的值放入对应的桶中
        for (int j = n - 1; j >= 0; j--) {
            int digit = (arr[j] / divisor) % 10;
            bucket[count[digit] - 1] = arr[j];
            count[digit]--;
        }
        
        // 将桶中的元素按顺序放回原数组
        for (int j = 0; j < n; j++) {
            arr[j] = bucket[j];
        }
        
        divisor *= 10;
    }
}

int main() {
    int arr[] = {53, 89, 150, 36, 633, 233, 197, 9, 473, 27};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    radixSort(arr, n);
    
    printf("\n排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}