歸并排序理論上時間復雜度只有O(NlogN)，但是其中存在過多臨時內(nèi)存分配和copy操作而不適用于內(nèi)存排序，卻是外部排序的基本思路。下面是我的實現(xiàn)：

#include<iostream> #include<algorithm> #include<cstring> using namespace std; int g=0;/*a,b is input array* c is output array* size of c is na+nb*/ template<typename T> void merge(T a[],int na,T b[],int nb,T c[]) {T* pa=a;T* pb=b;T* pt= new T[na+nb];int i=0,j=0,k=0;while(i<na+nb){while(j<na && k<nb && pa[j]<=pb[k]){pt[i++]=pa[j++];}while(j<na && k<nb && pb[k]<=pa[j]){pt[i++]=pb[k++];}if(j==na){while(k<nb)pt[i++]=pb[k++];break;}if(k==nb){while(j<na)pt[i++]=pa[j++];break;}}cout<<"merge"<<g++<<":";for(int i=0;i<na+nb;i++){c[i]=pt[i];cout<<c[i]<<' ';}cout<<endl;delete []pt; }template<typename T> void mergesort(T a[],int n) {if(n<=1)return;int m=n/2;mergesort(a,m);mergesort(a+m,n-m);merge(a,m,a+m,n-m,a); }template<typename T> void show(T a[],int n) {for(int i=0;i<n;++i){cout<<a[i]<<' ';}cout<<endl; }int main() {int l1[]={2,7,9,12};int l2[]={3,6,8,11};int l3[8];merge(l1,4,l2,4,l3);int a[]={9,3,6,2,7,5,8,0,4,1};mergesort(a,10);show(a,10);return 0; }

　　一些注意要點：

　　　　1.歸并排序是歸并算法的一個應(yīng)用，所以要先實現(xiàn)歸并算法，排序的時候先遞歸后操作。（如果遞歸算法是在第一層處理數(shù)據(jù)然后處理分支數(shù)據(jù)就是【先操作后遞歸】，如果是先分支從最后的分支開始處理數(shù)據(jù)向第一層合并，就是【先遞歸后操作】）。

　　　　2.盡量不要遞歸申請內(nèi)存，那樣會申請大量臨時內(nèi)存，這些內(nèi)存的數(shù)據(jù)要保存又要大量的copy操作。

　　　　3.使用鏈表排序就不用臨時分配內(nèi)存也不用頻繁copy。

　　　　4.循環(huán)嵌套的邏輯一次不一定寫正確，先用while嵌套，邏輯更清晰。

轉(zhuǎn)載于:https://www.cnblogs.com/jwk000/archive/2013/06/04/3117938.html

總結(jié)

以上是生活随笔為你收集整理的基本排序算法之4——归并排序mergesort的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。