為什麼自己寫的qsort比不上C語言庫里自帶的qsort效率高？

#define SWAP(a, b, size)
do
{
size_t __size = (size);
char *__a = (a), *__b = (b);
do
{
char __tmp = *__a;
*__a++ = *__b;
*__b++ = __tmp;
} while (--__size &> 0);
} while (0)

/*
為了閱讀方便，我把用於宏定義續行用的去掉了，方便看到語法高亮。

SWAP的定義很簡單，只是以char為單位長度進行交換。實際上，對於足夠大的對象，這裡還有
一定的優化空間，但qsort不能假定你的對象足夠大。這也是qsort統計性能不如C++的
std::sort的原因之一。

所謂qsort並不是單純的快速排序，當快速排序劃分區間小到一定程度時，改用插入排序可以在
更少的耗時內完成排序。glibc將這個小區間定義為元素數不超過常數4的區間：
*/

#define MAX_THRESH 4

/*
可以認為對每一個小區間的插入排序耗時是不超過一個常數值（即對4個元素進行插入排序的最
差情況）的，這樣插入排序總耗時也可以認為是線性的，不影響總體時間複雜度。

接下來這段不難理解：
*/

typedef struct
{
char *lo;
char *hi;
} stack_node;

#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
#define PUSH(low, high) ((void) ((top-&>lo = (low)), (top-&>hi = (high)), ++top))
#define POP(low, high) ((void) (--top, (low = top-&>lo), (high = top-&>hi)))
#define STACK_NOT_EMPTY (stack &< top) /* 這顯然是要手動維護棧來模擬遞歸，避免實際遞歸的函數調用開銷了。題主自己的實現在元素數 量過多的時候會崩潰，估計就是遞歸過深爆棧了。 比較值得一提的是STACK_SIZE的選擇。由於元素數量是由一個size_t表示的，size_t的最大 值應該是2 ^ (CHAR_BIT * sizeof(size_t))，快速排序的理想「遞歸」深度是對元素總數 求對數，所以理想的「遞歸」深度是CHAR_BIT * sizeof(size_t)。雖然理論上最差情況下 「遞歸」深度會變成2 ^ (CHAR_BIT * sizeof(size_t))，但是一方面我們不需要從頭到尾 快速排序（區間足夠小時改用插入排序），另一方面，我們是在假設元素數量等於size_t的上 限...這都把內存給擠滿了=_=所以最後glibc決定直接採用理想「遞歸」深度作為棧大小上限。 接下來該進入qsort的正文了： */ void _quicksort (void *const pbase, size_t total_elems, size_t size, __compar_d_fn_t cmp, void *arg) { /* qsort實際上是通過調用這個_quicksort實現的。最後的arg是個workaround，用來搞定 qsort_r的。暫且不去理會。下面是一些準備工作： */ char *base_ptr = (char *) pbase; const size_t max_thresh = MAX_THRESH * size; if (total_elems == 0) return; /* 明確了對內存操作是以sizeof(char)為單位的。max_thresh實際上是改用插入排序時，維護 當前區間的兩個指針（類型均為char*）之間的距離。另外，如果元素數量為0，qsort啥也不 干，函數直接返回。 */ if (total_elems &> MAX_THRESH)
// 如果元素數大於終止區間（4個元素），則進行快速排序
{
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;

/*
這裡採用的是中值劃分，用於降低特定序列導致遞歸惡化影響。也就是說，對區間里的首元
素、中間元素和尾元素先進行排序。排序方式是...呃，是冒泡。反正也就3個元素嘛。
*/

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; 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; /* 和傳統的劃分方式不同，首先把中間當作鍵值在左側找到一個不小於mid的元素，右側找到一個 不大於mid的元素 */ 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; } /* 如果左右側找到的不是同一個元素，那就交換之。如果左右側任意一側已經達到mid，就把mid往 另一邊挪。因為鍵值已經被「丟」過去了。 */ else if (left_ptr == right_ptr) { left_ptr += size; right_ptr -= size; break; } } /* 如果左右側是同一元素，劃分其實已經大功告成了。 */ while (left_ptr &<= right_ptr); /* 接下來，將劃分出來的所有大於的終止區間的區間壓入棧準備下一次劃分，連這裡都會發生喪心 病狂的優化...不能浪費已經在棧里的原區間上下界=_= */ if ((size_t) (right_ptr - lo) &<= max_thresh) { if ((size_t) (hi - left_ptr) &<= max_thresh) POP (lo, hi); else lo = left_ptr; } else if ((size_t) (hi - left_ptr) &<= max_thresh) hi = right_ptr; else if ((right_ptr - lo) &> (hi - left_ptr))
{
PUSH (lo, right_ptr);
lo = left_ptr;
}
else
{
PUSH (left_ptr, hi);
hi = right_ptr;
}
}
}

/*
至此快速排序工作結束。
*/

#define min(x, y) ((x) &< (y) ? (x) : (y)) // 頭一回學宏「函數」都應該見過這貨吧 /* 接下來是插入排序 */ { /* 眾所周知，傳統的插入排序中每一趟插入（假設是向前插入），我們都會迭代有序區間，如果已 經迭代到了區間頭部，那就把該元素插在區間首部；否則如果前一個元素不大於待插入元素，則 插在該元素之後。 這種插入方式會導致每一次迭代要進行兩次比較：一次比較當前迭代位置與區間首部，一次比較 兩個元素大小。但事實上，我們可以用一個小技巧省掉前一次比較————插入排序開始前，先將容 器內最小元素放到容器首部，這樣就可以保證每趟插入你永遠不會迭代到區間首部，因為你總能 在中途找到一個不小於自己的元素。 注意，如果區間大於終止區間，搜索最小元素時我們不必遍歷整個區間，因為快速排序保證最小 元素一定被劃分到了第一個終止區間，也就是頭4個元素之內。 */ char *const end_ptr = base_ptr[size * (total_elems - 1)]; char *tmp_ptr = base_ptr; char *thresh = min(end_ptr, base_ptr + max_thresh); char *run_ptr; 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); /* 準備工作完畢，這下可以放心地幹掉迭代位置的比較了。 */ 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;
}
}
}
}
}

char *mid = lo + size * ((hi - lo) / size &>&> 1);

The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

The GNU C Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, see
&. */

/* If you consider tuning this algorithm, you should consult first:
Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */

#include &
#include & #include &
#include &

/* Byte-wise swap two items of size SIZE. */
#define SWAP(a, b, size)
do
{
size_t __size = (size);
char *__a = (a), *__b = (b);
do
{
char __tmp = *__a;
*__a++ = *__b;
*__b++ = __tmp;
} while (--__size &> 0);
} while (0)

/* Discontinue quicksort algorithm when partition gets below this size.
This particular magic number was chosen to work best on a Sun 4/260. */
#define MAX_THRESH 4

/* Stack node declarations used to store unfulfilled partition obligations. */
typedef struct
{
char *lo;
char *hi;
} stack_node;

/* The next 4 #defines implement a very fast in-line stack abstraction. */
/* The stack needs log (total_elements) entries (we could even subtract
log(MAX_THRESH)). Since total_elements has type size_t, we get as
upper bound for log (total_elements):
bits per byte (CHAR_BIT) * sizeof(size_t). */
#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
#define PUSH(low, high) ((void) ((top-&>lo = (low)), (top-&>hi = (high)), ++top))
#define POP(low, high) ((void) (--top, (low = top-&>lo), (high = top-&>hi)))
#define STACK_NOT_EMPTY (stack &< top) /* Order size using quicksort. This implementation incorporates four optimizations discussed in Sedgewick: 1. Non-recursive, using an explicit stack of pointer that store the next array partition to sort. To save time, this maximum amount of space required to store an array of SIZE_MAX is allocated on the stack. Assuming a 32-bit (64 bit) integer for size_t, this needs only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes). Pretty cheap, actually. 2. Chose the pivot element using a median-of-three decision tree. This reduces the probability of selecting a bad pivot value and eliminates certain extraneous comparisons. 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving insertion sort to order the MAX_THRESH items within each partition. This is a big win, since insertion sort is faster for small, mostly sorted array segments. 4. The larger of the two sub-partitions is always pushed onto the stack first, with the algorithm then concentrating on the smaller partition. This *guarantees* no more than log (total_elems) stack size is needed (actually O(1) in this case)! */ void _quicksort (void *const pbase, size_t total_elems, size_t size, __compar_d_fn_t cmp, void *arg) { 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); 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;