Robbie Mosaic's Web Log

• 

快速排序算法是一个常用的排序算法。一般来说，该算法的写法如下：

void QuickSort(int *pData, int left, int right)
{
    int i, j;
    int middle, iTemp;
    i = left;
    j = right;

    middle = pData[(left + right) / 2]; //求中间值
    do
    {
        while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数
            i++;
        while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数
            j–;
        if (i <= j) //找到了一对值
        {
            //交换
            iTemp = pData[i];
            pData[i] = pData[j];
            pData[j] = iTemp;
            i++;
            j–;
        }
    } while (i <= j) ; //如果两边扫描的下标交错，就停止（完成一次）

    //当左边部分有值(left<j)，递归左半边

    if(left<j)
        QuickSort (pData,left,j);
    //当右边部分有值(right>i)，递归右半边
    if(right>i)
        QuickSort (pData,i,right);
}

另外，我自己有一次写该算法，写了半天没有写出来，后来想出来一个写法，如下，本质上也是快速排序，只是该算法不断地交换了一个 pivot。一般的算法是不针对 pivot 进行交换的，即被交换的两个元素可以都不是 pivot。我这里交换 pivot 的用意是：每次左右分割完成后把该 pivot 左边和该 pivot 右边的剩余元素再作分割，该 pivot 自己就可以不用再分割，那么可以每次都保证至少减少一个需要分割的元素。

void quick_sort(void *array, size_t length, size_t size, QsortCompareFunc compare)
{
    void *pivot;
    void *left;
    void *right;
    if (length < 2) {
        return;
    }
    pivot = get_middle_elem_ptr(array, length, size, compare);
    left = array;
    right = (char *)array + (length – 1) * size;
    swap_elem(left, pivot, size);
    /* now left is a pivot */
    while (true) {
        while (left < right) {
            if (compare(right, left) <= 0) {
                break;
            }
            right = (char *)right – size;
        }
        if (left >= right) {
            break;
        }
        if (compare(left, right) == 0) {
            /* both left and right are pivots */
            left = (char *)left + size;
        } else {
            /* right is smaller */
            swap_elem(left, right, size);
        }
        while (left < right) {
            if (compare(left, right) >= 0) {
                break;
            }
            left = (char *)left + size;
        }
        if (left >= right) {
            break;
        }
        if (compare(left, right) == 0) {
            /* both left and right are pivots */
            right = (char *)right – size;
        } else {
            swap_elem(left, right, size);
        }
    }
    /* sort the left half from array to left – size */
    quick_sort(array, ((char *)left – (char *)array) / size, size, compare);
    /* sort the right half from left + size to end of array */
    quick_sort((char *)left + size,
        length – ((char *)left – (char *)array) / size – 1,
        size, compare);
}

但是，上面第一个算法，它在分割完成后，也可以保证每次至少减少一个元素，这是因为它让 i > j 再跳出的，而且剩下要分割的是 >= i 和 <= j 的元素。不过这样一来，如果使用 size_t 作为 length 的类型，则必须在父函数中先判断是否 j > left，否则如果 j < left，把 j – left 转成 size_t 类型的整数后会变成负数。我的算法是“碰巧”不需要这个判断，因为跳出循环的条件是 i <= j（或者说是 left <= right，如果看实际程序的话）。

    if(left<j)
        QuickSort (pData,left,j);
    //当右边部分有值(right>i)，递归右半边

需要注意的是，两个算法都采用了主动交换并移进的法则。第二个算法中：

        while (left < right) {
            if (compare(right, left) <= 0) { /* 注意这一句 */
                break;
            }
            right = (char *)right – size;
        }

和第一个算法中：

        while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数
            i++;

都有这样的现象：compare(right, left) <= 0，而不是 compare(right, left) < 0，在第一个算法中是 pData[i] < middle，而不是 pData[i] <= middle。也就是，跳出循环的条件比较弱，比较容易跳出这个循环，只要遇到 pivot 就会跳出该循环。

我一开始以为，这样写可能是个凑巧。但是后来经历过一次失败以后发现，这样写不仅仅是巧合，而且是必要的。

为什么呢？我测试过一组数：0 ~ 9 随机抽取 100000 次，然后快速排序。pivot 是随机选的。结果，如果跳出循环的条件比较强，即遇到 pivot 不跳出，就很容易栈溢出。

为什么会栈溢出？嵌套太深。为什么嵌套太深？仔细想想……啊，原来如此啊！当数字比较有序了以后，可能子数组里面的数也就两三个不同的值，比如 1、2 和 3。而且其中有一个值出现得比较多，比如说 2。然后它被选作 pivot 的可能性就比较大。之后，由于遇到 2 并不跳出循环，结果就会停在 1 和 3 出现的那些位置中可能比较中间，也可能比较偏的地方。但是 1 和 3 本来就少，结果是再次分割时，一半只有 1 和 2，一半只有 2 和 3。然后再分割的时候，1 又更少了，2 还是容易被选作 pivot，于是位置就越来越偏。当 1 完全没有了的时候，每次左边就只有一个 2，右边就有剩下全部的 2，这样下去，结果就嵌套太深了。

如果遇到 pivot 停下，然后交换，这样会在数字比较单一的时候跑得更接近中间的位置，就不大会引起嵌套太深这种情况了。