Python在线学习文章目录 [ 隐藏 ]
简要说明
桶排序是一种效率很高的排序算法，它的时间复杂度为O(n)，但桶排序有一定的限制，只有当待排序序列的元素为0到某一确定取值范围的整数时才适用，典型的例子比如成绩的排序等。
桶排序算法思想
设待排序序列的元素取值范围为0到m，则我们新建一个大小为m+1的临时数组并把初始值都设为0，遍历待排序序列，把待排序序列中元素的值作为临时数组的下标，找出临时数组中对应该下标的元素使之+1；然后遍历临时数组，把临时数组中元素大于0的下标作为值按次序依次填入待排序数组，元素的值作为重复填入该下标的次数，遍历完成则排序结束序列有序。
Python算法实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#FileName:lean001.py #author:www.py40.com #Python桶排序 def bucket(lst): buckets = [0] * ((max(lst) - min(lst))+1) for i in range(len(lst)): buckets[lst[i]-min(lst)] += 1 res=[] for i in range(len(buckets)): if buckets[i] != 0: res += [i+min(lst)]*buckets[i] return res a =[12,4,2,4,56,1,4,0] b = bucket(a) print(b) |
运行结果
|
1 2 |
E:\js\FirstServer>python E:\python\learn\lean001.py [0, 1, 2, 4, 4, 4, 12, 56] |
未经允许不得转载：Python在线学习 » Python-桶排序