数据结构笔记(十四)排序算法之基数排序

发布于 / 程序猿 / 2 条评论

基数排序(英文:Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。

排序原理

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

基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反由键值的最左边开始,后面会谈到。

图文演示

对序列3221, 1, 10, 9680, 577, 9420, 7, 4793, 2030, 3138, 82, 2599, 743进行基数排序。

  • 第一次,按照个位数分配与收集

  • 第二次,按照十位数分配与收集

  • 第三次,按照百位数分配与收集

  • 第四次,按照千位数分配与收集

  • 排序完毕,序列有序

算法实现

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
using namespace std;
const int maxn = 100000000;
const int Max = 30000;
int a[maxn];

// 基数数量与维度
const int RADIX_CNT = 10;
const int RADIX[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

int R[RADIX_CNT][1000010];
int R_CNT[RADIX_CNT];

void display(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << a[i] << "  ";
        if ((i+1) % 10 == 0)
            cout << endl;
    }
}

void radix_sort(int a[], int n)
{
    for (int pos = 0; pos < RADIX_CNT; ++pos)
    {
        memset(R_CNT, 0, sizeof(R_CNT)); // 清零
        // 分配
        for (int i = 0; i < n; ++i)
        {
            int t = a[i] / RADIX[pos] % 10; // 得到相应位数上的数
            R[t][R_CNT[t]++] = a[i]; // 记录保存
        }
        // 收集
        int k = 0;
        for (int i = 0; i < RADIX_CNT; ++i)
            for (int j = 0; j < R_CNT[i]; ++j)
                a[k++] = R[i][j]; // 再赋值
    }
}

void getTime(void f(int [], int), int a[], int n)
{
    clock_t _start, _end;
    _start = clock();
    f(a, n);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
}

int main()
{
    srand((unsigned)time(NULL)); // 设置随机数种子
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % Max;
    //display(a, maxn);
    getTime(radix_sort, a, maxn);
    //display(a, maxn);
    return 0;
}
  • 序列3466, 2628, 3300, 3215, 3631, 2282, 2935 3774, 2785, 3216排序过程
3466  2628  3300  3215  3631  2282  2935  3774  2785  3216
3300  3631  2282  3774  3215  2935  2785  3466  3216  2628 // 个位
3300  3215  3216  2628  3631  2935  3466  3774  2282  2785 // 十位
3215  3216  2282  3300  3466  2628  3631  3774  2785  2935 // 百位
2282  2628  2785  2935  3215  3216  3300  3466  3631  3774 // 千位
  • 实测不同规模序列程序运行时间。
对于30000以内的数
当 maxn = 10000     时,时间为 0s
当 maxn = 100000    时,时间为 0.012s
当 maxn = 1000000   时,时间为 0.15s
当 maxn = 10000000  时,时间为 1.214s
当 maxn = 100000000 时,时间为 8.21s

以上实现代码还可以改进,没必要每次都循环十次,只需要找到最大的数,然后求出它的位数,即循环所需的次数,赋值给RADIX_CNT

算法分析

  • 时间复杂度

基数排序的时间复杂度是O(k·n),其中n是排序元素个数,k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n)),k的大小取决于数字位的选择(比如比特位数),和待排序数据所属数据类型的全集的大小;k决定了进行多少轮处理,而n是每轮处理的操作数目。

如果考虑和比较排序进行对照,基数排序的形式复杂度虽然不一定更小,但由于不进行比较,因此其基本操作的代价较小,而且在适当选择的之下,k一般不大于logn,所以基数排序一般要快过基于比较的排序,比如快速排序。

  • 稳定性

基数排序是稳定排序。

补充

为什么基数排序只有从最低位开始才是“稳定的排序算法”?

  • Adder

从高位可以,但是麻烦啊。
道理是基数排序每次都调用一个稳定排序,也就是说这一轮比不出大小的数据,保持原来的相对顺序不变。而数字比较大小就是从高位开始,比不出大小去看低位,当然应该让低位先排出“原来的相对顺序”了。
从高位开始排,就要分段了,每排完一位,把分不出大小的几个当成一段,一段段的排,不要让排完的数据跨段移动,保证这一段的数都比下一段小,排到最后每段就只有一个数了。这样就完全没有利用到每次调用的都是稳定排序这一点,感觉上丑多了,也没什么意思。

  • 高云璐

基数排序,又称为bucket sort,因为Hollerith当时的人们是拿着真的桶进行排序的。如果数字从高位开始排序,意味着有n位,就得有10^n个桶。因为你先排最高位,然后对于这个最高位又要分出十个桶排下一位。比如现在有13,23,12,22,11这五个数。你先为高位排序,就相当于把十位为1的分在一个桶1里(13,12,11),十位为2的分在一个桶2(22,23)里。然后在桶1和桶2之中剩下的元素排序((11),(12),(13))和((22),(23))。这样如果有很多位数,桶就很多。但是从最低位开始排就只需要10个桶,每移动一位,就用针对那一位排序(把元素扔进桶里)。所以不会占用大量的桶。所以,低位排序优于高位排序。

说明

文中基础知识和理论分析部分来源于维基百科基数排序,补充问题回答来源于知乎

推荐阅读


The end.
2018-01-01 星期一

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(十四)排序算法之基数排序
  1. 碧海长天

    想问候一下,可是没找到留言的位置,,,尴尬 新年快乐~

    1. TaiFu_S
      @碧海长天

      哈哈,谢谢!我没有单独弄留言板了,一般都是在 关于 页面留言。