常用12大排序算法之九:基数排序(LSD+MSD)-分配式排序-桶子法排序

2017-04-22 23:05 阅读 1,547 次 评论 0 条

1.基数排序算法简介

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

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

假设我们有一些二元组(a,b),要对它们进行以a为首要关键字,b的次要关键字的排序。我们可以先把它们先按照首要关键字排序,分成首要关键字相同的若干堆。然后,在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起,使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。第二种方式是从最低有效关键字开始排序,称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序,然后对所有的数据按照首要关键字排序。要注意的是,使用的排序算法必须是稳定的,否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序,LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。

基数排序的简单描述就是将数字拆分为个位十位百位,每个位依次排序。因为这对算法稳定要求高,所以我们对数位排序用到上一个排序方法计数排序。因为基数排序要经过d (数据长度)次排序, 每次使用计数排序, 计数排序的复杂度为 On),  d 相当于常量和N无关,所以基数排序也是 O(n)。基数排序虽然是线性复杂度, 即对n个数字处理了n次,但是每一次代价都比较高, 而且使用计数排序的基数排序不能进行原地排序,需要更多的内存, 并且快速排序可能更好地利用硬件的缓存, 所以比较起来,像快速排序这些原地排序算法更可取。对于一个位数有限的十进制数,我们可以把它看作一个多元组,从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序。

例如我们将一个三位数分成,个位,十位,百位三部分。我们要对七个三位数来进行排序,依次对其个位,十位,百位进行排序,如下图:

基数排序算法

很显然,每一位的数的大小都在[0,9]中,对于每一位的排序用计数排序再适合不过。

 

2.基数排序算法的基本原理

基数排序(以整形为例),将整形10进制按每位拆分,然后从低位到高位依次比较各个位。主要分为两个过程:

(1)分配——先从个位开始,根据位值(0-9)分别放到0~9号桶中(比如53,个位为3,则放入3号桶中);

(2)收集——再将放置在0~9号桶中的数据按顺序放到数组中;

重复(1)(2)过程,从个位到最高位(比如32位无符号整形最大数4294967296,最高位10位)。

基数排序算法

 

3.基数排序算法基本步骤

举例分析:待排序数组[62,14,59,88,16]简单点五个数字

(1)分配10个桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样

|  0  |  0  | 62 |  0  | 14 |  0  | 16 |  0  |  88 | 59 |

|  0  |  1  |  2  |  3  |  4 |  5  |  6  |  7  |  8  |  9  |桶编号

(2)将桶里的数字顺序取出来

输出结果:[62,14,16,88,59]

(3)再次入桶,不过这次以十位数的数字为准,进入相应的桶,变成下边这样:

由于前边做了个位数的排序,所以当十位数相等时,个位数字是由小到大的顺序入桶的,就是说,入完桶还是有序

|  0  | 14,16 |  0  |  0  |  0  | 59 | 62  | 0  | 88  |  0  |

|  0  |  1      |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |桶编号

 因为没有大过100的数字,没有百位数,所以到这排序完毕。

(4)顺序取出即可

最后输出结果:[14,16,59,62,88]

 

4.基数排序算法复杂度分析

(1)平均时间复杂度:O(dn)(d即表示整形的最高位数);

(2)空间复杂度:O(10n) (10表示0~9,用于存储临时的序列);

(3)稳定性:稳定。

 

5.基数排序算法C语言源代码

 

6.基数排序算法C++源代码

(1)基于LSD的基数排序算法

(2)基于数组的基数排序算法

 

(3)基于静态链表的基数排序算法

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用12大排序算法之九:基数排序(LSD+MSD)-分配式排序-桶子法排序 | 算法君

发表评论


表情