重温算法导论（五） 归并排序

归并排序，就是利用递归的思维，解决排序的问题

首先嘉定L R中已经是排好序的数据，利用Merge函数，将他们合并起来

Merge函数伪代码

Merge(A, p, q, r)
	n1 = q - p + 1
	n2 = r - q
	L[n1] = A[p, q]
	R[n2] = A[q+1, r]
	
	j = 0
	i = 0
	for k=p to r-1
		if L[i] <= R[i]
			A[k] = L[i]
			i = i+1
		else 
			A[k] = R[i]
			j = j+1

然后，利用递归，将其分割

MergeSort(A, p, r)
	q = (p+r)/2
	MergeSort(A, p, q)
	MergeSort(A, q+1, r)
	Merge(A, p,q, r)

C++实现代码：

template<class T> void Merge(T A[], int p, int q, int r)
{
	int iN1 = q -p +1, iN2 = r-q;
	T *L = new T[iN1];
	T *R = new T[iN2];

	memcpy(L, &A[p], sizeof(T)*iN1);
	memcpy(R, &A[q+1], sizeof(T)*iN2);
	
	int i=0, j = 0;
	for(int k=p; k<= r; k++)
	{
		if(i>=iN1) {
			A[k] = R[j];
			j += 1;
			continue;
		}
		if(j>=iN2) {
			A[k] = L[i];
			i += 1;
			continue;
		}
		if(L[i] <= R[j])
		{
			A[k] = L[i];
			i = i+1;
		}
		else
		{
			A[k] = R[j];
			j= j+1;
		}
	}
	delete []L;
	delete []R;
}

template<class T> void MergeSort(T A[], int p, int r)
{
	if(p<r){
		int q = (p+r)/2;
		MergeSort(A, p, q);
		MergeSort(A, q+1, r);
		Merge(A, p,q,r);
	}
}

int main(int argc, char* argv[])
{
	
	int iData[5] = {1,2,5,3,4};
	MergeSort(iData, 0, 4);
}