学步园

一、归并排序

基本思路：利用分治法的思想，将数组分成两个数组，如果两个子数组无序，那么就继续分解，直至每组只剩一个元素，最后依次进行合并。难点在于如何将两个有序数组合并为一个。

伪代码：

MERGESORT(A,p,r)
   if p<r
      q=(p+r)/2
      MERGESORT(a,p,q)
      MERGESORT(a,q+1,r)
      MERGE(A,p,q,r)

MERGE(A,p,q,r)
   len1=q-p+1
   len2=r-q
   let L[0...len1-1] and R[0...len2-1] be new arrays
   for i=0 to len1-1
      L[i]=A[p+i]
   for j=- to len2-1
      R[j]=A[q+j]
   m=0
   n=0
   k=0
   while m<len1 and n<len2
       if L[m]<R[n]
          A[p+k]=L[m]
          m++
          k++
       else
          A[p+k]=R[n]
          n++
          k++
   while m<len1
       A[p+k]=L[m]
       m++
       k++
   while n<len2
       A[p+k]=R[n]
       n++
       k++

java代码：

public static void mergeSort(int 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);
	}
	
}
public static void merge(int A[],int p,int q,int r){
	int len1 = q-p+1;
	int len2 = r-q;
	int L[] = new int[len1];
	int R[] = new int[len2];
	for(int i = 0; i < len1; i++)
		L[i] = A[p+i];
	for(int j = 0; j < len2; j++)
		R[j] = A[q+1+j];
	int n = 0;
	int m = 0;
	int k = 0;
	while(n < len1 && m < len2){
		if(L[n] < R[m]){
			A[p+k] = L[n];
			n++;
		}else{
			A[p+k] = R[m];
			m++;
		}
		k++;
	}
	while(n < len1){
		A[p+k] = L[n];
		n++;
		k++;
	}
	while(m < len2){
		A[p+k] = R[m];
		m++;
		k++;
	}
}