2013-07-02 22:28:40

转自：http://www.programfan.com/blog/article.asp?id=14298

　　正如大家所知道的，快速排序算法是现在作为数据排序中很常用的算法，它集成在ANSI C的函数库中。我们经常使用快速排序，就是调用qsort函数，那么qsort函数里面到底是怎么实现的呢？我们现在就来看一看。

　　在这个系列的文章中，我们主要研究一下ANSI C的库函数qsort的源代码，并给出它的性能特性分析。其中使用的源代码是VS.net 2003中VC++自带的源代码，大家可以在X:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\crt\src文件夹中找到这个名为qsort.c的文件。其他C/C++编程环境也有这个文件，只是在实现上面就可能有些差异而已。

    这篇文章先对qsort.c文件中的注释进行翻译，并在适当的时候进行一些分析工作。

    快速排序是一个递归的过程，每次处理一个数列的时候，就从数列中选出一个数，作为划分值，然后在这个数列中，比划分值小的数移动到划分值的左边，比划分值大的数移动到划分值的右边。经过一次这样的处理之后，这个数在最终的已排序的数列的位置就确定了。然后我们把比这个数小和比这个数大的数分别当成两个子数列调用下一次递归，最终获得一个排好序的数列。上面介绍的是基本快速排序的方法，每次把数组分成两分和中间的一个划分值，而对于有多个重复值的数组来说，基本排序的效率较低。集成在C语言库函数里面的的qsort函数，使用三路划分的方法解决这个问题。所谓三路划分，是指把数组划分成小于划分值，等于划分值和大于划分值的三个部分。

    下面我们开始分析源代码，在源代码中的解释以注释的形式出现：

/****qsort.c - quicksort algorithm; qsort() library function for sorting arrays**       Copyright (c) Microsoft Corporation. All rights reserved.**Purpose:*       To implement the qsort() routine for sorting arrays.******************************************************************************

**/

#include #include #include #include 

/* 加快运行速度的优化选项 */#pragma optimize("t", on)

/* 函数原型*/static void __cdecl shortsort(char *lo, char *hi, size_t width,                int (__cdecl *comp)(const void *, const void *));static void __cdecl swap(char *p, char *q, size_t width);

/* this parameter defines the cutoff between using quick sort and   insertion sort for arrays; arrays with lengths shorter or equal to the   below value use insertion sort */

/* 这个参数定义的作用是，当快速排序的循环中遇到大小小于CUTOFF的数组时，就使用插入

排序来进行排序，这样就避免了对小数组继续拆分而带来的额外开销。这里的取值8，是

经过测试以后能够时快速排序算法达到最快的CUTOFF的值。*/

#define CUTOFF 8            /* testing shows that this is good value */

/* 源代码中这里是qsort的代码，但是我觉得先解释了qsort要调用的函数的功能比较

好。

    shortsort函数：

    这个函数的作用，上面已经有提到。就是当对快速排序递归调用的时候，如果遇到

大小小于CUTOFF的数组，就调用这个函数来进行排序，而不是继续拆分数组进入下一层

递归。因为虽然这里用的是基本排序方法，它的运行时间和O(n^2)成比例，但是如果是

只有8个元素，它的速度比需要递归的快速排序要快得多。另外，在源代码的注释中，说

这是一个插入排序(insertion sort)，但是我觉得这个应该是一个选择排序才对

(selection sort)。至于为什么用选择排序而不用插入排序，应该是和选择排序的元素

交换次数少有关系，只需要N-1次交换，而插入排序平均需要(N^2)/2次。之所以要选择

交换次数少的算法，是因为有可能数组里面的单个元素的大小很大，使得交换成为最主

要的性能瓶颈。

    参数说明：

       char *lo;    指向要排序的子数组的第一个元素的指针

       char *hi;    指向要排序的子数组的最后一个元素的指针

       size_t width;  数组中单个元素的大小

       int (__cdecl *comp)(const void *,const void *);   用来比较两个元素大

小的函数指针，这个函数是你在调用qsort的时候传入的参数，当前一个指针指向的元素

小于后一个时，返回负数；当相等时，返回0；当大于时，返回正数。*/

static void __cdecl shortsort (    char *lo,    char *hi,    size_t width,    int (__cdecl *comp)(const void *, const void *)    ){    char *p, *max;

    /* Note: in assertions below, i and j are alway inside original bound of       array to sort. */

    while (hi > lo) {        /* A[i] 0) {            swap(lo, hi, width);        }        if (comp(mid, hi) > 0) {            swap(mid, hi, width);        }

        /* We now wish to partition the array into three pieces, one

consisting           of elements than it.  This is done           below; comments indicate conditions established at every step. */

        /*下面要把数组分区成三块，一块是小于分区项的，一块是等于分区项的，而

另一块是大于分区项的。*/

       /*这里初始化的loguy 和 higuy两个指针，是在循环中用于移动来指示需要交换的两个元素的。higuy递减，loguy递增，所以下面的for循环总是可以终止。*/

        loguy = lo;        higuy = hi;

        /* Note that higuy decreases and loguy increases on every iteration,           so loop must terminate. */        for (;;) {            /* lo mid && comp(higuy, mid) == 0);        }        if (mid >= higuy) {            do  {                higuy -= width;            } while (higuy > lo && comp(higuy, mid) == 0);        }

        /* OK, now we have the following:              higuy < loguy              lo