计数排序、桶排序
计数排序适用于一定范围的整数排序。在取值范围不是很大的情况下,它的性能在某些情况甚至快过那些O(nlogn)的排序,例如快速排序、归并排序。
计数排序原理:
找到给定序列的最小值与最大值
创建一个长度为最大值-最小值+1的数组,初始化都为0
然后遍历原序列,并为数组中索引为当前值-最小值的值+1
此时数组中已经记录好每个值的数量,自然也就是有序的了
def count_sort(s): """计数排序""" # 找到最大最小值 min_num = min(s) max_num = max(s) # 计数列表 count_list = [0]*(max_num-min_num+1) # 计数 for i in s: count_list[i-min_num] += 1 s.clear() # 填回 for ind,i in enumerate(count_list): while i != 0: s.append(ind+min_num) i -= 1 if __name__ == '__main__': a = [3,6,8,4,2,6,7,3] count_sort(a) print(a)
桶排序:适用于非整数
桶排序相当于把计数数组划分为按顺序的几个部分
每一部分叫做一个桶,它来存放处于该范围内的数
然后再对每个桶内部进行排序,可以使用其他排序方法如快速排序
最后整个桶数组就是排列好的数据,再将其返回给原序列
def bucket_sort(s): """桶排序""" min_num = min(s) max_num = max(s) # 桶的大小 bucket_range = (max_num-min_num) / len(s) # 桶数组 count_list = [ [] for i in range(len(s) + 1)] # 向桶数组填数 for i in s: count_list[int((i-min_num)//bucket_range)].append(i) s.clear() # 回填,这里桶内部排序直接调用了sorted for i in count_list: for j in sorted(i): s.append(j) if __name__ == '__main__': a = [3.2,6,8,4,2,6,7,3] bucket_sort(a) print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]