/*
作者：bacoo
日期：2008年9月21日
一個比較復雜的二路歸并排序算法，完成由小到大的排序功能
算法摒除了最初始的“從兩路頭部依次取出數據，經過比較后輸出較小值”方法；
而是找出“頭大”的一路，然后把另一路分成許多片斷，然后插入到“頭大”的那路中，
這里面尋找插入點使用了二分法查找以提高效率，
需要說明的是，該算法在兩部“交錯”不是很嚴重的情況下有較好的效率。
*/
#include <iostream>
using namespace std;
int find2fenfa(int a[],int h,int t,int num){//利用二分法來查找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;//這只給出一個推薦位置，也即最相關位置，在后續應用該結果時，需要做分析處理
}
void movedata(int a[],int pos,int h,int t){//該函數用于將[h,t]區間內的數據移動到pos指定的插入位置
int s;
if(pos>t){//插入點在后方
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){//插入點在前方
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)//該函數用于兩路合并，h和t分別表示頭部和尾部
{
if( h1>t1 || h2>t2 )return;
int i_pos=-1,s_end=-1;
if(a[h1]<=a[h2]){//確保都是為一個大數查找插入的位置
i_pos=find2fenfa(a,h1,t1,a[h2]);
a[i_pos]<=a[h2] ? i_pos++ : i_pos;//根據推薦位置對應的數值大小來調整合適的插入點
if(i_pos>t1)return;//已經有序，不必再合并了
s_end=find2fenfa(a,h2,t2,a[i_pos]);//為待插入的部分找到一個終點，起始點已經由h2來標記了
a[s_end]>=a[i_pos] ? s_end-- : s_end;//微調，很必要的
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){//兩路歸并，這個函數主要是為merge2函數每次分配合適的兩路
int x=1;//表示當前進行的兩路歸并中的“路的長度”
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;
}
單次運行結果為：
0
24
34
41
58
62
64
67
69
78
Press any key to continue