/*
作者：bacoo
日期：2008年9月21日
一個(gè)比較復(fù)雜的二路歸并排序算法，完成由小到大的排序功能
算法摒除了最初始的“從兩路頭部依次取出數(shù)據(jù)，經(jīng)過(guò)比較后輸出較小值”方法；
而是找出“頭大”的一路，然后把另一路分成許多片斷，然后插入到“頭大”的那路中，
這里面尋找插入點(diǎn)使用了二分法查找以提高效率，
需要說(shuō)明的是，該算法在兩部“交錯(cuò)”不是很?chē)?yán)重的情況下有較好的效率。
*/
#include <iostream>
using namespace std;
int find2fenfa(int a[],int h,int t,int num){//利用二分法來(lái)查找num的位置，要求在[h,t]之間
while(h<t){
int m=(h+t)/2;
if(num==a[m]){
return m;
}
else if(num<a[m])
t=m-1;
else
h=m+1;
}
return h;//這只給出一個(gè)推薦位置，也即最相關(guān)位置，在后續(xù)應(yīng)用該結(jié)果時(shí)，需要做分析處理
}
void movedata(int a[],int pos,int h,int t){//該函數(shù)用于將[h,t]區(qū)間內(nèi)的數(shù)據(jù)移動(dòng)到pos指定的插入位置
int s;
if(pos>t){//插入點(diǎn)在后方
for(int i=t;i>=h;i--){
s=a[i];
for(int j=i;j<pos-1;j++){
a[j]=a[j+1];
}
a[--pos]=s;
}
}
else if(pos<h){//插入點(diǎn)在前方
for(int i=h;i<=t;i++){
s=a[i];
for(int j=i;j>pos;j--){
a[j]=a[j-1];
}
a[pos++]=s;
}
}
}
void merge2(int a[],int h1,int t1,int h2,int t2)//該函數(shù)用于兩路合并，h和t分別表示頭部和尾部
{
if( h1>t1 || h2>t2 )return;
int i_pos=-1,s_end=-1;
if(a[h1]<=a[h2]){//確保都是為一個(gè)大數(shù)查找插入的位置
i_pos=find2fenfa(a,h1,t1,a[h2]);
a[i_pos]<=a[h2] ? i_pos++ : i_pos;//根據(jù)推薦位置對(duì)應(yīng)的數(shù)值大小來(lái)調(diào)整合適的插入點(diǎn)
if(i_pos>t1)return;//已經(jīng)有序，不必再合并了
s_end=find2fenfa(a,h2,t2,a[i_pos]);//為待插入的部分找到一個(gè)終點(diǎn)，起始點(diǎn)已經(jīng)由h2來(lái)標(biāo)記了
a[s_end]>=a[i_pos] ? s_end-- : s_end;//微調(diào)，很必要的
movedata(a,i_pos,h2,s_end);
merge2(a,i_pos+s_end-h2,s_end,s_end+1,t2);
}else{
i_pos=find2fenfa(a,h2,t2,a[h1]);
a[i_pos]<=a[h1] ? i_pos++ : i_pos;
if(i_pos>t2){
movedata(a,h1,h2,t2);
return;
}
s_end=find2fenfa(a,h1,t1,a[i_pos]);
a[s_end]>=a[i_pos] ? s_end-- : s_end;
movedata(a,i_pos,h1,s_end);
merge2(a,h1,t1-(s_end-h1+1),t1-s_end+h1,t2);
}
}
void sort_2way(int a[],int len){//兩路歸并，這個(gè)函數(shù)主要是為merge2函數(shù)每次分配合適的兩路
int x=1;//表示當(dāng)前進(jìn)行的兩路歸并中的“路的長(zhǎng)度”
int h1,t1,h2,t2;
while(x<=len){
for(int i=0;i<len;i+=2*x){
h1=i;
h2=i+x;
t1=h2-1;
t2=h2+x-1;
if(h2>=len)continue;
else{
if(t2>=len){
merge2(a,h1,t1,h2,len-1);
break;
}else
merge2(a,h1,t1,h2,t2);
}
}
x*=2;
}
}
void main(){
int a[10];
int len=sizeof(a)/sizeof(a[0]);
for(int i=0;i<len;i++)a[i]=rand()%100;
sort_2way(a,len);
for(i=0;i<len;i++)cout<<a[i]<<endl;
}
單次運(yùn)行結(jié)果為：
0
24
34
41
58
62
64
67
69
78
Press any key to continue