线性排序:

线性排序即排序算法的时间复杂度是线性的,也就是 O(n)。桶排序、计数排序、基数排序这三个算法是不基于比较的排序算法,都不涉及元素之间的比较操作。

基数排序(Radix sort)

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

基数排序实现

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

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

LSD 基数排序动图演示

基数排序.gif

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异案例看大家发的:

  • 基数排序:根据键值的每位数字来分配桶;

  • 计数排序:每个桶只存储单一键值;

  • 桶排序:每个桶存储一定范围的数值;

python代码

def radix(arr):
    digit = 0
    max_digit = 1
    max_value = max(arr)
    #找出列表中最大的位数
    while 10**max_digit < max_value:
        max_digit = max_digit + 1
    while digit < max_digit:
        temp = [[] for i in range(10)]
        for i in arr:
            #求出每一个元素的个、十、百位的值
            t = int((i/10**digit)%10)
            temp[t].append(i)
        coll = []
        for bucket in temp:
            for i in bucket:
                coll.append(i)
        arr = coll
        digit = digit + 1
    return arr

参考:

https://sort.hust.cc/10.radixsort

https://baike.baidu.com/item/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

https://time.geekbang.org/column/article/41913

本文地址: http://chenxm.cc/article/983.html
版权声明: 本文为原创文章,版权归  陈新明  所有,欢迎分享本文,转载请保留出处!
上一篇: python 排序算法——线性排序之计数排序(Counting sort)
下一篇: 十大经典排序算法,
发表评论

还没有留言,还不快点抢沙发?