对于qsort和sort使用效率的详细对比-白红宇

对于qsort和sort使用效率的详细对比

阅读量：4223 次

发布时间：2019-05-26

本文共 5376 字，大约阅读时间需要 17 分钟。

测试环境 VS2017

思路：用qsort与sort分别对有n个随机数的数组进行m次排序。

平台：x64

sort：

头文件： algorithm

函数原型：

template< class RandomIt >　　void sort( RandomIt first, RandomIt last );　　template< class RandomIt, class Compare >　　void sort( RandomIt first, RandomIt last, Compare comp );

sort作为STL库的成员函数，肯定是本着库通用的目的，采用模板元编程实现，可对STL库提供的大部分（？不知道是不是所有，目前仅排序过vector，string（list有自己的sort））容器进行排序（我猜应该是只能针对连续地址的数据进行排序）。

参数值：要排序的起始迭代器位置，尾后迭代器位置，比较函数（可选）。默认是升序排列。

如果想要降序排列，可以：1，重载要排序的元素类型的<操作符

2，传递一个比较函数，如果第一个参数小于第二个该函数,返回true（升序）。

如果第一个参数大于第二个该函数,返回true（降序）。

比较函数的原型为：

bool cmp(const Type1 &a, const Type2 &b);

cmp 函数的返回值	描述
true	elem1将被排在elem2前面
false	对elem1与elem2的次序不做改变

qsort：

头文件： cstdlib

函数原型：

void qsort(void *base , int nelem ,int width , int (*fcmp)(const void *,const void *));

qsort作为C语言标准库函数，可对连续地址存储的变量进行排序，没有默认排序方式，必须传入比较函数，并且相对于sort的操作符重载的方式改变排序规则的策略来讲，qsort只能通过改变比较函数的方式进行排序，策略单一。

参数值：排序的起始地址，排序的元素长度，要排序元素在内存中的占位值（即sizeof），比较函数指针

比较函数的原型为：

int compare( (void *) & elem1, (void *) & elem2 );

compare 函数的返回值	描述
“< 0”	elem1将被排在elem2前面
“0”	elem1 等于 elem2
“> 0”	elem1 将被排在elem2后面

**这里需要注意的是，不同于qsort的比较函数，fcmp返回的是一个int值类型，而不是单纯的true和false

如果比较函数写成**

int comp(const void*a, const void*b){    return *(int*)a>*(int*)b;//当a

使用实例及效率比较：

最开始我是看到这篇文章中对于二者的比较：http://blog.csdn.net/pku_zzy/article/details/51462417

作者得出的结论是，qsort比sort的效率高，一般情况下前者的用时是后者的三分之一，所以他推荐在一般情况下我们应该选择qsort而不是sort。

对这一结论我有疑惑：qsort只是实现了快速排序，而STL库中的sort实现了快排，堆排，归并排等多种排序，并且针对数据量的不同做了诸多优化，如果最终效率不及qsort，那么STL实现sort的意义在哪儿？

而且，我本人对STL库是抱着非常敬畏和尊敬的感情的，我不相信STL库的开发者们会做出这样没有意义的事情，并且还把它加到C++的标准库中。

带着如上疑问，我决定自己动手写一个测试，来看看qsort和sort的排序效率到底是怎样的。

以下为测试代码：

#include 
   
    #include 
    
     #include 
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAX_SIZE 1000#define N_TIMES 10000int inline comp(const void*a, const void*b)//当返回值大于0时，认为a>b,如果此时与实际情况相符，则按升序排列，相反则按降序排列 //返回值等于0，认为a=b，返回值小于0认为a
          
            (*(int*)b)的形式，因为这样只会返回0和1，而0是被认为二者是相等的{ return *(int*)a - *(int*)b; //return 0;}inline bool comp_sort(int a, int b)//当返回值为true时，认为a>b,否则，认为a<=b{ return a < b; //return false;}int main(void){ vector
           
            
              > collect_qsort; vector
             
              
                > collect_sort; vector
               
                 temp(MAX_SIZE); srand((unsigned)time(NULL));//置随机种子 for (int i = 0; i < MAX_SIZE; i++)//将temp填满随机数 { temp[i] = rand(); } for (int i = 0; i < N_TIMES; i++)//两个测试样例都填充N_TIMES次temp //这里两种排序的测试样例是完全相同的，都是对temp进行N_TIMES次排序 { collect_qsort.push_back(temp); collect_sort.push_back(temp); } //下面是计时操作一些相关变量的初始化 LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; double time; QueryPerformanceFrequency(&nFreq);//获取系统时钟频率 QueryPerformanceCounter(&nBeginTime);//获取系统当前计数器计数值 /***************************用qsort对样例进行N_TIMES次排序***************************************/ for(int i=0;i

在该项测试中，我们选取了1000个int型的随机数据进行排列，分别用sort与qsort对其进行1e4次排列。

在debug模式下，我发现确实如上面那篇博客的作者所言，sort的用时几乎是qsort的三倍甚至更多

这里写图片描述

但是IDE在debug模式下对代码的监视是要耗费资源的，越大规模的算法，在debug模式下对其监视所花费的资源也就越多，庞大如VS这样的IDE，debug所消耗的资源更甚。

因此同样的代码我又在release模式下跑了一遍：

这里写图片描述

可以看到，在release模式下，两种排序的时间都大幅降低了，并且sort的用时是明确小于qsort的用时的。

所以，到这里我可以肯定，上面那篇博客的作者的测试就是在debug和release的选择上出了问题。

为了得出一般性的结论，我们选择不同的输入规模，来看一看二者的效率是否会发生逆转

修改测试代码中的MAX_SIZE 与 N_TIMES（N_TIMES的作用仅仅是在小规模输入下增加对同样的数据的排序次数，以消除计时误差带来的影响，不影响sort与qsort的效率的排名结果）

我们来看一看不同规模的输入下，二者的相对表现如何：

输入规模（MAX_SIZE ）排序次数（N_TIMES） qsort用时 sort用时 qsort:sort

10 10000000 1.915217s 0.853853s 2.24:1

100 1000000 3.634150s 2.172662s 1.67:1

1000 100000 8.398367s 5.571055s 1.51:1

10000 10000 10.812114s 8.111797s 1.33:1

100000 1000 13.201909s 10.600798s 1.25:1

1000000 100 11.275247s 9.838172s 1.15:1

10000000 10 11.255788s 9.987730s 1.13:1

100000000 1 10.782703s 9.452227s 1.14:1

由上表我们可以看出，从10到1e8（即1亿）的数据量级的比较中，虽然随着数据量级的增长，qsort的效率越来越接近sort的效率，但是qsort：sort的值始终是大于1的。因此不难得出结论，一般情况下而言，sort的效率始终是高于qsort的效率的

因为int是内置类型，我想可能会有影响，所以又定义了一个自定义类型Point

class Point{public:    int x;    int y;};

以Point点到坐标原点的距离作为排序的依据：

代码实现如下

#include 
   
    #include 
    
     #include 
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;class Point{public: int x; int y;};int inline comp(const void*a, const void*b)//当返回值大于0时，认为a>b,如果此时与实际情况相符，则按升序排列，相反则按降序排列 //返回值等于0，认为a=b，返回值小于0认为a
          
            (*(Point*)b)的形式，因为这样只会返回0和1，而0是被认为二者相等的{ return ((Point*)a)->x* ((Point*)a)->x + ((Point*)a)->y* ((Point*)a)->y - ((Point*)b)->x* ((Point*)b)->x - ((Point*)b)->y* ((Point*)b)->y;}inline bool comp_sort(Point &a, Point &b)//当返回值为true时，认为a>b,否则，认为a<=b{ return a.x*a.x + a.y*a.y < b.x*b.x + b.y*b.y;}#define MAX_SIZE 10000#define N_TIMES 10000int main(void){ vector
           
            
              > collect_qsort; vector
             
              
                > collect_sort; vector
               
                 temp(MAX_SIZE); srand((unsigned)time(NULL));//置随机种子 for (int i = 0; i < MAX_SIZE; i++)//将temp填满随机数 { temp[i].x = rand() % 100; temp[i].y = rand() % 100; } for (int i = 0; i < N_TIMES; i++)//两个测试样例都填充N_TIMES次temp //这里两种排序的测试样例是完全相同的，都是对temp进行N_TIMES次排序 { collect_qsort.push_back(temp); collect_sort.push_back(temp); } //下面是计时操作一些相关变量的初始化 LARGE_INTEGER nFreq; LARGE_INTEGER nBeginTime; LARGE_INTEGER nEndTime; double time; QueryPerformanceFrequency(&nFreq);//获取系统时钟频率 QueryPerformanceCounter(&nBeginTime);//获取系统当前计数器计数值 /***************************用qsort对样例进行N_TIMES次排序***************************************/ for (int i = 0; i