快速排序

重在递归的理解

算法步骤：
（1）：选取主元（数组中随机一个即可，为简化程序，以下选取数组开头为主元）；
（2）：小于等于主元的放左边，大于等于主元的放右边；
（3）：分别对左边，右边递归，即重复（1）（2）步。

void QuickSort(int array[], int left, int right)
{
    if (left >= right)
        return;

    int base = array[left];
    int i = left;
    int j = right;

    while (i < j)  // 小于等于主元的放左边，大于等于主元的放右边
    {
        while (i < j && array[j] >= base)
            j--;
        while (i < j && array[i] <= base)
            i++;
        swap(array[i], array[j]);
    }

    swap(array[left], array[i]);

    QuickSort(array, left, i - 1);  // 分别对左边，右边递归
    QuickSort(array, i + 1, right);
}

有必要对以上代码的细节方面作个说明：
（1）：递归结束条件

if (left >= right)
    return;

结束条件应该是大于等于，而不仅仅是等于。

考虑这样的情况：在一段区间中，取开头作为主元，很巧的是该区间除开头（即主元），其它所有的数都大于主元，于是分别对两边递归：

QuickSort(array, left, i - 1);
QuickSort(array, i + 1, right);

第一个函数的后两个参数： left 与 i - 1 ，前者大，后者小。
（2）：等于主元的数如何放置

while (i < j && array[j] >= base)
    j--;
while (i < j && array[i] <= base)
    i++;

本文的代码对等于主元的数采取的策略是：保持原位不动。

我们试着改变下代码：

while (i < j && array[j] > base)  // 去掉等号
    j--;
while (i < j && array[i] <= base)
    i++;

我们把等于主元的数全部移动到左边。这么做，程序依旧运行正常。

我们再试着改下代码：

while (i < j && array[j] > base)  // 去掉等号
    j--;
while (i < j && array[i] < base)  // 去掉等号
    i++;

左边等于主元的数移到右边，右边等于主元的数移到左边。

这样的做法有点诡异，似乎除了多了无用的交换操作耗时外，并不会对程序造成其它的影响。

但是请考虑这样的情况：

3 作为主元，i 和 j 指向的位置如上图，接着交换两个位置的值，

while (i < j)  
{
    while (i < j && array[j] > base)  // 去掉等号
        j--;
    while (i < j && array[i] < base)  // 去掉等号
        i++;
    swap(array[i], array[j]);  // 交换两值
}

程序会永远在这步进入死循环。

有的人提议：只要在 swap 后再加一句代码就行了嘛。如下：

while (i < j)  
{
    while (i < j && array[j] > base)  // 去掉等号
        j--;
    while (i < j && array[i] < base)  // 去掉等号
        i++;
    swap(array[i], array[j]);  // 交换两值
    i++; j++;  // 新增的代码
}
swap(array[left], array[i]);

但这么做，又引出了新的麻烦。

试想，若 i 的下一个位置就是 j（即 i+1 等于 j），在 i++; j++; 后，while 语句停止，swap 语句交换了主元和位置 i 的值，问题来了，i 指向的值或许是大于主元的，这就造成了程序的逻辑错误。

（3）：i 和 j 的操作顺序

while (i < j && array[j] >= base)
    j--;
while (i < j && array[i] <= base)
    i++;

为何 j 在前，i 在后？

其实这与我们选取的主元位置有关。程序中我们以数组首开头作为主元。

while (i < j)
{
    while (i < j && array[j] >= base)
        j--;
    while (i < j && array[i] <= base)
        i++;
    swap(array[i], array[j]);
}

swap(array[left], array[i]);

while 语句停止的条件正好是 i 等于 j，接下来交换主元与 array[i] ，值得我们注意的是， array[i] 被交换至左边，但它可以保证其值总是小于等于主元么？

简单推理之下，若我们让 j 先行，i 后走，就可以保证被交换前，其值总是小于等于主元的。反之，若误写了下面的代码，排序后的结果就会是错的。

while (i < j && array[i] <= base)  // i 在前
    i++;
while (i < j && array[j] >= base)  // j 在后
    j--;