qsort与sort的性能比较

oyangningtao

在C/C++标准库中提供了快速排序的函数qsort()；在STL中也提供了sort()排序函数，那么这两个函数哪个快呢？
取int类型的数据进行排序，对数据规模为1000，10000，100000的数据集分别在VC6.0（Debug and Release模式），Dev C++（集成GCC/G++编译器的IDE工具）和CodeBlock（一个开源的C/C++ IDE编译工具）进行了比较，得到如下结果：
一 VC Debug模式下
1）数据规模为1000

2）数据规模为10000

3）数据规模为100000


二 VC Release模式下
1）数据规模为1000

2）数据规模为10000

3）数据规模为100000


三 Dev C++工具下
1）数据规模为1000

2）数据规模为10000

3）数据规模为100000


四 CodeBlock工具下
1）数据规模为1000

2）数据规模为10000

3）数据规模为100000


从以上的结果中不难看出，同样的数据规模，在VC下qsort排序算法需要的时间是sort的2倍以上。两者都是“快速排序”，但qsort采用的不是简单的快速排序，而是结合内插排序算法，并且编译器根据运行平台作了一定的优化，可以保证很好的平均性能。在DEV C++和CodeBlock下，编译器不会对代码作任何的优化，qsort反而要比sort快不少！在这两个平台下的运行速度应该是比较客观地反应出qsort和sort的快慢！相信在linux/unix下qsort要比sort快（有测试平台的朋友可以试试)。

oyangningtao

验证代码如下

#include <iostream>
#include <vector>
#include <algorithm>
#include "MyTimer.h"
#include <stdlib.h>

using namespace std;

const int C_Size = 100000;

int Compare(const void *a,const void *b)
{
return (*(int *)a - *(int *)b);
}

int main()
{
vector<int> num;
int i,element;
int array[C_Size];
MyTimer mt;

cout << "排序规模为:" << C_Size << endl;

for(i=0;i<C_Size;i++)
{
element = rand()%1000;
num.push_back(element);
array[i] = rand()%1000;
}

mt.Start();
sort(num.begin(),num.end());
mt.End();
cout << "sort() cost time:" << mt.costTime << " us" << endl;

mt.Reset();
mt.Start();
qsort(array,C_Size,sizeof(int),Compare);
mt.End();
cout << "qsort() cost time:" << mt.costTime << " us" << endl;

return 0;
}