利用兩個陣列互相作為對方的輔助陣列來實作，先二路劃分，再從單個元素開始歸并，代碼如下：
/* 二路歸并排序，采用了遞回的做法，它首先將整個佇列劃分為兩個部分，再一次對這兩個部分進行二分操作， 直到每個部分只包含一個元素為止，然后再依次對這些只包含一個元素的部分開始進行歸并，然后遞回操作會依次向上 進行回溯，最后回傳已排好序的佇列，排序完成， 時間復雜度n*log2n */ #include <iostream> using namespace std; void merge(int * b,int * t,int s,int mid,int e){ int i=s; int j=mid+1; int idx=s; while(i<=mid&&j<=e) { if(b[i]<b[j]) { t[idx++]=b[i++]; } else { t[idx++]=b[j++]; } } while(i<=mid) { t[idx++]=b[i++]; } while(j<=e) { t[idx++]=b[j++]; } } void TwoGuiBing(int * a,int * t,int s,int e){ if(s==e) { t[s]=a[s]; return; } int mid=(s+e)/2; TwoGuiBing(t,a,s,mid); TwoGuiBing(t,a,mid+1,e); merge(a,t,s,mid,e); for(int i=s;i<=e;i++) { cout<<t[i]<<" "; //a[i]=t[i]; } cout<<endl; } int main(){ int s[10]={4,1,5,2,4,3,98,6,65,1};//1 1 2 3 4 4 5 6 65 98 int t[10]; for(int i=0;i<10;i++) { t[i]=s[i]; } TwoGuiBing(s,t,0,9); for(int i=0;i<10;i++){ cout<<t[i]<<" "; } cout<<endl; return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/105921.html
標籤：C++
上一篇：c++記憶體模型