基数排序算法详解

本文共716个字,预计阅读时间需要2分钟。

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

实现方法:

最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。
最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。
(1)假设有欲排数据序列如下所示:
73 22 93 43 55 14 28 65 39 81首先根据个位数的数值,在遍历数据时将它们各自分配到编号0至9的桶(个位数值与桶号一一对应)中。
分配结果(逻辑想象)如下图所示:
分配结束后。接下来将所有桶中所盛数据按照桶号由小到大(桶中由顶至底)依次重新收集串起来,得到如下仍然无序的数据序列:
81 22 73 93 43 14 55 65 28 39
接着,再进行一次分配,这次根据十位数值来分配(原理同上),分配结果(逻辑想象)如下图所示:

代码:

C:

C++:

 

读者评分
[评分人数: 5 平均分: 2.2]

评论

OmegaXYZ