img

基数排序

基数排序（Radix sort）是一种非比较型整数排序算法。

在竞赛中，有时候快排或者说归并排序这样的复杂度有时是不够的，当待排序数据是不太大的自然数时候，可以用计数排序。

如下：

1
2
3
4
5
6
7
8
9
10
11
12
// 计数排序
int Cnt[MAXM];
void counting_sort(unsigned A[], int len)
{
    for (int i = 0; i < len; ++i)
        Cnt[A[i]]++;
    int pos = 0;
    for (int i = 0; pos < len; ++i)
        if (Cnt[i])
            for (int j = 0; j < Cnt[i]; ++j)
                A[pos++] = i;
}

对于计数排序来说，当m比较大的时候，会出现时间和空间的告急

因此需要基数排序。

基数排序也是针对自然数（其他数可以考虑转化为自然数）的排序，它的思想是，对数字的每一位分别进行计数排序。所谓的基数（radix），也就是“进制”的意思，所谓的“每一位”是该进制下的位。

基数排序是怎样运作的了：从低位到高位，依次进行计数排序。

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

  • MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
  • LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

① 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。 ② 从最低位开始，依次进行一次排序。 ③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

如果有一系列小于1000的数进行排序，按照这三趟：

  • 按照个位数进行排序。
  • 按照十位数进行排序。
  • 按照百位数进行排序。

排序后，数列就变成了一个有序序列。

复杂度分析

时间复杂度：\(O(k*N)\) 空间复杂度：\(O(k + N)\) 稳定性：稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];      ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        maxData /= 10;
        ++d;
    }
    return d;
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}