早就想寫寫幾個排序的算法了，原來一直是直接調用庫函數sort()和qsort(),導致自己對它們內部是實現機理有些忽視。現在就把我剛剛手寫的一個歸并排序（時間復雜度是o(n*log(n))），其中我是用遞歸來實現的。在代碼中我還比較了手寫歸并，sort(),qsort(),的效率。
先對程序中所用的數據結構做下聲明，方便大家理解接下來的程序：
int res[cnt]; int num1[cnt],num2[cnt],num3[cnt];
其中res是歸并時用的輔助數組，num1，num2，num3都是保存的是待排序的數，為了使程序具有可比性，所以把它們的元素賦成相同的值：
void init()
{
for(int i=0;i<cnt;i++)
{
num3[i]=num1[i]=num2[i]=rand();
}
}再附上歸并排序的兩個主要函數代碼：
void merge(int start,int end,int tail)
{
int i=start,j=end+1;
int t=start;
while(i<=end && j<=tail)
{
while(i<=end && num1[i]<=num1[j])
{
res[t++]=num1[i++];
}
while(j<=tail && num1[j]<num1[i])
{
res[t++]=num1[j++];
}
if(i>end && j<=tail)
{
while(j<=tail)
{
res[t++]=num1[j++];
}
break;
}
if(j>tail && i<=end)
{
while(i<=end)
{
res[t++]=num1[i++];
}
break;
}
}
for(int i=start;i<=tail;i++)
{
num1[i]=res[i];
}
}void mergesort(int l,int r)
{
if(l==r)
{
res[l]=num1[l];
return ;
}
int mid=(l+r)>>1;
mergesort(l,mid);
mergesort(mid+1,r);
merge(l,mid,r);
return ;
}主函數如下：
int main()
{
init();
clock_t clk1,clk2,clk3,clk4,clk5,clk6;
clk1=clock();
mergesort(0,cnt-1);
clk2=clock();
cout<<"歸并："<<(double)(clk2-clk1)/CLOCKS_PER_SEC<<endl;
clk3=clock();
sort(num2,num2+cnt);
clk4=clock();
cout<<"sort:"<<(double)(clk4-clk3)/CLOCKS_PER_SEC<<endl;
clk5=clock();
qsort(num3,cnt,sizeof(int),cmp);
clk6=clock();
cout<<"qsort:"<<(double)(clk6-clk5)/CLOCKS_PER_SEC<<endl;
for(int i=0;i<cnt;i++)
{
if(num1[i]!=num2[i] || num1[i]!=num3[i])
{
cout<<"not equal"<<endl;
cout<<setprecision(4)<<num1[i]<<" "<<num2[i]<<" "<<num3[i]<<" "<<i<<endl;
break;
}
}
system("pause");
return 0;
}最后的那個循環(huán)主要是為了用來判斷我手寫代碼的正確性。
最后我們來看一下比較效率的結果（這里通過改變cnt的數量級，來經行多組對比）：
當cnt=50000時的輸出為：
歸并：0.018
sort:0.099
qsort:0.039
當cnt=500000時的輸出為：
歸并：0.181
sort:1.066
qsort:0.393
當cnt=5000000時的輸出為：
歸并：1.931
sort:9.484
qsort:3.881
從以上三組數據可以看出它們之間的效率關系為：sort()<qsort()<手寫歸并，回到理論上它們三個的平均時間復雜度都是o（n*log(n)），可是在這里出現的差別還是比較大的。記得原來做ACM的時候經常會聽到有人說sort()要比qsort()高效，但這里的結果卻與這個說法不相符。
開始我是懷疑排序元素類型的原因，不過換了double試了一下，還是同樣的結果，不過換用double有點換湯不換藥的感覺，大家如有有興趣的話可以用string類型試試。
喜歡 
頂
難過
囧
圍觀
無聊