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

类型：游戏辅助大小：599KB语言：中文评分：5.0
标签：

立即下载

早就想写写几个排序的算法了，原来一直是直接调用库函数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;
}

最后的那个循环主要是为了用来判断我手写代码的正确性。

最后我们来看一下比较效率的结果（这里通过改变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类型试试。