数据结构和算法-排序算法-归并排序
2023-09-14 09:00:33 时间
################## 归并排序 #######################
""" 归并算法逻辑 拆分 对整个序列进行拆分,左边一部分,右边一部分 然后对每一部分再次进行拆分,一直到拆分到只有一个元素,就到头了, 第1次拆分:54, 26, 93, 17, 77, 31, 44, 55, 第2次拆分:54, 26, 93, 17, 77, 31, 44, 55, 第3次拆分:54, 26, 93, 17, 77, 31, 44, 55, 第4次拆分:54, 26, 93, 17, 77, 31, 44, 55, 合并 然后把拆分到的再次合并,小的在前,大的在后, 第1次合并:26,54, 17,93 31,77, 44, 55, 第2次合并,需要借助两个游标,left,right, 26,54, 17,93 左边游标初始指向26,右边游标初始指向17, 然后左边第一个的和右边的依次比较,如果左边小,数字不动,然后右边的游标往后移动,如果右边小,就把左右的数字交换, 然后比较完左边的第一个,然后就是第二个,知道把数字都从小到大排序, 第3次合并的方式都是一样的,直到所有的都排序完毕, 代码实现, 还是需要使用到递归, """
################## 归并排序 #######################
def merge_sort(alist): n=len(alist) if n <=1 : # 这是如果只有一个元素不往下拆分了,这也是递归结束的条件 return alist mid = n//2 # 这是左边的部分 left = merge_sort(alist[:mid]) # 这是右边的部分, right =merge_sort(alist[mid:]) # 合并: # merge(left,right) # 定义两个游标 left_pointer ,right_pointer=0,0 result=[] while left_pointer<len(left) and right_pointer < len(right): if left[left_pointer]<right[right_pointer]: result.append(left[left_pointer]) left_pointer+=1 else: result.append(right[right_pointer]) right_pointer+=1 result +=left[left_pointer:] result += right[right_pointer:] return result if __name__ == '__main__': alist = [54,26,93,17,77,31,44,55,20] print(alist) sorted_alist = merge_sort(alist) print(sorted_alist)
# 这样排序就结束了,下面讲搜索,
相关文章
- 排序算法的复习和总结[PHP实现]
- Java实现 蓝桥杯 算法训练 排序
- Python排序算法之冒泡排序
- java算法 -- 快速排序
- 数据结构和算法-排序算法-插入排序
- 数据结构和算法14 之归并排序
- 数据结构和算法15 之二叉树排序
- 数据结构和算法17 之拓扑排序
- 为什么说任何基于比较的算法将5个元素排序都需要7次?
- 五种C语言非数值计算的常用经典排序算法
- 各种排序算法的分析与实现
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-快速排序
- 《数据结构与算法之美》——冒泡排序、插入排序、选择排序
- JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序
- Elias-Fano编码算法——倒排索引压缩用,本质上就是桶排序数据结构思路
- python 十大经典排序算法
- 数据结构与算法_28 _ 堆和堆排序:为什么说堆排序没有快速排序快?
- 十大算法 — 选择排序法【C语言代码诠释】