网上的文章当提到std::sort和qsort的区别时，通常把它们的性能差异归因于qsort的反引用开销，我们在这里通过实验来测试看看是不是这样，并且判断std::sort的算法是否有较之于qsort代码更优的性能，或者反过来。
测试用的源代码如下：
main.cpp 主函数所在的文件
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <algorithm>
#include "m_qsort.cpp"
#include "funcs.h"
using namespace std;
#define N 1000000
int comp(const void* a,const void* b)
{
return *(int*)a-*(int*)b;
}
void main()
{
int i,j,*a,*b;
clock_t st,et,tt[3]={0};
a=(int*)malloc(sizeof(int)*N);
b=(int*)malloc(sizeof(int)*N);
getchar();
for (i=0;i<10;i++)
{
m_srand((long)time(NULL));
for (j=0;j<N;j++) a[j]=m_rand();
memcpy(b,a,N*sizeof(int));
st=clock();
qsort(b,N,sizeof(int),comp);
et=clock();
tt[0]+=(et-st);
memcpy(b,a,N*sizeof(int));
st=clock();
m_qsort2(b,N);
et=clock();
tt[1]+=(et-st);
memcpy(b,a,N*sizeof(int));
st=clock();
sort(b,b+N);
et=clock();
tt[2]+=(et-st);
}
printf("qsort %d ms\n",tt[0]/10);
printf("m_qsort2 %d ms\n",tt[1]/10);
printf("sort %d ms\n",tt[2]/10);
getchar();
}
funcs.h
void m_srand(long seed);
int m_rand();
m_qsort.cpp 用于测试qsort修改版的代码
#include <algorithm>
using namespace std;
/* Always compile this module for speed, not size */
#pragma optimize("t", on)
/* prototypes for local routines */
template<class _RanIt>
static void __cdecl shortsort(_RanIt *lo, _RanIt *hi);
#define CUTOFF 8 /* testing shows that this is good value */
#define STKSIZ (8*sizeof(void*) - 2)
template<class _RanIt>
void m_qsort (
_RanIt base,
size_t num
)
{
_RanIt lo, hi; /* ends of sub-array currently sorting */
_RanIt mid; /* points to middle of subarray */
_RanIt loguy, higuy; /* traveling pointers for partition step */
size_t size; /* size of the sub-array */
_RanIt lostk[STKSIZ], histk[STKSIZ];
int stkptr; /* stack for saving sub-array to be processed */
if (num < 2)
return; /* nothing to do */
stkptr = 0; /* initialize stack */
lo = base;
hi = base +num-1; /* initialize limits */
recurse:
size = hi - lo + 1; /* number of el's to sort */
/* below a certain size, it is faster to use a O(n^2) sorting method */
if (size <= CUTOFF) {
shortsort(lo, hi);
//_Insertion_sort(lo,hi+1);
}
else {
mid = lo + size / 2; /* find middle element */
/* Sort the first, middle, last elements into order */
if (*lo>*mid) {
iter_swap(lo, mid);
}
if (*lo>*hi) {
iter_swap(lo, hi);
}
if (*mid>*hi) {
iter_swap(mid, hi);
}
loguy = lo;
higuy = hi;
for (;;) {
if (mid > loguy) {
do {
loguy ++;
} while (loguy < mid && *loguy<=*mid);
}
if (mid <= loguy) {
do {
loguy ++;
} while (loguy <= hi && *loguy<=*mid);
}
/* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy,
either loguy > hi or A[loguy] > A[mid] */
do {
higuy --;
} while (higuy > mid && *higuy> *mid);
if (higuy < loguy)
break;
iter_swap(loguy, higuy);
if (mid == higuy)
mid = loguy;
}
higuy ++;
if (mid < higuy) {
do {
higuy --;
} while (higuy > mid && *higuy==*mid);
}
if (mid >= higuy) {
do {
higuy --;
} while (higuy > lo && *higuy==*mid);
}
if ( higuy - lo >= hi - loguy ) {
if (lo < higuy) {
lostk[stkptr] = lo;
histk[stkptr] = higuy;
++stkptr;
} /* save big recursion for later */
if (loguy < hi) {
lo = loguy;
goto recurse; /* do small recursion */
}
}
else {
if (loguy < hi) {
lostk[stkptr] = loguy;
histk[stkptr] = hi;
++stkptr; /* save big recursion for later */
}
if (lo < higuy) {
hi = higuy;
goto recurse; /* do small recursion */
}
}
}
--stkptr;
if (stkptr >= 0) {
lo = lostk[stkptr];
hi = histk[stkptr];
goto recurse; /* pop subarray from stack */
}
else
{
return; /* all subarrays done */
}
}
template<class _RanIt>
static void __cdecl shortsort (
_RanIt *lo,
_RanIt *hi
)
{
_RanIt *p, *max;
while (hi > lo) {
/* A[i] <= A[j] for i <= j, j > hi */
max = lo;
for (p = lo+1; p <= hi; p ++) {
/* A[i] <= A[max] for lo <= i < p */
if (*p>*max) {
max = p;
}
}
iter_swap(max, hi);
hi --;
}
}
m_rand.cpp 用于生成0~0x00ffffff之间随机数的代码
static long holdrand;
void m_srand(long seed)
{
holdrand=seed;
}
int m_rand()
{
return ((holdrand = holdrand * 214013L + 2531011L) & 0x00ffffff);
}
主函数分成三段测试代码，每段测试一个函数：qsort、m_qsort、std::sort。其中m_qsort是复制qsort的代码过来然后修改而成。测试数据共有10组，取平均值输出。下面我们开始测试。
先测试qsort和std::sort两个函数，把另外两段测试代码注释掉以节约时间：
qsort 1156 ms
sort 860 ms
实验证明，std::sort比qsort快25.6%。我们把N扩大为两倍2000000，即数组大小扩大成两倍，测试结果：
qsort 2416 ms
sort 1828 ms
实验结果表明在数据增长成两倍的时候，qsort运行时间增长为原来的2.09倍；sort增长为原来的2.13倍。sort算法的增长速度稍快。
std::sort比qsort快25.6%，到底快在哪里呢？我们现在来看看。我们修改了qsort，成为m_qsort，它使用了模板，不需要传入函数指针，而且换掉了原来低效的逐个字节交换的swap函数，用iter_swap代替。比较三个函数：
qsort 1131 ms
m_qsort 640 ms
sort 857 ms
我们发现，经过对qsort函数进行修改之后，它竟然比sort函数快25.3%！这说明qsort函数的主要开销在于直接对字节指针的操作。这同时也说明，对于基本没有重复键的数据来说，qsort比sort要快。
我们再来比较一下特殊情况。使用系统自带的srand函数和rand函数，生成0~0x00007fff的数，这样1000000个数中就会每个数平均有31个重复值。我们看一下运行结果：
qsort 894 ms
m_qsort 519 ms
sort 554 ms
可以清楚地看到，在数据重复比较多的时候，sort的性能明显得到了提高。考虑一种极限情况，所有数据相同，我们修改代码再运行一次：
qsort 72 ms
m_qsort 42 ms
sort 24 ms
这次很明显了，对于重复数据，sort函数的处理能力明显强于qsort。这主要是和sort函数三路划分分得更细致有关。
我们接着考虑递增和递减数组。修改代码然后测试，结果如下：
qsort 497 ms
m_qsort 234 ms
sort 203 ms
sort函数的运行时间比m_qsort要少。我们可以看到，相比随机数据，有序数据在快速排序的时候得到了很好的优化。再来看递减的数组。
qsort 534 ms
m_qsort 261 ms
sort 338 ms
递减数组中sort函数略逊于qsort改进版，这大概是因为sort函数取样9个点造成过多交换开销造成的。
从整体上看，我们得出这样一个结论：对于随机基本无重复的数据，qsort的改进版比sort函数优秀；而sort函数由于对分区比较细致，所以处理重复数据较多的数组则会比较优化。而我们平常所遇到的数据，比如出生年月，性别等，都有很多的重复值，所以sort函数就成为了排序这些数据的首选。
