排序算法集合（二）歸并排序精講

     合并排序是一種分治算法，所謂分治法，即分而治之，将大問題分解為小問題，處理小問題得到相應的結果。

     思路分析：

     從資料中點将一排資料分為前後兩組，分别對兩組遞歸進行排序，然後将兩個有序的子序列合并為一個有序的數組。假設A={2,4,9,8,3,5,7,6}進行排序。先講A劃分為前半部分A1={2,4,9,8}和後半部分A2={3,5,7,6},前一部分A1遞歸排序被劃分為A11={2,4}和後半部分A12={9,8};對A11和A12繼續進行遞歸排序，A11有序遞歸結束後A11={2,4} , A12遞歸排序後 A12 ={8,9}之後合并A11，A12得到A1={2,4,8,9};同理處理A2之後得到A2={3,5,6,7}，最後合并A1，A2得到A={2,3,4,5,6,7,8,9}；

#include<iostream>
#define MAX 100
using namespace std;
int B[MAX];
int Merge(int a[], int n) 
{
	int mid,s1,s2,i,b;
	mid = n/2;//将數組劃分為兩部分，A1=[0-(mid-1)];A2=[mid-n];此時A1，A2同時有序 
	s1 = 0;//A1的頭部位置 
	s2 = mid;//A2的頭部位置
	b = 0;
	while(s1 < mid && s2 < n)//将s1和s1中較小的元素存入B 
	{
		if(a[s1]<=a[s2])
			B[b++]=a[s1++];
		else
			B[b++]=a[s2++];
	} 
	if(s1 < mid)//前一個子數組的剩餘元素轉移到B中 
	{
		for(i = s1; i < mid; i++)
			B[b++] = a[i]; 
	} 
	else// if(s2 < n)//後一個子數組的剩餘元素轉移到B中 
	{
		for(i = s2; i < n; i++)
			B[b++] = a[i];
	}
	for(i = 0; i < n; i++)
		a[i] = B[i];//将B中已經排好序的元素轉移到A中 
	return 1;
}
int MergeSort(int a[], int n)
{
	if(n<=1)
		return 1;//遞歸終止條件，将傳進MergeSort函數的個數小于等于一個元素時，遞歸終止。
	else
	{
		MergeSort(a,n/2);//将該數組前半部分遞歸
		MergeSort(a+n/2,n-n/2);//将該數組後半部分遞歸
		//第一次遞歸到該行時，該數字隻有兩個元素，前半部分和後半部分各有一個元素
		Merge(a,n);//合并，各自有序的前半部分和後半部分 
		return 1;//退出該函數，進行下一次合并 
	} 
}
int main()
{
	int a[MAX],n;
	cin>>n;
	for(int i = 0; i < n ;i++)
		cin>>a[i];
	MergeSort(a,n);
	for(int i = 0; i < n ;i++)
		cout<<a[i]<<" "; 
 }
           

時間複雜性分析：

由于Merge所需要做的工作是将每個元素加入B中一共有n個元素，故其複雜性為O(n),而算法MergeSort的時間複雜性滿足下述遞歸方程：

            T(n)=2T(n/2)+O(n);

a=2,b=2,E=1,F(n)=O(n^Elog0(n)).T(n)=O(nlog(n)).