在阅读这篇博客之前请确保您已经理解了快速排序的思想。
qsort函数位于GLIBC的stdlib目录下，内部实现了快速排序的功能，我们先不去管这个函数内部具体是怎么实现的，先来考虑如果我们要调用它，该怎么去调用呢。很显然，我们需要给它传入一个待排序的数组array，由于C语言会将数组参数转为指针，所以很自然地要传入一个数组长度的值，一般表示数组长度就是arraySize。看起来没什么问题，那我们来看一下它对外封装的接口是不是如我们所想呢。
看来我们的考虑还是欠佳，封装的接口有四个参数，除了传入的数组以外还要传入数组个数，每个元素的大小和一个比较函数。比较函数还是很容易理解的，因为我们毕竟不能保证始终要求它给我们升序排列，也不能保证随便什么内容都要求程序可以不出错的给我们排好序。但是为什么传入数组大小的时候必须要分开传参呢，我们自己写函数的时候也是只传了一个参数表示数组长度的呀。在分析原因之前我们先按照提供的接口简单测试一个例子吧。
#include <stdio.h>
#include <stdlib.h>
int Cmp(const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int main()
{
int n;
int values[] = { 2, 5, 4, 1, 3 };
printf("排序之前的列表：\n");
for( n = 0 ; n < 5; n++ ) {
printf("%d ", values[n]);
}
qsort(values, 5, sizeof(int), Cmp);
printf("\n排序之后的列表：\n");
for( n = 0 ; n < 5; n++ ) {
printf("%d ", values[n]);
}
return(0);
}
排序的结果如下图，
看来确实得用官方给的方式来调用，那为什么要分两次传数组的长度呢，比较函数又是怎么用的呢，这就需要我们从源码中找答案了，首先我们看下面的代码实现，
void _quicksort (void *const pbase, size_t total_elems, size_t size,
__compar_d_fn_t cmp, void *arg)
这是里面的函数封装，可以看到pbase是void类型的，也就是说程序不知道我们给它的数组是什么类型，那它就只能通过指针和我们给它类型的长度来遍历元素了，这也是为什么要分数组元素个数和数组中每个元素的大小来传参了。我们平时自己封装的函数都是已知类型的，所以就只需要传一个参数就可以了。我们看下面的代码块中left_ptr = lo + size;和right_ptr = hi - size;就是通过这种方式来实现元素转移的。同时我们还注意到const只修饰了pbase指针，也就是说pbase指针指向不能改，但指向的值是可以修改的。
/* 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;
我们再观察上面的代码，发现给它传入的比较函数cmp也派上用场了，并且用函数指针的方式来调用它。因为我们事实上传给qsort的就是一个函数指针，在最开始的例子中，我们调用qsort的方式是 qsort(values, 5, sizeof(int), Cmp)，用的是Cmp而不是Cmp()，当然后者表示函数调用，如果成功将会返回一个返回值类型的数。关于函数指针的更详细解释可以参考菜鸟教程 。
我们继续分析这个调用的过程，下面这行代码传入的参数类型一律被强转成了void类型的指针，而我们根据前面的分析知道这里的参数类型实际上是Cmp()函数的参数。也就是说我们最开始在编写Cmp()函数的参数类型的时候就要把它设定为void *。
if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
到这里我们已经了解了整个函数参数的功能和意义，下面来看一下具体算法的实现吧。这里只列出关键代码，详细信息请参阅官方网站 。可以看到官方用的是do-while的方式使得pivot位置左边的值都比它小，右边的值都比它大。然后是用栈的方式来划分下一次迭代时左右指针的位置的。
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;
}
}
}
最后值得注意的是，一旦 BASE_PTR 数组被快速排序部分排序，其余部分则是完全使用插入排序来进行排序的。以上就是qsort的大致实现，主要是从使用者的角度向大家分享的，所以并不涉及到太多实现的细节，如果对这方面感兴趣，推荐您去查阅官方文档或者阅读源码。
因为我接触C语言的时间也不长，难免其中会有很多错误，欢迎大家指出文中的错误，好让我们共同进步！！
Last modified on 2022-04-30