C语言基数排序代码实现

基数排序是一种非比较整数排序算法，它通过将待排序的整数按位数切割成不同的数字，然后按每个位数分别比较，从最低有效位到最高有效位逐次排序。以下是简单的C语言基数排序代码实现：

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

#define MAX_DIGITS 10

void countingSort(int arr[], int exp, int n) {
    int output[n];
    int count[MAX_DIGITS + 1] = {0}, i;

    // 计算每个桶（0-9）内的元素个数
    for (i = 0; i < n; i++) {
        count[(arr[i]/exp)%10]++;
    }

    // 统计每个桶内元素的位置
    for (i = 1; i < MAX_DIGITS; i++) {
        count[i] += count[i - 1];
    }

    // 将元素放入相应的桶中
    for (i = n - 1; i >= 0; i--) {
        output[count[(arr[i]/exp)%10] - 1] = arr[i];
        count[(arr[i]/exp)%10]--;
    }

    // 把排序后的元素复制回原数组
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

// 主函数
void radixsort(int arr[], int n) {
    int max = arr[0], m = 1;
    // 找出最大数的位数
    while (max/m > 0) {
        countingSort(arr, m, n);
        m *= 10;
    }
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr)/sizeof(arr[0]);

    printf("Original array: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    radixsort(arr, n);

    printf("\nSorted array: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}