这函数真够长的，吓死！
记得我前两天看到别人做的一个程序，用的是自己写的快速排序，而我用的qosrt，结果我的100ms，他的350ms。这程序真贼快的
因为我把每天的倾城都安排好了，所以只有半个小时的时间看，所以没看完，先注释一部分吧，明天再补一部分，估计一下子还看不完。整个qsort的代码如下：
#include <alloca.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
/* 交换一块内存数据, 长度为size字节 */
#define SWAP(a, b, size) \\
do \\
{ \\
register size_t __size = (size); \\
register char *__a = (a), *__b = (b); \\
do \\
{ \\
char __tmp = *__a; \\
*__a++ = *__b; \\
*__b++ = __tmp; \\
} while (--__size > 0); \\
} while (0)
#define MAX_THRESH 4
typedef struct{
char *lo;
char *hi;
}stack_node;
/* 初步猜测lo和hi，的功能，根据下面的PUSH和POP宏, 估计是一段内存的两端
lo就是low, hi就是high，就是说从low所指向的位置到hi所指向的位置就是
这个元素的内容。 */
#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
/* 关于这个CHAR_BIT在网上搜了下，在limits.h文件中有定义:
#define CHAR_BIT 8 */
#define PUSH(low, high) ((void)((top->lo = (low)), (top->hi = (high)), ++top))
#define POP(low, high) ((void)(--top, (low = top->lo), (high = top->hi)))
/* 译(准确的说是注释的人:zqynux/My S-K-Y)者感到有点奇怪，
能转换void这个类型 */
#define STACK_NOT_EMPTY (stack < top)
/* 上面三个都是超快速 + 简单的栈操作 */
void _quicksort (void *const pbase, size_t total_elems, size_t size,
__compar_d_fn_t cmp, void *arg)
/* 其实__compar_d_fn_t这个类型我没查也知道是什么类型, 就是一个函数指针,
所以就没查了. */
{
register char *base_ptr = (char *) pbase;
const size_t max_thresh = MAX_THRESH * size;
if(total_elems == 0)
/* Avoid lossage with unsigned arithmetic below. */
return;
if(total_elems > MAX_THRESH){
char *lo = base_ptr;
char *hi = &lo[size * (total_elems - 1)];
stack_node stack[STACK_SIZE];
stack_node *top = stack;
PUSH (NULL, NULL);
while (STACK_NOT_EMPTY){
char *left_ptr;
char *right_ptr;
/* Select median value from among LO, MID, and HI. Rearrange
LO and HI so the three values are sorted. This lowers the
probability of picking a pathological pivot value and
skips a comparison for both the LEFT_PTR and RIGHT_PTR in
the while loops. */
char *mid = lo + size * ((hi - lo) / size >> 1);
if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
SWAP (mid, lo, size);
if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
SWAP (mid, hi, size);
else
goto jump_over;
if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
SWAP (mid, lo, size);
jump_over: ;
left_ptr = lo + size;
right_ptr = hi - size;
/* Here\'s the famous ``collapse the walls\'\' section of quicksort.
Gotta like those tight inner loops! They are the main reason
that this algorithm runs much faster than others. */
do{
while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
left_ptr += size;
while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
right_ptr -= size;
if (left_ptr < right_ptr){
SWAP (left_ptr, right_ptr, size);
if (mid == left_ptr)
mid = right_ptr;
else if (mid == right_ptr)
mid = left_ptr;
left_ptr += size;
right_ptr -= size;
}else if (left_ptr == right_ptr){
left_ptr += size;
right_ptr -= size;
break;
}
}while (left_ptr <= right_ptr);
/* Set up pointers for next iteration. First determine whether
left and right partitions are below the threshold size. If so,
ignore one or both. Otherwise, push the larger partition\'s
bounds on the stack and continue sorting the smaller one. */
if ((size_t) (right_ptr - lo) <= max_thresh){
if ((size_t) (hi - left_ptr) <= max_thresh)
/* Ignore both small partitions. */
POP (lo, hi);
else
/* Ignore small left partition. */
lo = left_ptr;
}else if ((size_t) (hi - left_ptr) <= max_thresh)
/* Ignore small right partition. */
hi = right_ptr;
else if ((right_ptr - lo) > (hi - left_ptr)){
/* Push larger left partition indices. */
PUSH (lo, right_ptr);
lo = left_ptr;
}else{
/* Push larger right partition indices. */
PUSH (left_ptr, hi);
hi = right_ptr;
}
}
}
/* Once the BASE_PTR array is partially sorted by quicksort the rest
is completely sorted using insertion sort, since this is efficient
for partitions below MAX_THRESH size. BASE_PTR points to the beginning
of the array to sort, and END_PTR points at the very last element in
the array (*not* one beyond it!). */
#define min(x, y) ((x) < (y) ? (x) : (y))
{
char *const end_ptr = &base_ptr[size * (total_elems - 1)];
char *tmp_ptr = base_ptr;
char *thresh = min(end_ptr, base_ptr + max_thresh);
register char *run_ptr;
/* Find smallest element in first threshold and place it at the
array\'s beginning. This is the smallest array element,
and the operation speeds up insertion sort\'s inner loop. */
for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
tmp_ptr = run_ptr;
if (tmp_ptr != base_ptr)
SWAP (tmp_ptr, base_ptr, size);
/* Insertion sort, running from left-hand-side up to right-hand-side. */
run_ptr = base_ptr + size;
while ((run_ptr += size) <= end_ptr){
tmp_ptr = run_ptr - size;
while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
tmp_ptr -= size;
tmp_ptr += size;
if (tmp_ptr != run_ptr){
char *trav;
trav = run_ptr + size;
while (--trav >= run_ptr){
char c = *trav;
char *hi, *lo;
for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
*hi = *lo;
*hi = c;
}
}
}
}
}