手写归并排序算法和sort(),qsort()的比较

早就想写写几个排序的算法了，原来一直是直接调用库函数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
再附上归并排序的两个主要函数代码：
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]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<
最后的那个循环主要是为了用来判断我手写代码的正确性。
最后我们来看一下比较效率的结果（这里通过改变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()
开始我是怀疑排序元素类型的原因，不过换了double试了一下，还是同样的结果，不过换用double有点换汤不换药的感觉，大家如有有兴趣的话可以用string类型试试。