分治是优化算法中的重要思想。
归并排序的主要技巧,如何处理两个分别已经排好序的数组?
采用额外空间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)