Python培训
400-996-5531
Python培训 > Python教程知识 > 正文
Python归并排序简介
- 发布：Python培训
- 来源： 叶藏手札
- 时间：2019-12-09 11:42
一、Pythond归并排序
归并排序(Merge Sort)也称为合并排序，是1945年由约翰·冯·诺伊曼首次提出的一种创建在归并操作上的有效的排序算法，效率为O(nlogn)。该算法是遵循分而治之(Divide and Conquer)的方法，且各层分治递归可以同时进行。算法的基本思想是：将待排序数组分成两个子数组，使用归并排序递归地对两个子数组进行排序，将两个有序的子数组合并成一个大的有序的数组，通过递归，层层合并，即为归并。归并排序的执行过程如下图所示：
算法的基本过程包括两个过程：拆分与合并。
归并排序拆分阶段：
将待排序数组分成长度大约相等的两个子数组，每个子数组继续分成长度大约相等的两个子数组，递归实现，直到子数组只有一个元素为止(只有一个元素的数组是有序数组)。
归并排序合并阶段：
设定两个指针，最初位置分别为两个已经排序子数组的起始位置。
比较两个指针所指向的元素，选择相对小的元素放入到合并数组，并移动指针到下一位置。
重复上述步骤直到某一指针到达子数组尾部。
将另一子数组剩下的所有元素直接复制到合并数组尾部。
归并算法的整个过程如下图所示：
二、python归并排序算法代码实现：
# 归并排序 2def merge_sort(data_list): 3 length = len(data_list) 4 if length == 0 or length == 1: 5 return data_list 6 # 拆分为2个子数组 7 middle = length//2 8 left = data_list[:middle] 9 right = data_list[middle:] 10 # 递归使用归并排序子数组 11 new_left = merge_sort(left) 12 new_right = merge_sort(right) 13 # 合并2个已排序子数组 14 sort_list = merge(new_left,new_right) 15 return sort_list 16 17# 合并函数 18def merge(left,right): 19 sort_list = [] 20 while len(left) != 0 and len(right) != 0: 21 if left[0] < right[0]: 22 sort_list.append(left[0]) 23 left.remove(left[0]) 24 else: 25 sort_list.append(right[0]) 26 right.remove(right[0]) 27 28 if len(left) == 0: 29 sort_list += right 30 else: 31 sort_list += left 32 33 return sort_list
测试结果：
免责声明：内容和图片源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
预约申请免费试听课
填写下面表单即可预约申请免费试听！ 怕学不会？助教全程陪读，随时解惑！担心就业？一地学习，可全国推荐就业！
上一篇：Python正则表达式及应用
下一篇：Python面向对象编程基础知识
Copyright © Tedu.cn All Rights Reserved 京ICP备08000853号-56 
京公网安备 11010802029508号 达内时代科技集团有限公司 版权所有
选择城市和中心
北京
黑龙江省
吉林省
内蒙古
河北省
陕西省
江苏省
湖北省
四川省
重庆
湖南省
江西省
贵州省
云南省
广西省
海南省
台湾