快速排序

算法描述

像归并排序一样，快速排序也是一种分治的递归算法。经典快速排序，输入存放在数组里，且算法不产生额外的数组。将数组S排序的基本算法由下列简单的四步组成：

1. 如果数组S中的元素个数是0或者1，则返回。
2. 取S中任意一元素v，称之为枢纽元（pivot）。
3. 将（S中其余元素）划分成两个不相交的集合：和。
4. 依次返回，，
   步骤的示意图如下：
   快速排序的各步骤
   选取枢纽元
   这里介绍三种方法。
   I. 一种常见但不好的方法
   通常的、无知的选择是将第一个元素用作枢纽元。如果待排数组的元素是随机的，那么可以接受，而如果输入时预排序的或是反序的，那么这样的枢纽元会产生一个劣质的分割，即所有的元素要么被划入S1，要么被划入S2.更糟糕的是这种情况毫无例外的会发生在所有的递归中。这种最坏情形下的性能为O(N2) 。
   II. 一种安全的做法
   随机选取枢纽元。这种方法是安全的，因为随机的枢纽元不可能接连不断的产生劣质的分割。另一方面，随机数的生成开销一般很大，根本减少不了算法其余部分的平均运行时间
   III.三数中值分割法（Median-of-Three Partitioning）
   一般的做法是使用左端、右端、和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的坏情况，并且实际减少了14%的比较次数。
   分割策略
   在分割阶段要做的就是把所有严格小于枢纽元的元素移到数组的左边，而把所有严格大于枢纽元的元素移到数组的右边，如果数组中有其他与枢纽元相等的元素，可保持位置不变即可。每一趟分割之后，枢纽元都会处在正确的位置上。示意图如下：
   
   首先将枢纽元与最后位置的元素交换。然后i从第一个元素开始向后遍历，j从最后一个元素开始向前遍历（i先遍历，j再遍历）。当i在j的左边时，我们将i右移，移过那些小于等于枢纽元的元素；并将j右移，移过那些大于等于枢纽元的元素。当i和j停止时，如果i在j的左边，那么将这两个元素交换，其效果就是将一个大元素推向右边，而把一个小元素推向左边。当i和j相遇时，停止移动，此时相遇的位置就是枢纽元在数组中的正确位置，所以最后将枢纽元与相遇位置上的元素进行交换。
   解释一下为什么首先将枢纽元与最后位置的元素交换：因为i先于j遍历的缘故，最后i和j相遇的位置上的元素，一定是大于枢纽元的（无论是i遇上j，还是j遇上i）。而大于枢纽元的元素应该落在数组的右边，所以我们先将枢纽元提前放置在了最后。
   同理可得，如果j先于i遍历，那么最后相遇的位置上的元素必定比枢纽元小，那么这种情况下就不需要提前将枢纽元与最后位置的元素交换了。

代码

选取第一个元素作为枢纽元的代码如下，其中需要注意的点是比较nums[i]或者nums[j]与pivot的大小时，必须加上等号，否则当nums[i]=nums[j]=pivot时，i++和j--永远无法执行到，导致程序就会陷入无限循环，跳不出for(;;)。

    public void quickSort(int[] nums, int left, int right) {
        if(left >= right){
            return;
        }

        // 选取第一个数作为枢纽元(若选取最后一个数作为枢纽元,就不需要交换位置）
        int pivot = nums[left];
        swapReferences(nums, left, right);

        // j必须从right开始, 保证了当枢纽元是最大的数时的正确性
        int i = left, j = right;

        while (true) {
            // <= 保证当 nums[i] = nums[j] = pivot时, 程序不会陷入无限循环
            while (i < j && nums[i] <= pivot) {
                i++;
            }
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                swapReferences(nums, i, j);
            } else {
                break;
            }
        }

        // restore pivot
        swapReferences(nums, i, right);

        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

通过三数中值分割法的程序如下：

    public void quickSort(int[] nums, int left, int right) {
        if(left >= right){
            return;
        }

        int pivot = median3(nums, left, right);

        int i = left, j = right - 1;

        while (true) {
            while (i < j && nums[i] <= pivot) {
                i++;
            }
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                swapReferences(nums, i, j);
            } else {
                break;
            }
        }

        // restore pivot
        swapReferences(nums, i, right - 1);

        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

    /**
     * 三数中值分割法选取枢纽元(pivot):
     * 对left, center, right三个位置的数进行排序, 枢纽元选取center位置的数
     * 并且将枢纽元放在right-1位置, 这样只需排序(left, right-1)区间的数
     */
    private static int median3(int[] nums, int left, int right) {

        // 将left, center, right三个元素排序
        int center = (left + right) / 2;
        if (nums[center] < nums[left]) {
            swapReferences(nums, left, center);
        }
        if (nums[right] < nums[left]) {
            swapReferences(nums, left, right);
        }
        if (nums[right] < nums[center]) {
            swapReferences(nums, center, right);
        }

        // 选取center元素作为枢纽元(pivot), 并将枢纽元放置在right-1位置
        swapReferences(nums, center, right - 1);
        return nums[right - 1];
    }

算法分析

正如归并排序那样，快速排序也是递归的，因此它的分析需要求解一个递推公式。快速排序的运行时间等于两个递归调用的时间加上花费在分割上的线性时间。我们得到基本的时间复杂度递推关系式其中i是S1集合中的元素的个数。我们将考察三种情况。

最坏情况的分析
枢纽元始终是最小元素。此时，我们忽略无关紧要的，那么递推关系为,求解上面的递推方程（依次用N-1代替N得到众多方程，然后相加所有方程）可以得到

最好情况的分析
在最好的情况下，枢纽元正好位于中间。为了简化数学推导，我们假设两个子数组恰好各为原数组的一般大小，那么递推关系为,求解上面的递推方程(左右两边同除N，依次用N/2代替N得到众多方程，然后相加所有方程)可以得到

平均情况的分析
这是最困难的部分。假设和的平均值为，那么递推关系为，最后解得（过程略）