算法:递归-归并排序

2018-09-12

归并排序

归并算法的中心是归并两个已经有序的数组

"归并-排序"

"归并-合并数组"

归并排序的思想是把一个数组分成两半，排序每一半，然后把两半归并成有序的数组

"归并-归并为大数组"

MergeSort.py结构

class MergeSort:
    def __init__(self,max):
        self.theArray=[0]*max		#初始化数组
        self.elements=0				#初始化数值个数
	#插入操作
    def _insert(self,var):
        self.theArray[self.elements]=var
        self.elements+=1
	#打印数组
    def _display(self):
        for i in range(0,self.elements):
            print(str(self.theArray[i]))

归并方法入口

#递归执行合并
def _reMergeSort(self,workSpace,lowerBound,upperBound):
	#只有一个数组的值时停止递归
	if lowerBound==upperBound:
		return
	else:
		#获取中间索引位置
		mid=int((lowerBound+upperBound)/2)
		#递归两边的数组
		_reMergeSort(workSpace,lowerBound,mid)
		_reMergeSort(workSpace,mid+1,upperBound)
		#合并两个数组操作
		_merge(workSpace,lowerBound,mid+1,upperBound)
#归并入口方法
def _mergeSort(self):
	workSpace=[0]*self.elements
	_reMergeSort(workSpace,0,self.elements-1)

合并A数组和B数组到C数组的方法

def _merge(self,workSpace,lowPtr,highPtr,upperBound):
	#0
	j=0
	lowerBound=lowPtr
	mid=highPtr-1
	n=upperBound-lowerBound+1
	#1
	while lowPtr <= mid and highPtr <= upperBound:
		if self.theArray[lowPtr] < self.theArray[highPtr]:
			workSpace[j]=self.theArray[lowPtr]
			j+=1
			lowPtr+=1
		else:
			workSpace[j]=self.theArray[highPtr]
			j+=1
			highPtr+=1
	#2
	while lowPtr <= mid:
		workSpace[j]=self.theArray[lowPtr]
		j+=1
		lowPtr+=1
	while highPtr <= upperBound:
		workSpace[j]=self.theArray[highPtr]
		j+=1
		highPtr+=1
	#3
	for i in range(0,n):
		self.theArray[lowerBound+i]=workSpace[i]

步骤	比较(如果两个数组有值的话)	复制
1	23 < 7 ?	7 B->C
2	23 < 14 ?	14 B->C
3	23 < 39 ?	23 A->C
4	39 < 47 ?	39 B->C
5	55 < 47 ?	47 A->C
6	55 < 81 ?	55 B->C
7	62 < 81 ?	62 B->C
8	74 < 81 ?	74 B->C
9		81 A->C
10		95 A->C