排序(8):基数排序

2018年1月4日15:56:01 6 9,016 °C
摘要

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

排序(8):基数排序

一、前言

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

二、算法思想

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

算法步骤:

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

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

不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

我们知道,任何一个阿拉伯数,它的各个位数上的基数都是以 0~9 来表示的,所以我们不妨把 0~9 视为 10 个桶。

我们先根据序列的个位数的数字来进行分类,将其分到指定的桶中。例如:R[0] = 50,个位数上是 0,将这个数存入编号为 0 的桶中。

排序(8):基数排序

分类后,我们在从各个桶中,将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时,得到的序列就是个位数上呈递增趋势的序列。

按照个位数排序: {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

接下来,可以对十位数、百位数也按照这种方法进行排序,最后就能得到排序完成的序列。

动态效果示意图:

排序(8):基数排序

1、代码

C++:

运行结果如下图所示:

排序(8):基数排序

Python:

三、算法分析

1、基数排序的性能

排序(8):基数排序

其中,d代表数组元素最高为位数,n代表元素个数。

2、时间复杂度

这个时间复杂度比较好计算:count * length;其中 count 为数组元素最高位数,length为元素个数;所以时间复杂度:O(n * d)

3、空间复杂度

空间复杂度是使用了两个临时的数组:10 + length;所以空间复杂度:O(n)。

4、算法稳定性

在基数排序过程中,每次都是将当前位数上相同数值的元素统一“装桶”,并不需要交换位置。所以基数排序是稳定的算法。

 

本站整理自:

http://www.cnblogs.com/jingmoxukong/p/4311237.html

https://www.cnblogs.com/chunguang/p/5892768.html

https://61mon.com/index.php/archives/204/

https://yq.aliyun.com/articles/11331

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:6   其中:访客  3   博主  3

    • avatar zyh 来自天朝的朋友 谷歌浏览器 Windows 10 河南省郑州市 联通 1

      python算法里第60行,循环条件 for i in range(1,length):应该是for i in range(1,10):
      count列表只有10个元素,因为你的待排序序列刚好有十个数,所以程序没报错。待排序序列超过十个会下标溢出,少于十个排序错误。

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学四舍(女生)

          @zyh 感谢已更正~

        • avatar hello 来自天朝的朋友 谷歌浏览器 Windows 10 浙江省杭州市 电信 1

          python 第42行 判断条件 d>0 应该改成d>1,你可以试一下,输入列表稍微大一点,就不对了

            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学四舍(女生)

              @hello 感谢指正,已更新。

            • avatar yangdaotamu 来自天朝的朋友 谷歌浏览器 Windows 10 湖北省武汉市 湖北大学 0

              大神,for (int i = 1; i < 10; i++){
              count[i] += count[i – 1];
              } 请问这里对count数组做这样的处理是为什么?

                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

                  @yangdaotamu 有注释了啊,你思考下。举个例子。