【Radix Sort】基数排序算法_时间复杂O(n)
本帖最后由 Lthero 于 2021-5-12 19:50 编辑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之间 用时一秒不到。（另外，桶排序针对负数要拿出来单独排序）
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 =
RadixSort(data)
print(data)
下图是几个常用算法对一万个随机数（0~十万）同时进行排序的时间比较
最快的是RadixSort 也就是基数排序
你这个并不如timsort吧，而且timsort空间复杂度也更低 帮我看一下悬赏区的一个帖子，谢谢。可以吗 tanrenye 发表于 2021-5-10 20:40
你这个并不如timsort吧，而且timsort空间复杂度也更低
这个算法也是几个基础算法之一吧，TimSort是其它基础算法plus版本。不作比较
页:
[1]