首页 > 编程笔记 > 算法

C语言基数排序（附带源码和解析）

基数排序是一种非比较型的整数排序算法，它的工作原理与我们给扑克牌排序的方式非常相似。这种算法通过逐位比较，从最低有效位到最高有效位，将待排序的元素分配到不同的桶中，然后收集这些桶中的元素，最终得到一个有序序列。


基数排序特别适用于整数或字符串的排序，尤其是当被排序的数据范围不是很大时，它的性能表现得更加出色。

基数排序的基本原理

基数排序的核心思想是利用整数的位值特性。对于一个 n 位整数，我们可以从最低位开始，依次对每一位进行排序。每一轮排序都会将当前位相同的数字放入同一个桶中，然后按照桶的顺序收集数字。经过 n 轮排序后，整个序列就变得有序了。


让我们通过一个简单的例子来理解这个过程：

原始数组：170, 45, 75, 90, 802, 24, 2, 66

第一轮（个位）：
桶0：170, 90
桶2：802, 2
桶4：24
桶5：45, 75
桶6：66

收集后：170, 90, 802, 2, 24, 45, 75, 66

第二轮（十位）：
桶0：802, 2
桶1：170
桶2：24
桶4：45
桶6：66
桶7：75
桶9：90

收集后：802, 2, 24, 45, 66, 170, 75, 90

第三轮（百位）：
桶0：2, 24, 45, 66, 75, 90
桶1：170
桶8：802

最终结果：2, 24, 45, 66, 75, 90, 170, 802

通过这个例子，我们可以清晰地看到基数排序的每一步操作。每一轮排序都会使数组更加有序，直到最后完全有序。

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};

    // 统计出现次数
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // 修改 count[i]，使其包含实际在输出数组中的位置
    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]--;
    }

    // 将输出数组复制回 arr[]，这样 arr[] 就包含了当前位排序后的数字
    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, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：\n");
    printArray(arr, n);

    radixSort(arr, n);

    printf("排序后数组：\n");
    printArray(arr, n);

    return 0;
}

运行结果：

原始数组：
170 45 75 90 802 24 2 66
排序后数组：
2 24 45 66 75 90 170 802

这段代码实现了完整的基数排序过程。getMax 函数用于找出数组中的最大值，这决定了我们需要进行多少轮排序。countSort 函数实现了计数排序，它是基数排序的核心。radixSort 函数则是基数排序的主体，它调用 countSort 函数对每一位进行排序。

总结

基数排序是一种独特而高效的排序算法，特别适用于整数和字符串的排序。


基数排序的时间复杂度是 O(d * (n + k))，其中 d 是最大数字的位数，n 是待排序数字的数量，k 是进制（这里是 10，因为我们使用十进制）。当 d 和 k 都是常数时，基数排序的时间复杂度就变成了 O(n)，这在理论上比基于比较的排序算法（如快速排序、归并排序等）的 O(nlogn) 更优。


基数排序有以下优点：

 

然而，基数排序也有一些限制：


你可能还想关注其它 9 种排序算法：

  1. C语言冒泡排序（附带源码和解析）
  2. C语言快速排序（附带源码和解析）
  3. C语言选择排序（附带源码和解析）
  4. C语言插入排序（附带源码和解析）
  5. C语言希尔排序（附带源码和解析）
  6. C语言归并排序（附带源码和解析）
  7. C语言堆排序（附带源码和解析）
  8. C语言计数排序（附带源码和解析）
  9. C语言桶排序（附带源码和解析）

声明：《算法系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。

相关文章

精选内容