快排：最优复杂度 O（n*logn） 最坏时间复杂度O（n^2）平均时间复杂度n^(1.3)
归并排序：最优/平均/最坏 时间复杂度均O（nlogn）,但是内存占用为list大小的两倍，算法稳定
############################## p5 排序 ###################################def bubble_sort(alist):"""顺序表实现bubble"""n=len(alist)for j in range(0,n-1):#遍历次数，没遍历一次 遍历长度-1 遍历j次 -jcount = 0for i in range(0,n-1-j):#一次循环找到最大值，并且移动到最后位置 主体if alist[i]>alist[i+1]:alist[i],alist[i+1]=alist[i+1],alist[i]count+=1if 0 == count:return #####count 优化 不交换数字 不增加计数def choose_sort(alist):"""选择排序：找到最小的数字，放到最前面"""min = 0n = len(alist)for j in range(0,n-2):min = jfor i in range(j+1,n):if alist[min]>alist[i]:min = ialist[j],alist[min] = alist[min],alist[j]def insert_sort(alist):"""插入排序，从右边去除一个数 ，房子啊最左边 在最左边排序，不断地从右边获取后面的数字"""n = len(alist)#从右边的无序序列中取出多少个元素执行这样的过程for j in range(1,n):#内层循环的起始值i = j#执行从右边的无序序列中去除第一个元素，即i位置的元素，插入到正确的位置while(i>0): #for i in range(i,0,-1)if alist[i] < alist[i-1]:alist[i], alist[i-1] = alist[i-1], alist[i]i -= 1else:breakdef shell_sort(alist):""""希尔排序 不稳定 O（n^2） 分而治之 p5.7 -p5.8"""n = len(alist)gap = n//2 # python取整 双斜线while gap >= 1:#该循环将gap 变换到1 之前#插入算法与普通插入算法一样for j in range(gap,n):#j = [gap,gap+1,gap+2,.....,n ]i = jwhile(i>0): ###除了间隔 gap 和插入算法一摸一样if alist[i] < alist[i-gap]:#alist[i],alist[i-gap] = alist[i-gap],alist[i]i -= gapelse:breakgap //= 2def quick_sort(alist, first, last):""""#快速排序 递归嵌套 最优时间复杂度nlgn"""if first >= last:returnlow = firsthigh = lastmid_value = alist[first]while low < high:while low < high and alist[high] >= mid_value: #high左移high -= 1alist[low] = alist[high]while low < high and alist[low] < mid_value: # low右移low += 1alist[high] = alist[low]# 从循环退出时 low = highalist[low] = mid_valuequick_sort(alist,first,low-1) #对low左边的列表执行快排quick_sort(alist,low+1,last) #对low右边的列表执行快排def merge_sort(alist):"""有额外开销 需要两倍的存储空间"""n = len(alist)if n<= 1:return alistmid = n//2###拆分的过程部分代码left_li = merge_sort(alist[:mid])right_li = merge_sort(alist[mid:])## 合并的部分代码 merge(left,right)left_pointer, right_pointer = 0, 0result = []## 调整内部顺序while left_pointer < len(left_li) and right_pointer < len(right_li):if left_li[left_pointer] <= right_li[right_pointer]:result.append(left_li[left_pointer])left_pointer += 1else:result.append(right_li[right_pointer])right_pointer += 1#####合并切片result += left_li[left_pointer:]result += right_li[right_pointer:]return resultif __name__ == "__main__":li = [54, 26, 2, 4, 5, 100, 102]print(li)# quick_sort(li, 0, len(li)-1)result_li = merge_sort(li)print(result_li)"""merge_sort=[54, 26, 2, 4, 5, 100, 102]left_li = [54, 26, 2, 4] right_li=left_li = [54, 26] right_li = [2, 4] left_li = [54] right_li = [26]左边一半完成分割，开始进行排序操作执行 if n<= 1: list长度为1 ，返回自身 left_li = [54] right_li = merge_sort(alist[mid:]) = merge_sort(【54，26】[mid=1:])=[26]right_li = [26][54,26] 进行主循环 返回[2,4] 开始 执行 ## 调整内部顺序"""
如果觉得《python数据结构与算法：排序算法（面试经验总结）》对你有帮助，请点赞、收藏，并留下你的观点哦！
