基数排序 订阅
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。 展开全文
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。
信息
领    域
计算机算法
类    别
分配式排序
方    法
最高位优先法和最低位优先
发明者
赫尔曼·何乐礼
中文名
基数排序
外文名
Radix sort
别    称
“桶子法”
基数排序基本解法
以LSD为例,假设原来有一串数值如下所示:73, 22, 93, 43, 55, 14, 28, 65, 39, 81首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:01 812 223 73 93 434 145 55 65678 289 39接下来将这些桶子中的数值重新串接起来,成为以下的数列:81, 22, 73, 93, 43, 14, 55, 65, 28, 39接着再进行一次分配,这次是根据十位数来分配:01 142 22 283 394 435 556 657 738 819 93接下来将这些桶子中的数值重新串接起来,成为以下的数列:14, 22, 28, 39, 43, 55, 65, 73, 81, 93这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
收起全文
精华内容
下载资源
问答
  • 基数排序

    2021-01-20 11:33:57
    基数排序: 思想:基数排序可以看成是桶排序的扩展,以整数排序为例,主要思想是将整数按位数划分,准备 10 个桶,代表 0 – 9,根据整数个位数字的数值将元素放入对应的桶中,之后按照输入赋值到原序列中,依次对十...
  • 基数排序基数排序基数排序基数排序基数排序

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,879
精华内容 28,351
关键字:

基数排序