歸并排序是一個很穩(wěn)定的排序方法，它具有以下特點： 1.時間復雜度為θ（NlogN）（關于時間復雜度的符號表示可以查看《算法導論》第一部分第三/四章），穩(wěn)定而且是比較排序模型中能達到的最快（當然就算換個很舒服的輸入也只能花同樣的時間） 2.它不是一個in place的排序算法。也就是說它的排序需要借助一個臨時數(shù)組來存放數(shù)據(jù)。
歸并排序用的是分治法 眾所周知（強行眾所周知）分治法的三個步驟：拆分（母問題為子問題）-解決（子問題）-合并（子問題的解）。歸并排序的這三個步驟描述如下： 拆分：將數(shù)組拆為兩個子數(shù)組（盡量等分） 解決：將兩個子數(shù)組分別排序 合并：此處是歸并排序的重點部分，其思路是這樣的——首先創(chuàng)建一個足以容納下兩個數(shù)組的所有元素的數(shù)列用于儲存數(shù)據(jù)，然后對于兩個已經(jīng)排好序的數(shù)列來說，比較其首元素，取小的一方填入新數(shù)列，隨后將新數(shù)列和剛處理的數(shù)列指針后移，然后如此往復，當某一個指針已經(jīng)指向數(shù)組最后一個元素之后時，將另一個數(shù)組中的元素按順序填入新數(shù)組。 不難看出，如果兩子數(shù)列已經(jīng)有序那么最后合并所得的數(shù)列一定是有序的。而當問題被遞歸式地拆分到底（bottom out）時，也就是只有一個元素之后，合并所做的只是將兩個元素按照大小順序填入一個新的只會有兩個元素的數(shù)組。
這里就只說C啦，C++的也可以按著寫反正用到的還沒有那么多不同。 首先關于臨時數(shù)組我是這么想的：既然每次都會用到對應大小的數(shù)組，那么干脆就申請一個等大的數(shù)組用于排列，正好序號還能對得上。不過考慮到每次排序完成后是臨時數(shù)組變得有序，所以在排序之后還應有個復制的過程。 因為排序的時候有排序和合并兩個操作，所以要有兩個函數(shù)。因為是自己用所以也不用關心越界/錯誤情況，所以返回值用void就好
#include <stdio.h>void mergesort(int *arr,int *tem,int begin,int end);void merge(int *arr,int *tem,int begin,int mid,int end);int main()//再次強調(diào)：你可以只寫main()但一定不要寫 void main()！{ int n,i; scanf("%d",&n); int arr[n],tem[n];//C99之后可以用變量作為容量申請數(shù)組了 mergesort(arr,tem,0,n-1); reutnr 0;}主函數(shù)就完成了，現(xiàn)在我們開始考慮mergesort函數(shù) 傳入以后要判斷是不是已經(jīng)到底了，如果到底我們是需要一個復制的過程，之后會需要遞歸排序，最后用合并函數(shù)。 于是mergesort函數(shù)寫成這樣：
void mergesort(int *arr,int *tem,int begin,int end){ if(begin<end){ int mid=(begin+end)>>1; mergesort(arr,tem,begin,mid); mergesort(arr,tem,mid+1,end); merge(arr,tem,begin,mid,end); }else{ tem[begin]=arr[begin]; }}現(xiàn)在可以開始merge函數(shù)的編寫了，這也是我認為的歸并排序最難的地方，我理出來的思路是這樣的： 因為最后是有一個復制的過程的，所以指針在開始的時候是不能變的，那么就在開始申請變量賦值用于開始的排序就好。 int *p1=tem+first,*p2=tem+mid+1,*p3=arr+first; 對于是否滿足放入數(shù)組的條件我一開始寫成這樣：
if((p1<tem+mid+1)&&(*p1<*p2))錯在哪里？ 注意如果p2都已經(jīng)到末尾了（越界），這個壞東西還是會判斷后面的垃圾數(shù)據(jù)是不是滿足條件，而我們又都知道C語言的邏輯是存在短路這個東西的，所以最后merge函數(shù)應該長這樣：
void merge(int *arr,int *tem,int first,int mid,int last){ int *p1=tem+first,*p2=tem+mid+1,*p3=arr+first; int i; for(i=0;i<last-first+1;i++){ if((p2>tem+last)||(p1<tem+mid+1)&&(*p1<*p2)){ *(p3++)=*(p1++); }else{ *(p3++)=*(p2++); } }while(first<=last){ *(tem+first)=*(arr+first);//可別忘復制這個操作 first++; }}如果感覺自己明白了，不妨動手試一試寫一個自己的歸并排序吧~新聞熱點
疑難解答
