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
using namespace std;
/* Always compile this module for speed, not size */
#pragma optimize("t", on)
/* prototypes for local routines */
template
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
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
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函数就成为了排序这些数据的首选。
