排序（2）：快速排序

快速排序本身不难，对于初学者，难就难在递归的理解。

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

void QuickSort(int array[], int left, int right)
{
    int i = left;
    int j = right;
    int base = array[left];

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

        if (i <= j)
        {
            swap(array[i], array[j]);
            i++;
            j--;
        }
    }

    if (left < j)
        QuickSort(array, left, j);
    if (i < right)
        QuickSort(array, i, right);
}

一：算法复杂度

最好的情况，每次我们运行一次分区，我们会把一个数组分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数组。则会有关系式：

$$T(n)=2T(\\frac n2)+O(n)$$

解出$T_{best}(n)=O(nlogn)$。

最坏的情况，在分割后，两子数组总是拥有各为1和n-1长度的数组，则递归关系式变为：

$$T(n)=T(n-1)+O(n)+O(1)=T(n-1)+O(n)$$

解出$T_{worst}(n)=O(n^2)$。

二：细节讨论

（1）：如何选择主元

本文的代码很简单，以数组首元素作为主元。但我们知道主元的大小直接决定快排的效率，因为数组的划分需要依靠主元，理想状态下，给定的主元正好可以把数组分为长度相等的两个子数组，但找到并确定这样的主元还需要耗费额外的时间，如此一来，得不偿失。

因此现实生活中，我们更多的采取"三点中值"，即数组首元素，尾元素和中间元素这三个元素的中位数作为主元。

（2）：等于主元的数如何放置

左右扫描，如果遇到和主元相等的元素怎么办？是暂停扫描（然后交换）还是继续扫描？

首先，两个方向采取的策略应该是一样的，也就是要么都暂停（然后交换），要么都继续扫描。否则将导致两个子数组不平衡。

其次，为了更好分析这个问题，我们不妨考虑所有元素都相同的情形。如果我们遇到和主元相等的时候不停止，那么从左到右扫描时，两指针将相遇，此次过程结束。结果呢？什么都没做，却得到了两个大小极其不均衡的数组。算法时间复杂度为$O(n^2)$。如果我们选择遇到相等元素时停止扫描，然后交换，那么虽然看上去交换的次数变多了，但是我们将得到大小相等（或者差1）的两个子数组，算法的时间复杂度为$O(nlogn)$。

因此，遇到和主元相等的元素时候我们都暂停扫描，交换元素后继续，直到指针相遇或者交叉。（摘自深入解析快速排序）

（3）：i <= j 的等号可以去掉么

不可以！

我们先来看下代码的结尾，

if (left < j)
    QuickSort(array, left, j);
if (i < right)
    QuickSort(array, i, right);

从上面的代码可以看出，当while循环结束，i需指向左子数组的尾元素，j需指向右子数组的首元素，但两者不能重合，因为一旦重合，子数组的递归就可能会打乱它们的排序。

（4）：分割划分策略

本文所采用的划分策略很简单，易于理解，实际应用中，要复杂的多，有兴趣的朋友可以参见这里。