归并排序的实现及其优化（递归法）

归并排序

一、思路(递归)

list = [a,b,c,d]

1、 递归过程

1、数组一分为2，list1 = [a,b] list2 = [c,d]

2、先确立递归项：分别对list1/list2做归并排序，此时可以假设左右子数组已经有序。

3、执行merge子过程，将list1/list2合并并使之有序。

3、在程序首部添加基准条件：当前候选数组长度为1，直接return，停止向下递归。

• 约定

经典的归并排序，目标数组采用闭区间来标记，即[left,right],各标记定义如下：

数组长度 n=7index 0 1 2 3 4 5 6 value 3 2 5 | 7 1 3 6 标记 left mid right注：n = 7left = 0right = n -1mid = right // 2

2、merge子过程

• 思路

1、函数传入整个数组，要merge的子数组区间范围[left,mid]，[mid+1,right]

2、做完整数组的切片 a=list[left,right+1]

3、设定内部指针i遍历子数组1，j遍历子数组2
指针k遍历赋值给完整数组

二、实现

from sort_helper import test_sort,random_arraydef __merge(array, left, mid, right):temp = array[left:right+1]#新数组temp的左中右标记,充当常量n = len(temp)l = 0r = n-1m = l + (r -l) // 2#左数组标记i,右数组标记j,赋值外部循环标记ki = 0j = m + 1#遍历【0，n)即整个数组长度，每次确定一个下标应该赋值的元素并完成赋值操作k = 0 while k < n:#2、定义判断条件，防越界；循环的次数是由n确定的，不存在i,j同时越界的情况if i > m:array[k + left] = temp[j]j += 1elif j > r:array[k + left] = temp[i]i += 1#1、判断两个子数组当前位置的值，并赋值给原数组array的对应位置，此处可能涉及到越界问题,所以循环主体开始之前要判断一下elif temp[i] < temp[j]:array[k + left] = temp[i]i += 1else:array[k + left] = temp[j]j += 1k += 1#错误示范 def __merge1(array, left, mid, right):#错误1，开辟数组空间只针对一部分元素，而非整个数组temp = array[:]#错误2，left应该最后赋值为0，否则后两部相当于减0，无作用#错误3：内部端点就应该重新定义为l、r、mid;一旦否则array[k+left]无效果，因为left已变..left = 0mid = mid - leftright = right - leftn = right - left + 1i = 0j = mid + 1k = 0 while k < n:if i > mid:array[k + left] = temp[j]j += 1elif j > right:array[k + left] = temp[i]i += 1elif temp[i] < temp[j]:array[k + left] = temp[i]i += 1else:array[k + left] = temp[j]j += 1k += 1print(array)#该私有函数需要左右下标 def __merge_sort(array, left, right):#3、添加基准条件,左右区间短点，相差1即可，即子数组长度为1if right -left <= 0:return#1、一分为二mid = left + (right -left) // 2 #2、左右分别归并排序，应该考虑到要添加基准条件了，否则无限递归__merge_sort(array, left, mid)__merge_sort(array, mid+1, right)#4、此时，array两个子数组都已有序，但整个数组却还无序，需要合并__merge(array, left, mid, right)def merge_sort(array):#作为带外暴露的归并排序函数，不需要左右下标__merge_sort(array, 0, len(array)-1)if __name__ == '__main__':array = random_array()test_sort('merge_sort', merge_sort, array)

三、优化

1、提前终止不必要的merge操作

def __merge_sort1(array, left, right):#3、添加基准条件,左右区间短点，相差1即可，即子数组长度为1if right -left <= 0:return#1、一分为二mid = left + (right -left) // 2 #2、左右分别归并排序，应该考虑到要添加基准条件了，否则无限递归__merge_sort1(array, left, mid)__merge_sort1(array, mid+1, right)#4、此时，array两个子数组都已有序，但整个数组却还无序，需要合并if array[mid] > array[mid+1]:__merge(array, left, mid, right)def merge_sort1(array):#作为带外暴露的归并排序函数，不需要左右下标__merge_sort1(array, 0, len(array)-1)

2、使用插入排序优化

def __merge_sort2(array, left, right):if right -left <= 50:insert_sort(array, left, right)#必须要有return，否则无限递归returnmid = left + (right -left) // 2 __merge_sort2(array, left, mid)__merge_sort2(array, mid+1, right)if array[mid] > array[mid+1]:__merge(array, left, mid, right)def merge_sort2(array):__merge_sort2(array, 0, len(array)-1)

3、测试用例

if __name__ == '__main__':array = random_array()array1 = array[:]array2 = array[:]array3 = nearly_ordered_array(10000, 1)array4 = array3[:]array5 = array3[:]test_sort('merge_sort random_array', merge_sort, array)test_sort('merge_sort1 random_array', merge_sort1, array1)test_sort('merge_sort2 random_array', merge_sort2, array2)test_sort('merge_sort nearly_ordered_array', merge_sort, array3)test_sort('merge_sort1 nearly_ordered_array', merge_sort1, array4)test_sort('merge_sort2 nearly_ordered_array', merge_sort2, array5)

优化效果在有序性较强的情况下比较明显

总结

以上是生活随笔为你收集整理的归并排序的实现及其优化（递归法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。