歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用卵牍。將已有序的子序列合并，得到完全有序的序列廉羔；即先使每個(gè)子序列有序，再使子序列段間有序僻造。若將兩個(gè)有序表合并成一個(gè)有序表憋他，稱(chēng)為二路歸并
歸并排序是一種穩(wěn)定的排序算法，其時(shí)間復(fù)雜度為:O(nlogn)
算法思路（從小到大）：
1髓削、對(duì)于一組數(shù)據(jù)a[N]竹挡，申請(qǐng)臨時(shí)空間，temp[N],用于臨時(shí)存放數(shù)據(jù)立膛，劃分為兩個(gè)序列
2揪罕、設(shè)置兩個(gè)指針?lè)謩e指向兩個(gè)序列的首部，其中中間數(shù)據(jù)mid=(start+end)/2劃分到前一個(gè)序列當(dāng)中
3宝泵、比較兩個(gè)指針?biāo)赶虻臄?shù)據(jù)好啰，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
4儿奶、重復(fù)步驟3框往，直到這兩個(gè)指針的某個(gè)指針超出自身所指向序列
5、將另外一個(gè)序列全部依次放入到臨時(shí)數(shù)組中（合并空間）
#include<stdio.h>
/*歸并排序*/
void Merge_Sort(int *arr, int *temparr,int start,int mid,int end)
{
? ? int left_start = start ;
? ? int left_end? = mid ;
? ? int right_start = mid+1 ;
? ? int right_end? = end ;
? ? int index = start ;
? ? while(left_start<=left_end&&right_start<=right_end)
? ? {
? ? ? ? if(arr[left_start]>arr[right_start])
? ? ? ? ? ? temparr[index++] = arr[right_start++] ;
? ? ? ? else
? ? ? ? ? ? temparr[index++] = arr[left_start++] ;
? ? }
? ? while(left_start<=left_end)
? ? ? ? temparr[index++] = arr[left_start++] ;
? ? while(right_start<=right_end)
? ? ? ? temparr[index++] = arr[right_start++] ;
? ? for(index = start ;index<=end ;++index)
? ? ? ? arr[index] = temparr[index] ;
}
void Sort_Message(int *arr, int *temparr,int start,int end)
{
? ? if(start<end)
? ? {
? ? ? ? int mid = (start+end)/2 ;
? ? ? ? Sort_Message(arr,temparr,start,mid) ;
? ? ? ? Sort_Message(arr,temparr,mid+1,end) ;
? ? ? ? Merge_Sort(arr,temparr,start,mid,end) ;
? ? }
}
int main(void)
{
? ? int a[] = {9,2,5,3,7,4,8,0} ;
? ? int n = sizeof(a)/sizeof(a[0]) ;
? ? int i, temp[8] ;
? ? printf("原序列為:") ;
? ? for(i=0;i<n;++i)
? ? ? ? printf("%d ",a[i]) ;
? ? printf("\n") ;
? ? Sort_Message(a,temp,0,n-1) ;
? ? printf("\n排后序列:") ;
? ? for(i=0;i<n;++i)
? ? ? ? printf("%d ",a[i]) ;
? ? printf("\n") ;
? ? return 0 ;
}
