算法学习-02(希尔排序,计数排序,桶排序,基数排序)
希尔排序
# 希尔排序 # 希尔排序是对插入排序的升级改造 # 它的大致流程是 # 1、将长度为n的序列 分为d = n//2组 # 2、使每一组变的有序 # 3、将序列分为 d1 = d // 2 组 # 4、将每一组变的有序 # 5、直到最后 d 小于等于 0 def inster_sort_gap(li,gap): for i in range(gap,len(li)): tmp = li[i] j = i - gap while j >= 0 and tmp > li[j]: li[j+gap] = li[j] j -= gap li[j+gap] = tmp def shell_sort(li): n = len(li) gap = n // 2 while gap > 0: inster_sort_gap(li,gap) gap //= 2
计数排序
#计数排序 对列表进行排序,已知列表中的数范围都在0到100之间。 设计时间复杂度为O(n)的算法 #eg: 1 3 2 4 1 2 3 1 3 5 # 分配0-5六个桶,遇到一个数,在相应的桶上加一 0 1 1+1+1 2 1+1 3 1+1+1 4 1 5 1 复杂度 O(n) 占用空间 O(n) # 计数排序 def count_sort(li, max_count): count = [0 for _ in range(max_count+1)] for i in li: count[i] += 1 li.clear() for ind, val in enumerate(li): for i in range(val):
桶排序
# 如果计数排序中,如果元素的范围比较大(比如在1到1亿之间),如何改造算法 # 桶排序(Bucket Sort): 把元素放在不同的桶里,对每个桶里面的元素保持有序 def bucket_sort(li,n=100,max_num=10000): """ :param li: 需要排序的列表 :param n: 分多少个桶 :param max_num: 最大数 :return: """ buckets = [[] for _ in range(n)] for var in li: i = min(var // (max_num // n), n-1) # i 表示var放到几号桶里面 buckets[i].append(var) # 把var 放到对应的桶里 # 保持桶内的顺序 for j in range(len(buckets[i])-1, 0, -1): if buckets[i][j] < buckets[i][j-1]: buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j] else: break sorted_li = [] for buc in buckets: sorted_li.extend(buc) return sorted_li# 范围特别大,用的不是太多 # 桶排序的效率 # 取决于数据的分布,也就是需要对不同数据排序时,采取不同的分桶策略 # 平均分布--- # 不平均,90%的数在某一个桶里 # # 平均情况时间复杂度:O(n+k) # 最坏情况时间复杂度:O(n**2k) # 空间复杂度:O(nk) # 还可以优化,比如内部排序过程
基数排序
# 先行知识点: 基于多关键字排序 eg:对员工表进行薪资排序,薪资相同的按照年龄排序 先按照年龄进行排序,再按照薪资进行稳定的排序 #对 32,13,19,52,54,94,3,17 的排序,也可以看作是多关键字排序 #先对个位数进行桶排序,再对十位数进行桶排序 时间复杂度,O(kn) 空间复杂度,O(k+n) k表示数字位数 快排 nlogn # logn=log(2,n) 计数排序 kn # k=log(10,n) 当长度是固定的,数值范围越来越大,达到一定程度100000000...,基数排序的性能会变差 缺陷在于,需要占用空间 字符串的排序 # abcd # ab00 #在面加0 数字排序,是在前面001 ,012,123 小数? # 基数排序 def radix_sort(li): max_num = max(li) # 取出最大值,99->2, 888->3, 10000->5 it = 0 # 7--> it=0 77-->it=2, it等于0的时候,取个位数,it=1的时候,取的是十位数 while 10 ** it <= max_num: # 在每次里面进行分桶 buckets = [[] for _ in range(10)] # 0-9 共计 10个 桶 for var in li: # 分到几号桶,看的是哪一位的数 # 怎么取出对应位置上的数字 # 987 it=0 取第一位7 987%10=7 # it=1 取第二位8 987//10=98 98%10=8 # it=2 取第三位9 987//100=9 9%10=9 # 所以,公式: (987//10**it) % 10 digit = (var // 10 ** it) % 10 buckets[digit].append(var) # 已经做好了分桶 # 把数重新写进li li.clear() for buc in buckets: li.extend(buc) it += 1
相关推荐
Skyline 2020-06-16
dushine00 2020-04-19
代码之神 2019-11-04
郭岚 2019-06-28
WindChaser 2019-06-26
郭岚 2017-12-04
Python探路者 2014-04-25
BitTigerio 2018-05-07
算法改变人生 2020-07-28
路漫 2020-06-16
roseying 2019-12-02
natloc 2015-05-01
StrongHYQ 2015-04-30
azhedashuaibi 2019-06-28
郭岚 2019-06-27
YUAN 2019-06-21
standfly 2018-08-14
清雨轩 2017-11-29