C语言基数排序算法详解（从零开始掌握高效非比较排序）

基数排序的基本步骤

1. 找出数组中最大值，确定最大位数。
2. 从最低位（个位）开始，对每一位进行“分配”和“收集”操作。
3. 使用计数排序或桶排序作为子过程，对当前位进行排序。
4. 重复上述过程，直到处理完最高位。

C语言基数排序实现

下面我们用C语言完整实现一个基数排序程序。该程序使用“桶”（即二维数组）来模拟分配与收集过程。

#include <stdio.h>#include <stdlib.h>// 获取数组中的最大值int getMax(int arr[], int n) {    int max = arr[0];    for (int i = 1; i < n; i++) {        if (arr[i] > max)            max = arr[i];    }    return max;}// 对某一位进行计数排序void countSort(int arr[], int n, int exp) {    int output[n]; // 输出数组    int count[10] = {0}; // 0~9 的计数器    // 统计当前位上各数字出现的次数    for (int i = 0; i < n; i++)        count[(arr[i] / exp) % 10]++;    // 将计数数组转换为累积计数    for (int i = 1; i < 10; i++)        count[i] += count[i - 1];    // 构建输出数组（从后往前保证稳定性）    for (int i = n - 1; i >= 0; i--) {        output[count[(arr[i] / exp) % 10] - 1] = arr[i];        count[(arr[i] / exp) % 10]--;    }    // 将排序结果复制回原数组    for (int i = 0; i < n; i++)        arr[i] = output[i];}// 基数排序主函数void radixsort(int arr[], int n) {    // 找到最大值以确定位数    int m = getMax(arr, n);    // 对每一位进行计数排序    for (int exp = 1; m / exp > 0; exp *= 10)        countSort(arr, n, exp);}// 打印数组void printArray(int arr[], int n) {    for (int i = 0; i < n; i++)        printf("%d ", arr[i]);    printf("\n");}// 主函数测试int main() {    int arr[] = {170, 45, 75, 90, 2, 802, 24, 66};    int n = sizeof(arr) / sizeof(arr[0]);    printf("原始数组: \n");    printArray(arr, n);    radixsort(arr, n);    printf("排序后数组: \n");    printArray(arr, n);    return 0;}

代码解析

• getMax()：用于找出数组中的最大值，从而确定需要处理多少位。
• countSort()：对指定“位”（由 exp 表示，如 1 表示个位，10 表示十位）进行稳定排序。
• radixsort()：主排序函数，循环调用 countSort 处理每一位。

时间与空间复杂度

- 时间复杂度：O(d × (n + k))，其中 d 是最大数的位数，n 是元素个数，k 是基数（通常为10）。

- 空间复杂度：O(n + k)，用于存储输出数组和计数数组。

适用场景

基数排序特别适合处理整数或固定长度字符串的排序。当数据范围不大、位数较少时，其效率远高于快速排序等比较型算法。这也是为什么学习基数排序C语言实现对提升算法能力非常有帮助。

总结

通过本教程，你已经掌握了排序算法入门中一个高效且有趣的算法——基数排序。它不依赖比较，而是利用数字的结构特性进行排序。希望你能动手运行上面的代码，加深理解。记住，多练习才是掌握C语言基数排序的关键！