【Radix Sort】基数排序算法_时间复杂O(n)

Lthero

Radix Sort
目前最快的排序方法（某些场合下相对于其它稳定算法），时间复杂度O (nlog(r)m)，其中r为所采取的基数，而m为堆数（一般为10堆），基数取决于数字位数。

假设原来有一串数值如下所示：73, 22, 93, 43, 55, 14, 28, 65, 39, 81

• 第一步   首先根据个位数的数值，在遍历数值时将它们分配至编号0到9的桶子中：
  

0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

• 第二步     将这些桶子中的数值重新串接起来，成为以下的数列：
  

81, 22, 73, 93, 43, 14, 55, 65, 28, 39     接着再进行一次分配，这次是根据十位数来分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

• 第三步    将这些桶子中的数值重新串接起来，成为以下的数列：
  

14, 22, 28, 39, 43, 55, 65, 73, 81, 93


这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。


楼主测试了十万数据，范围在0~100000之间 用时一秒不到。（另外，桶排序针对负数要拿出来单独排序）

[Python] 纯文本查看 复制代码

class RadixSort():
    def __init__(self, arrx):
        self.start(arrx)

    def start(self, arr):
        # buckets有十个桶
        buckets = []
        for i in range(10):
            buckets.append([])
        # 基数设置为6位
        for i in range(6):
            for j in arr:
                buckets[(j // int(pow(10, i))) % 10].append(j)
            #清空 arr
            arr.clear()
            #重新排序 并放入arr中
            for k in buckets:
                for z in k:
                    arr.append(z)
            #清空所有桶内容
            for u in buckets:
                u.clear()

if __name__ == '__main__':
    x = input().split(' ')
    data = [int(n) for n in x]
    RadixSort(data)
    print(data)

下图是几个常用算法对一万个随机数（0~十万）同时进行排序的时间比较
最快的是RadixSort 也就是基数排序

tanrenye

你这个并不如timsort吧，而且timsort空间复杂度也更低

不是童画

帮我看一下悬赏区的一个帖子，谢谢。可以吗

Lthero

tanrenye 发表于 2021-5-10 20:40
你这个并不如timsort吧，而且timsort空间复杂度也更低

这个算法也是几个基础算法之一吧，TimSort是其它基础算法plus版本。不作比较