归并排序

浏览数：31 / 时间：2015年06月08日

分治法：将原问题分解为规模比较小的几个子问题，递归的求解子问题的解，然后利用这些子问题的解来建立原问题的解。
归并排序的也完全遵循分治模式：
分解：分解待排序的n个元素的序列为n/2个元素的两个子序列；
解决：使用归并排序递归的排序两个子序列；
合并：合并两个子序列得到答案

借用一张原理图帮助理解，从上往下看是递归分解的过程，当分解为当个元素时候，我们认为是有序的，然后两两合并



归并排序的伪代码如下：
很多时候，伪代码更容易理解：

MERGE(A,p,q,r)
  n1=q-p+1
  n2=r-q
  let L[0...n1] and R[0.....n2]be new arrays
  for i=0 to n1-1
     l[i]=A[p+i]
  for j=0 to n2-1
      R[j]=A[p+q+1]
  L[n1]=无穷大
  R[n2]=无穷大 
  i=0
  j=0
  for k=p to r
  if L[i]<=R[j]
      A[k]=l[i]
      i++
  else A[k]=R[j]
      j++


用C++实现如下：
#include <iostream>
#include<limits>
using namespace std;

void merge(int a[],int p,int q,int r){
	int n1=q-p+1;
	int n2=r-q;
	int* L=new int[n1+1];//左半部分临时数组；
	int* R=new int[n2+1];//右半部分临时数组
	for(int i=0;i<n1;i++){//分别把要排序的数组存放在左右两个临时数组中
		L[i]=a[p+i];
	}
	for(int j=0;j<n2;j++){
		R[j]=a[q+j+1];
	}
	int i=0;
	int j=0;
	L[n1]=INT_MAX;//在临时数组末尾设置一个结束标记
	R[n2]=INT_MAX;
	for(int k=p;k<=r;k++){//分别把左右两个数组合并到原数组中去

		if(L[i]<=R[j]){
			a[k]=L[i];
			i++;
		}else{
			a[k]=R[j];
			j++;
		}
	}

	delete []L;
	delete []R;

}
void merge_sort(int a[],int p,int r){//采用递归的形式实现归并排序
	if(p<r){
		int q=(p+r)/2;
		merge_sort(a,p,q);
		merge_sort(a,q+1,r);
		merge(a,p,q,r);
	}
}
int main(){
	int a[]={1,3,2,5,7,6,8,4};
	merge_sort(a,0,7);
	for(int i=0;i<=7;i++){
		cout<<a[i]<<" ";
	}
	return 1;
} 

归并排序的时间复杂度是nlogn