快速排序的高效性依赖于一定的运气成分

↑这么讲其实不严谨。准确来讲，快速排序的高效性依赖于数学概率，且这里的数学概率可以保证——你的电脑在使用快速排序(正确实现的)给一组数据排序时，比插入排序或选择排序要低效的概率比你的电脑此时被闪电击中的概率还要低！

因其高效性，快速排序是当下应用最广泛的排序算法。

一种应用广泛的算法其效率居然是靠概率来保证的，听起来可能有点扯，到底是如何？下面且仔细道来。

正文

相比于归并排序，快速排序在保证高效的前提下并不需要那么多的辅助空间(线性级别)，这是它的一大优势。

快速排序的最基本算法思路到底是怎样？

快速排序的基本算法

与归并排序类似，快速排序的算法也是一种分而治之的思路。以数组为例，先将数组分成两个子数组，然后分别将两个子数组排序（是不又想到了递归）。与归并排序不同的是，归并排序将两个子数组排序后还需将两个子数组归并到一起，已使数组整体有序。快速排序与之不同，快速排序中给两个子数组排好序时，原始数组也就自然地整体有序了。

特别需要注意的是，快速排序的实现依赖于一个非常重要的切分操作。就是以一个元素(的正确位置)为基准，将原数组切分成两个待排序的子数组，子数组不包含这个切分位置(即不包含此位置上的元素，严格来讲原数组被分成了三个子数组！)，左边子数组的元素都不大于此元素的键值，右边子数组的元素都不小于此元素的键值。

这意味着什么？这意味着切分位置的元素已经呆在原数组整体有序时它该在的位置了！

所以说快速排序中给两个子数组排好序时，原始数组也就自然地整体有序了。

说这么多，用图片具象化展示下快速排序的过程：

OK 捋完了基本逻辑思路，下面直接上代码来看一种快速排序算法的经典实现。

快速排序的一种经典实现

基于递归的一种经典实现(Java 版本)：

/**
     * <p>为数组a 的 [start, end] 下标区间原地快速排序的递归实现</p>
     * @param a：待排序数组
     * @param start，排序区间起始下标
     * @param end，排序区间终止下标
     */
    public static void sortQuick(int[] a, int start, int end){
        if (end <= start){
            return;
        }
        int j = clip(a, start, end);//切分操作完成后，数组 a 的 j 位置已放着整体有序时正确的元素！
        sortQuick_(a, start, j - 1);//将切分位置左边的子数组排序
        sortQuick_(a, j + 1, end);//将切分位置右边的子数组排序
        //数组达到整体有序
    }


/**
     * <p>快速排序的切分操作，将数组 a 切分为 a[start, j - 1], a[j], [j + 1, end]，返回 j </p>
     * @param a：待切数组
     * @param start，起始下标
     * @param end，终止下标
     * @return j 切分点下标
     */
    public static int clip (int[] a, int start, int end){
        int i = start, j = end + 1;//左右两个扫描数组的指针
        int indexRandom = nextInt(start, end);//[start, end]区间里的一个随机位置
        exch(a, start, indexRandom);//将此随机位置的元素交换到a[start]
        int clip = a[start];//切分元素，取[start, end]区间里的一个随机位置
        while (true){
            //扫描左右两边，并在需要时交换元素
            while (a[++i] < clip){//扫描左边
                if (i == end){
                    break;
                }
            }
            while (a[--j] > clip){//扫描右边
                if (j == start){
                    break;
                }
            }
            if (i >= j){//此条件成立则表示已整体扫描完
                break;
            }
            //i < j 时，交换两个位置的元素
            exch(a, i, j);
        }
        exch(a, start, j);//将clip 放入正确位置 j
        //此时对于数组中的所有元素(键值)，已达成 a[start, j - 1] <= a[j] <= a[j + 1, end]
        return j;
    }


/**
     * <p>返回 min <= 随机数 <= max 的随机整数数</p>
     * @param min：min
     * @param max：max
     * @return int i：指定闭区间内的随机数
     */
    public static int nextInt(int min, int max){
        return min + (int)(Math.random() * (max-min+1));
    }

以上代码中最关键的是 clip 方法，最难理解的也是 clip 方法。

其实可以这么理解，每次进行的切分操作都能为原数组排定一个元素(就是那个用来切分的元素)，因为该元素左边的元素(组成的子数组)都不大于它，而右边的元素(组成的子数组)都不小于它，所以此切分元素肯定已经在(原数组整体有序时)它该在的位置了。此时如果我们把切分的左子数组和右子数组都接着排好序那么原数组便达到了整体有序！clip 方法中的两个指针（i 和 j）相遇时我们将切分元素 a[start] 和当前左子数组最右边一个元素（a[j]）交换然后返回 j 即可。两个指针 i 和 j 会在什么时候相遇呢？只会有两种情况：

i > j 或者 i == j

这点不难自行归纳证明。

另一种更简洁的实现

其实我们可以在思维层面更进一步，上面的实现我们在 clip 操作里其实是把原数组分成了三个子数组，左子数组，切分的中间元素（中间数组？），和右子数组。

必须要有这个中间元素吗？我写完上面的代码后忽然觉得没有这个中间元素好像完全没问题，甚至能让我们的代码更简洁！

快速排序是一种分而治之的算法，上面我们是把原数组分成了三部分，左子数组，切分的中间元素（已在数组整体有序时它该在的位置），右子数组。原问题确实分成了两个更小的子问题（此时把左右数组排好序原数组就整体有序了），这就叫分而治之。从逻辑上来分析，没有中间元素，就单纯的把原数组分成左右两个子数组，只要右子数组里的元素都不小于左子数组里面的元素，把这两个子数组排好序后原数组同样能达到整体有序。这确实是一种更精简的思路，直接来看下实现代码：

/**
     * <p>为数组a 的 [start, end] 下标区间原地快速排序的非递归实现</p>
     * @param a：待排序数组
     * @param start，排序区间起始下标
     * @param end，排序区间终止下标
     */
    public static void sortQuick(int[] a, int start, int end){
        if (start >= end){
            return;
        }
        //遍历数组的两个指针，和用于切分数组的元素 clip，此方法将数组 a 切分成两个纯粹的左右子数组，无多余的中间元素
        int i = start, j = end, clip = a[nextInt(start, end)];
        while (i <= j){
            while (a[i] < clip){
                i++;
            }
            while (a[j] > clip){
                j--;
            }
            if (i < j){
                exch(a, i, j);
                i++;
                j--;
            }else if (i == j){
                i++;//或者j--
            }
        }
        /**
         * ↑捋一下逻辑，上面的循环走完后，j 刚刚比 i 大一
         */
        sortQuick(a, start, j);//将左边的子数组排序
        sortQuick(a, i, end);//将右边的子数组排序
        //数组达到整体有序
    }

/**
     * <p>返回 min <= 随机数 <= max  的随机整数数</p>
     * @param min：min
     * @param max：max
     * @return int i：指定闭区间内的随机数
     */
    public static int nextInt(int min, int max){
        return min + (int)(Math.random() * (max-min+1));
    }

确实更简洁了~

小结

快速排序的理想情况是每次都刚好将数组对半切分，这样算法运行起来最高效(成本最低)。想要每次都让切分元素都刚好落在数组中间是很难做到的。快速排序实现的一大暗坑就是在切分不平衡时算法可能会极为低效，比如第一次从数组中最小的元素开始切分，第二次从第二小的元素开始切分……这会导致一个大数组需要被切分太多次。不过我们上面实现的代码能做到平均而言切分元素都在数组中间，我们随机选择切分元素的操作就是为使产生糟糕切分的可能性降到很低，尽力避免上述弊端。

总结

以上所述乃是最基本的快速排序，读者还需好好消化吸收一下。快速排序的平均时间复杂度为线性对数级别的 O(n log n)，所需的空间复杂度根据具体实现的不同加以区别，如我们上述的实现只需常数级别的辅助空间。特别注意对于不好的实现，快速排序最坏需要平方级别的时间复杂度。

上述分析其实不够立体，对于一些典型用例，快速排序是要比我们之前文章里讨论的排序算法都要快的，这点读者不妨自己写些测试用例实际跑跑对比看看其他排序算法。

当然以上所述只是最基本的快速排序，其还有很大改进空间，例如针对含有大量重复元素数组优化的三向切分的快速排序算法。针对基本快速排序算法的改进暂不在本文讨论范围，以后有机会可以单发篇文章好好聊聊此方面。

系列文章至此，主流几种排序算法已全部讲完，下篇聊啥呢？