线性排序算法-归并排序（3）
线性排序算法-归并排序（3）
birdskyws
发布于 2018-09-12 15:48:17
发布于 2018-09-12 15:48:17
分治是优化算法中的重要思想。
归并排序的主要技巧，如何处理两个分别已经排好序的数组？
采用额外空间O(n)，交替遍历两个数组，时间复杂度为O(n)
将原数组不断向下拆分
举例说明，16个整形数组向下拆分 16-->(8,8)-->(4,4)-->(2,2)(2,2)(2,2)(2,2)->(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)
(1,1)采用归并，生成排好序的（2） (2,2)采用归并，生成拍好序的（4) (4,4)-->(8) (8,8)-->16
def __Merge(self,a,l,mid,r):
#排序对象a[l,mid) [mid,r)
b=[a[i] for i in range(l,r)]
i = 0
j = mid-l
for k in range(l,r):
if i == mid-l:
a[k] = b[j]
j = j+1
elif j == r-l :
a[k] = b[i]
i = i+1
elif b[i] > b[j]:
a[k] = b[j]
j = j+1
else:
a[k] = b[i]
i = i+1循环调用
def MergeSort2(self,a):
sz = 1
total = len(a)
while(sz< total):
i = 0
while(i<total-sz-1):
self.__Merge(a,i,i+sz,min(i+sz+sz,total))
i = i+sz+sz
sz = sz+sz递归调用
def __MergeSort(self,a,l,r):
#排序对象 a[l,r)
if (l+1) >= r:
return
"""
## 在小数组情况下，用插入排序，实验优化效果不好
if (l+6)<=r:
self.InsertionSortPart(a,l,r)
return
"""
mid = l+(r-l)//2
self.__MergeSort(a,l,mid)
self.__MergeSort(a,mid,r)
self.__Merge(a,l,mid,r)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.07.13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录