基数排序(Radix Sort)与快速排序不同,是一种非比较的排序算法,本质上属于一种特殊的桶排序,将的范围缩小到了$|\sum|$个,其中$|\sum|$为偏序字符集的大小(对于整型而言就是10)。

算法的核心思想是从低位到高位(高位到低位)按位比较

例如对于以下序列

$$1,23,456,34,798,97$$

算法首先比较其个位(或最高位百位),放入桶中

0123456789
1 2334 45697798

依次取出,序列变为

$$1,23,34,456,97,798$$

再对十位进行同样的操作

0123456789
1 2334 456 97,798

序列变为

$$1,23,34,456,97,798$$

同样的操作再对百位进行一次,序列变为

$$1,23,34,97,456,798$$

即为最终排序结果。

需要注意的是,取出与放入是存在顺序的。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

int n;
int d[N];

void radix_sort(int data[], int n, int maxn) {
    int max_bit = 0;
    for ( ; maxn; maxn /= 10)
        ++max_bit;

    int count[10], temp[n], radix = 1;
    for ( int i = 1; i <= max_bit; ++i ) {
        memset(count, 0, sizeof count);
        for ( int j = 0; j < n; ++j )
            ++count[(data[j] / radix) % 10];

        for ( int j = 1; j < 10; ++j )
            count[j] = count[j - 1] + count[j];

        for ( int j = n - 1; j >= 0; --j ) {
            int k = (data[j] / radix) % 10;
            temp[count[k] - 1] = data[j];
            --count[k];
        }

        for ( int j = 0; j < n; ++j )
            data[j] = temp[j];

        radix *= 10;
    }
}

int main() {
    scanf("%d", &n);

    int maxn = 0;
    for ( int i = 0; i < n; ++i ) {
        scanf("%d", &d[i]);
        maxn = max(maxn, d[i]);
    }

    radix_sort(d, n, maxn);

    for ( int i = 0; i < n; ++i )
        printf("%d ", d[i]);

    return 0;
}

算法性能

算法时间复杂度$O(kn)$,空间复杂度$O(k+n)$,其中$k$为数字位数,$n$为排序元素个数。

Last modification:August 9th, 2020 at 02:40 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏