基数排序msdC语言例子

基数排序是一种非比较排序算法，它通过将待排序元素按照位数切割成不同的数字，然后按照每个位数分别进行比较排序，从而达到排序的目的。MSD（Most Significant Digit）是基数排序中的一种实现方式，它从最高位开始排序，逐步向低位进行排序。下面是一个基数排序MSD的C语言例子：

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

// 获取数字的某一位数
int getDigit(int num, int digit) {
    int i;
    for (i = 1; i < digit; i++) {
        num /= 10;
    }
    return num % 10;
}

// 基数排序MSD
void radixSortMSD(int arr[], int left, int right, int digit) {
    if (left >= right || digit <= 0) {
        return;
    }
    int i, j, k;
    int count[10] = {0};
    int *bucket = (int *)malloc(sizeof(int) * (right - left + 1));
    // 统计每个桶中的元素个数
    for (i = left; i <= right; i++) {
        count[getDigit(arr[i], digit)]++;
    }
    // 计算每个桶的起始位置
    for (i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    // 将元素放入桶中
    for (i = right; i >= left; i--) {
        j = getDigit(arr[i], digit);
        bucket[count[j] - 1] = arr[i];
        count[j]--;
    }
    // 将桶中的元素复制回原数组
    for (i = left, j = 0; i <= right; i++, j++) {
        arr[i] = bucket[j];
    }
    // 递归排序每个桶中的元素
    for (i = 0, k = left; i < 10; i++) {
        int num = count[i] - k + left;
        radixSortMSD(arr, k, num - 1, digit - 1);
        k = num;
    }
    free(bucket);
}

int main() {
    int arr[] = {53, 3, 542, 748, 14, 214, 154, 63, 616};
    int len = sizeof(arr) / sizeof(arr[0]);
    radixSortMSD(arr, 0, len - 1, 3);
    int i;
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}