想要看更加舒服的排版、更加准时的推送 关注公众号“不太灵光的程序员” 每日八点有干货推送 公众号“不太灵光的程序员” 同时发布《基于桶子法实现的两种排序算法》 阅读原文
在前面的几天我们学习了基于比较的排序算法，今天来了解下基于桶排序的两个排序算法，桶排序不是一种具体的实现是一种排序思想。
桶排序是将数组中分到有限的桶里，通俗的讲就是我们已经有一些有限个数的、排好序的桶子，将相应属性的数据放入对应的桶中，再按桶的顺序取出，新的数组就是有序的了。
桶排序的局限性？？当我们选择的数据范围比较小时，例如人的身高、考试分数、绩效评级，数据基本上处在一个小的数值范围内，但当我们对员工薪资进行排序时，数据范围很大从几千到几万的都有，需要的桶的数量非常多，且当这些数据分布不均匀时，会造成很大的空间浪费。
计数排序基于桶排序思想，但是每个桶只存储单一键值。比如过我们要把公司员工安装身高进行排序，分析一个成年人的身高是在1m3m之间，对应的厘米数是100cm300cm，我们需要创建100~300号的桶，然后我们把所有员工，按照他们的身高放入对应的桶中；然后从100号桶开始往外倒数据，员工被导出的顺序就是员工升高的排序了。
- 时间复杂度O(N)
- 空间复杂度O(M) M是选择的桶的数量
- 稳定排序
def CountSort(nums):
# 以身高的最大最小值来确定桶的范围
min_num = min(nums)
max_num = max(nums)
# 申请学生升高范围的所有桶
count = {i: 0 for i in range(min_num, max_num+1)}
for i in nums:
count[i] += 1
return [key for key, value in count.items() for j in range(value)]
if __name__ == "__main__":
# 对一组学生身高进行排序
print(CountSort([175, 187, 183, 182, 163, 190, 159, 167]))
基于桶排序思想，根据键值的每位数字来分配桶；首先我们假设数据组的所有元素都是十进制的，然后就准备0~9号桶；把每个数据的个位是几就把它放入几号桶，再从0号桶依次倒出数据，把每个数据的十位是几就把它放入几号桶，再从0号桶依次倒出数据；直到所有数的每位都重复到以上过程，0号桶依次倒出数据就是有序的了。
- 时间复杂度O(N)
- 空间复杂度O(M) M是选择的桶的数量
- 稳定排序
def RadixSort(nums):
# 首先要申请0-9的十个桶
def pour_out(arr):
return [i for value in arr.values() for i in value]
# 当前排序的位数 0个位，1十位，2百位等...
intm = 0
while 1:
count = {i: [] for i in range(10)}
for i in nums:
# 当前排序位 的数值
initn = i // 10 ** intm % 10
count[initn].append(i)
nums = pour_out(count)
intm += 1
if len(count[0]) == len(nums):
break
return count[0]
if __name__ == "__main__":
# 对一组学生身高进行排序
print(RadixSort([175, 187, 183, 182, 163, 190, 159, 167]))
- Redis实现消息队列的6种方案
- 让运维更简单的7种定时任务实现方式
- 细品28岁程序员退休创业背后的可怕故事
- 工作中都有哪些让你心累的时刻
