[经典算法]合并排序 Merge-Sort
2021/12/19 1:21:07
本文主要是介绍[经典算法]合并排序 Merge-Sort,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
合并排序(归并排序)采用分治法(Divide and Conquer),先递归分解数组,将序列每次折半划分,再合并数组,将划分后的序列两两合并后排序。
基本方法:
1、将序列从中间位置分成左右两个序列
2、再将这两个子序列按照第1步继续二分下去,直到所有左右子序列的长度都为1
3、将合并排序的左右序列合并成一个有序序列
def Merge(left, right): # 将左右数组元素排序并合并成一个数组 temp = [] i = j = 0 while i < len(left) and j < len(right): # 将两边数组的元素进行比较,选择较小的填进临时数组,直到将一边填完 if left[i] < right[j]: temp.append(left[i]) i += 1 else: temp.append(right[j]) j += 1 if i == len(left): # 左侧数组已比对完,把右侧数组剩余数据全部填充到数组 for k in right[j:]: temp.append(k) else: # 右侧数组已比对完,把左侧数组剩余数据全部填充到数组 for h in left[i:]: temp.append(h) print('Merge temp:',temp) return temp def MergeSort(ls): if len(ls) < 2: # 单个元素列表无需排序 return ls middle = len(ls)//2 left = MergeSort(ls[:middle]) # 左边列表元素递归分解并排序 print('MergeSort left:',left) right = MergeSort(ls[middle:]) # 右边列表元素递归分解并排序 print('MergeSort right:',right) return Merge(left, right) # 左右两边分解的列表做最后合并 a = [8,4,5,7,1,3,6,2] print('合并排序结果为:',MergeSort(a))
====================== RESTART: test.py ====================== MergeSort left: [8] MergeSort right: [4] Merge temp: [4, 8] MergeSort left: [4, 8] MergeSort left: [5] MergeSort right: [7] Merge temp: [5, 7] MergeSort right: [5, 7] Merge temp: [4, 5, 7, 8] MergeSort left: [4, 5, 7, 8] MergeSort left: [1] MergeSort right: [3] Merge temp: [1, 3] MergeSort left: [1, 3] MergeSort left: [6] MergeSort right: [2] Merge temp: [2, 6] MergeSort right: [2, 6] Merge temp: [1, 2, 3, 6] MergeSort right: [1, 2, 3, 6] Merge temp: [1, 2, 3, 4, 5, 6, 7, 8] 合并排序结果为: [1, 2, 3, 4, 5, 6, 7, 8]
这篇关于[经典算法]合并排序 Merge-Sort的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南