常见排序算法-基数排序、计数排序
2021-02-12 07:17
标签：ceil mil 排序 连接 数据 col 位置 遍历 年龄 基数排序（桶排序）： 设置若干个箱子，将关键字为k的记录放入第k个箱子中，然后按序号将非空的连接。而数字是有范围的，若待排元素均由0-9这十个数字组成，则只需设置十个箱子，相继按个、十、百...进行排序 平均，最坏时间复杂度 O(k*(n+m)) k是关键字的个数，如个位、十位分别就是关键字；n是元素的个数，m是桶的个数。最好时间复杂度 O(n+m)，一次分配就搞定！ 计数排序 基本思想：用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出，即可得到有序序列。 适用范围：数据量大范围小 小结：基数和计数排序都不是基于比较交换的算法，属于线性时间复杂度，但需要一定的辅助空间。对排序的元素也有要求，适合量大数据范围有限的数据，如公司员工的年龄。 常见排序算法-基数排序、计数排序 标签：ceil mil 排序 连接 数据 col 位置 遍历 年龄 原文地址：https://www.cnblogs.com/wanrongshu/p/12731240.htmlimport math
def radix_sort(lists, radix=10):
k = int(math.ceil(math.log(max(lists), radix))) #找到最高位的数字。这的确是个好办法
bucket = [[] for i in range(radix)] #bucket是一个有十个空列表元素的列表
for i in range(k):
for j in lists:
bucket[j//(10**i)%10].append(j) #从高到低依次找出该数每一位的数值
del lists[:]
for z in bucket:
if len(z):
lists += z #等效于lists.append(z[0])
del z[:]
return lists
def countSort(arr):
# 1.计算数列的最大值与最小值，从而得到计数数组的长度
length=max(arr)-min(arr)+1
busket=[0 for i in range(length)]
sortarr=[0 for i in range(len(arr))]
#2.busket统计数组用来统计数组个数
for i in arr:
busket[i-min(arr)]+=1
#3.统计数组变形，后面元素等于前面元素之和
sum1=0
for j in range(length):
sum1+=busket[j]
busket[j]=sum1
#4.倒序遍历原始数组，从统计数组找到正确位置，输出结果数组
for k in arr[::-1]:
sortarr[busket[k-min(arr)]-1]=k
busket[k-min(arr)]-=1
return sortarr
if __name__==‘__main__‘:
a=[4,3,2,5,1,3]
sort_a=countSort(a)
print(sort_a)