基数排序：算法设计中的高效排序利器

创作时间:

2025-01-22 20:47:54

作者:

@小白创作中心

基数排序：算法设计中的高效排序利器

基数排序是一种独特的非比较型整数排序算法，通过按位排序实现高效性。它不仅在理论上有重要意义，也在实际应用中展现出强大的实用价值。

基数排序的原理

基数排序的核心思想是将整数按位数拆分，从最低位到最高位依次进行稳定排序。这种排序方式可以采用两种不同的顺序：LSD（Least Significant Digital，最低有效位优先）和MSD（Most Significant Digital，最高有效位优先）。

LSD（最低位优先）

LSD方式从数值的最右边（低位）开始排序。这种排序方式从数据的最低位开始处理，逐步向高位进行，适用于位数较多的数据排序，因为它从较低位开始，可以更快地处理大量数据。

MSD（最高位优先）

MSD则从数值的最左边（高位）开始排序。与LSD相反，MSD从数据的最高位开始处理，逐步向低位进行。这种方式适用于位数较少但高位有较大差异的数据排序。

以LSD为例，对一串数据进行排序的过程如下：

278 109 063 930 589 184 505 269 008 083

确定基数和分发趟数：这是十进制数据，基数为0~9，最高位是百位，所以分发趟数为3。
分发和收集过程：

第一趟分发（个位）：

0号桶：930, 008
1号桶：109
3号桶：063
4号桶：184
5号桶：278, 505
8号桶：589
9号桶：269
收集后序列：930, 008, 109, 063, 184, 278, 505, 589, 269

第二趟分发（十位）：

0号桶：008
1号桶：109, 184
3号桶：930
5号桶：505
6号桶：063
7号桶：278
8号桶：589
9号桶：269
收集后序列：008, 109, 184, 930, 505, 063, 278, 589, 269

第三趟分发（百位）：

0号桶：008, 063
1号桶：109, 184
2号桶：269, 278
5号桶：505, 589
9号桶：930
收集后序列：008, 063, 109, 184, 269, 278, 505, 589, 930

效率分析：

时间复杂度：O(d(n+radix))，其中d为关键码个数，n为记录数，radix为基数
空间复杂度：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针

代码实现

以下是基数排序的C++代码实现：

#include <queue>
#include <cmath>

std::queue<int> q[10]; //0~9一共10个基数,需要10个队列(先进先出)

//获取对应位的值
int GetDigit(int value, int k) {
    int tmp;
    while (k-- >= 0) {
        tmp = value % 10;
        value /= 10;
    }
    return tmp;
}

//获取最大位数
int getNumberOfDigits(int number) {
    if (number == 0) return 1;  // 特殊情况：0 的位数为 1
    if (number < 0) number = -number;  // 转换为正数
    return (int)log10(number) + 1; //log后取整+1就能得到位数
}

//分发
void Distribute(int *a,int size, int k) {
    for (int i = 0 ; i < size; ++i) {
        int digit = GetDigit(a[i],k);
        q[digit].push(a[i]);
    }
}

//收集
void Collect(int *a, int size) {
    int j = 0;
    for (int i = 0; i < 10;i++) {
        while (!q[i].empty()) {
            a[j++] = q[i].front();
            q[i].pop();
        }
    }
}

void RadixSort(int* a, int size) {
    int k = getNumberOfDigits(a[0]); //获取最大数的位数
    for (int i = 0; i < k; i++) {
        Distribute(a, size, i);
        Collect(a, size);
    }
}