基于桶的基数排序

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


基数排序

基数排序(Radix Sort)算法是一种非比较的排序算法,早在 1887 年 Herman Hollerith 就已经在打孔卡片制表机中使用该算法。一般多用于对整数的排序,但由于整数与某些字符能互相转换,所以它也能够用于字符串的排序。简单来说,基数排序算法就是将整数或字符串切分成不同的数字或字符,然后按对应位置的数或字符分别进行比较。

稳定性

基数排序具备稳定性,即能保证相同值元素之间的相对顺序在排序前后一致。基于计数排序的方式主要是通过对计数数组进行前缀和运算,外加通过额外的辅助数组,最后逆序循环将待排序数组中的所有元素放置到辅助数组中,以达到稳定性效果。而基于桶的方式则是通过在每个桶中控制顺序,从而达到稳定性效果。

时间复杂度

基数排序的时间复杂度为Ο(w(n+k)),其中n为待排序数组长度;k为关键字的取值范围,等于进制数,比如十进制则k=10;w为待排序数组元素最大的字长,比如最大字长元素为358,则字长为3。

当k确定后,时间复杂度其实就是O(wn),但有时还需要考虑字长w,不能简单将其认定为常数。假如取基数为B(即B进制),待排序集合最大元素为N,则w为大于$log_BN$的最小整数。所以并不是说基数排序就一定完胜最好的比较排序$(O(n * log n))$,实际过程中还跟所取的基和待排序集合具体的情况相关。

排序方式

基数排序可以采用最高有效数位(MSD)和最低有效数位(LSD)两种方式,其中LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。

在算法过程中,对于LSD,对某个有效数位分配后需要执行一次合并,然后再对下一位分配;而对于MSD,对某个有效数位分配后不执行合并,它将继续对相同高位的元素继续进行分配,直到无法继续分配时执行合并操作。

基于桶实现

基于桶方式是指使用桶作为辅助工具,过程中循环每个有效数位将元素分配到对应的桶中,从而实现基数排序。

基于桶方式的基数排序的操作步骤如下:

  1. 确定桶的数量,由进制数确定,比如十进制则桶的数量为10,分别代表0到9,并且每个桶内的结构为队列。
  2. 从最低有效位到最高有效位,针对每个有效位执行步骤3到步骤5。
  3. 按顺序遍历待排序数组,根据当前有效位将它们分配到对应桶的队列中。
  4. 按桶编号顺序进行遍历,将每个桶中队列按顺序收集到原数组中。
  5. 选择下一个有效位执行步骤2到步骤4,直到所有有效位处理完得到的结果即是最终的结果。

同样是对前面的8位小学生的语数英总成绩进行基于桶方式的基数排序操作。一共有8个学生,所以待排序数组长度为8。而且因为使用十进制,所以桶的索引范围是0-9。此外每个桶对应创建一个队列,这里假设队列长度为5,长度也可以为待排序数组长度,但实际中更多使用动态扩展策略。

image

第一阶段:针对个位数将元素放到对应的桶中。

待排序数组的第一个元素的健值为198,放到编号8的桶中。

image

第二个元素的健值为248,放到编号为8的桶中。

image

第三个元素的健值为98,放到编号为8的桶中。

image

第四个元素的健值为247,放到编号为7的桶中。

image

类似地,将剩下的元素都放到对应桶中的队列,可以看到每个桶中的队列维护了顺序性。

image

接着按桶顺序将桶中队列输出到原数组中,先输出编号为0的桶。

image

接着输出编号为7的桶。

image

再输出编号为8的桶。

image

最后输出编号为9的桶。

image

第二阶段:针对十位数将元素放到对应的桶中。

待排序数组的第一个元素的健值为80,放到编号8的桶中。

image

第一个元素的健值为247,放到编号4的桶中。

image

将剩下的元素都放到对应桶中的队列。

image

将编号为4的桶的队列输出到原数组中。

image

将编号为8的桶的队列输出到原数组中。

image

将编号为9的桶的队列输出到原数组中。

image

第三阶段:针对百位数将元素放到对应的桶中。

第一个元素的健值为247,放到编号2的桶中。

image

第二个元素的健值为247,放到编号2的桶中。

image

将剩下的元素都放到对应桶中的队列。

image

将编号为0的桶的队列输出到原数组中。

image

将编号为1的桶的队列输出到原数组中。

image

将编号为2的桶的队列输出到原数组中。

image

至此,以上完成整个排序过程。

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 基于桶的基数排序
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏