Python排序算法(六) | 您所在的位置:网站首页 › python的有序序列 › Python排序算法(六) |
有趣的事,Python永远不会缺席! 如需转发,请注明出处:小婷儿的python
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序适用于子序列有序的数据排序。 1、原理归并排序是分治法的典型应用。分治法(Divide-and-Conquer):将原问题划分成 n 个规模较小而结构与原问题相似的子问题;递归地解决这些问题,然后再合并其结果,就得到原问题的解。从上图看分解后的数列很像一个二叉树。 归并排序采用分而治之的原理: 将一个序列从中间位置分成两个序列; 在将这两个子序列按照第一步继续二分下去; 直到所有子序列的长度都为1,也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。原理如上图,图片来源于https://blog.csdn.net/su_bao/article/details/81053871 2、举例 对以下数组进行归并排序: [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]2. 首先,进行数组分组,即 [11, 99, 33 , 69, 77, 88, 55], [ 11, 33, 36,39, 66, 44, 22] [11, 99, 33] , [69, 77, 88, 55], [ 11, 33, 36], [39, 66, 44, 22] [11], [99, 33] , [69, 77], [88, 55],[ 11], [33, 36],[39, 66], [44, 22]直到所有子序列的长度都为1,也就是不可以再二分截止。 [11], [99], [33] , [69], [77], [88], [55],[ 11], [33], [36],[39], [66], [44], [22]3. 这时候再两两合并成一个有序序列即可。 [11],[33,99],[69,77],[55,88],[11],[33,36],[39,66],[22,44] [11,33,99],[55,69,77,88],[11,33,36],[22,39,44,66] [11,33,55,69,77,88,99],[11,22,33,36,39,44,66]4、最终排序 1 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99] 二、代码代码用jupyternotebook实现 1 def merge_sort(arr): 2 """归并排序""" 3 if len(arr) == 1: 4 return arr 5 # 使用二分法将数列分两个 6 mid = len(arr) // 2 7 left = arr[:mid] 8 right = arr[mid:] 9 # 使用递归运算 10 return marge(merge_sort(left), merge_sort(right)) 11 12 13 def marge(left, right): 14 """排序合并两个数列""" 15 result = [] 16 # 两个数列都有值 17 while len(left) > 0 and len(right) > 0: 18 # 左右两个数列第一个最小放前面 19 if left[0] |
CopyRight 2018-2019 实验室设备网 版权所有 |