基数排序的顺序表实现

基数排序是一种非比较排序算法，它通过将待排序元素按照位数切割成不同的数字，然后按照每个位数分别进行排序，最终实现整体排序的目的。下面给出基数排序的顺序表实现：

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

#define RADIX 10 // 基数
#define MAX_LENGTH 100 // 最大长度

// 获取 num 的第 digit 位数字
int get_digit(int num, int digit) {
    int i;
    for (i = 0; i < digit - 1; i++) {
        num /= RADIX;
    }
    return num % RADIX;
}

// 基数排序
void radix_sort(int a[], int n) {
    int i, j, k, digit, m = 1;
    int bucket[RADIX][MAX_LENGTH], count[RADIX];
    memset(count, 0, sizeof(count)); // 初始化 count 数组

    // 找到最大数的位数
    for (i = 0; i < n; i++) {
        for (j = 1; a[i] / j > 0; j *= RADIX);
        if (j > m) {
            m = j;
        }
    }

    // 按照从低位到高位的顺序进行排序
    for (digit = 1; digit <= m; digit *= RADIX) {
        // 将元素按照当前位数放入桶中
        for (i = 0; i < n; i++) {
            bucket[get_digit(a[i], digit)][count[get_digit(a[i], digit)]++] = a[i];
        }

        // 将桶中的元素按照顺序放回原数组
        k = 0;
        for (i = 0; i < RADIX; i++) {
            for (j = 0; j < count[i]; j++) {
                a[k++] = bucket[i][j];
            }
        }

        // 清空桶和计数器
        memset(bucket, 0, sizeof(bucket));
        memset(count, 0, sizeof(count));
    }
}

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

    printf("排序后的结果为：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

在该实现中，我们使用了桶的思想，将待排序元素按照当前位数放入对应的桶中，然后再按照桶中元素的顺序将其放回原数组。这样，经过多次迭代，最终实现了整体排序的目的。