「快速排序算法」排序算法：快速排序

快速排序算法

概述

手写排序算法几乎是程序员面试必问的题目，大多数人都会选择写冒泡排序，如果此时你写的是其他改进过的排序算法，相信会让面试官眼前一亮。本文将介绍常见的排序算法中的“快速排序”。

基本思想

快速排序（QuickSort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：

从要排序的数据中取一个数为“基准数”。
通过一趟排序将要排序的数据分割成独立的两部分，其中左边的数据都比“基准数”小，右边的数据都比“基准数”大。
然后再按步骤2对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

该思想可以概括为：挖坑填数 + 分治法。

分治法

分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础，如快速排序，归并排序，傅立叶变换（快速傅立叶变换）等等。

例子

下面通过一个例子来看看快速排序是怎么工作的，例子中表格中红色的字体为需要填的坑，绿色的字体为已经移动过的数据。

1）刚开始，i 和 j 分别指向数组头和数组尾，即 i = 0，j = 9，基准数取第一个数，即 index = array[i] = array[0] = 23。

此时，array[0] 的值已经存在了index，因此 array[0] 的位置就好像被挖了个坑，可以填充一个数。

因此，我们从位置 j 开始向左寻找比 index 小的数，当 j = 8 时，符合条件，于是我们将 array[8] 的值填到 array[0] ，即将 9 填入 array[0]，并将 i 向右移动一个位置，即 i++。

从位置 j 向左寻找比 index 小的数，并在寻找到后填入坑中，用代码表示如下。

while (i < j && array[j] >= index) { // 向左寻找第一个小于index的数
    j--;
}
if (i < j) {
    array[i++] = array[j]; // 将array[j]填入array[i]，并将i向右移动
}

此时，array 数组如下图。

2）因为 array[0] 的坑被 array[8] 填了，于是 array[8] 的位置又成了一个新的坑。此时我们从位置 i 开始向右寻找比 index 大的数，当 i = 2 时符合条件，于是我们将 array[2] 的值填到 array[8] ，即将 37 填入 array[8]，并将 j 向左移动一个位置，即 j--。

从位置 i 向右寻找比 index 大的数，并在寻找到后填入坑中，用代码表示如下（跟上面相似）。

while (i < j && array[i] < index) {// 向右寻找第一个大于index的数
    i++;
}
if (i < j) {
    array[j--] = array[i]; // 将array[i]填入array[j]，并将j向左移动
}

此时，array 数组如下图。

以之后重复上述过程即可。

3）同样的，array[8] 的坑被 array[2] 填了，于是 array[2] 的位置又成了一个新的坑。此时我们从位置 j 开始向左寻找比 index 小的数，当 j = 5 时符合条件，于是我们将 array[5] 的值填到 array[2] ，即将 21 填入 array[2]，并将 i 向右移动一个位置，即 i++，此时 array 数组如下图。

4）同样的，array[2] 的坑被 array[5] 填了，于是 array[5] 的位置又成了一个新的坑。此时我们从位置 i 开始向右寻找比 index 大的数，当 i = 3 时符合条件，于是我们将 array[3] 的值填到 array[5] ，即将 89 填入 array[5]，并将 j 向左移动一个位置，即 j--，此时 array 数组如下图。

5）同样的，array[5] 的坑被 array[3] 填了，于是 array[3] 的位置又成了一个新的坑。此时我们从位置 j 开始向左寻找比 index 小的数，当 j = 4 时符合条件，于是我们将 array[4] 的值填到 array[3] ，即将 2 填入 array[3]，并将 i 向右移动一个位置，即 i++，此时 array 数组如下图。

6）此时，我们发现 i = j，结束遍历，并将index填入 array[4]，即将 23 填入 array[4]，此时 array 数组如下图。此时，array[4] 左边的数据全比 array[4] 小，而 array[4] 右边的数据全比 array[4] 大。

7）接下去，我们只需要对 array[4] 两边的数据分别在进行上面的操作即可（分治法），如下图。

分治的代码可以写成如下：

quickSort(array, low, i - 1); // 递归调用，分治
quickSort(array, i + 1, high); // 递归调用，分治

整合

根据以上步骤，稍微整理一下，可以得出快速排序的代码如下：

public class QuickSort {
    private static void quickSort(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }
        int i = low, j = high, index = array[i]; // 取最左边的数作为基准数
        while (i < j) {
            while (i < j && array[j] >= index) { // 向左寻找第一个小于index的数
                j--;
            }
            if (i < j) {
                array[i++] = array[j]; // 将array[j]填入array[i]，并将i向右移动
            }
            while (i < j && array[i] < index) {// 向右寻找第一个大于index的数
                i++;
            }
            if (i < j) {
                array[j--] = array[i]; // 将array[i]填入array[j]，并将j向左移动
            }
        }
        array[i] = index; // 将基准数填入最后的坑
        quickSort(array, low, i - 1); // 递归调用，分治
        quickSort(array, i + 1, high); // 递归调用，分治
    }

    public static void quickSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        quickSort(array, 0, array.length - 1);
    }
}

时间复杂度

最好情况的时间复杂度为O(nlogn)，过程比较复杂，就不在此赘述。

最差情况下每一次取到的数（基准数）都是当前要比较的数中的最大/最小值，在这种情况下，每次都只能得到比上一次少1个数的子序列（即要么全比基准数大，要么全比基准小），此时相当于一个冒泡排序，比较的次数 = (n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2，此时的时间复杂度为：O(n^2)。最差情况一般出现在：待排序的数据本身已经是正序或反序排好了。

使用场景

基本上在任何需要排序的场景都可以使用快速排序。虽然快速排序的最坏情况时间复杂度为O(n^2)，但是由于基本不会出现，因此可以放心的使用快速排序。在本人的电脑测试，100万的随机数字，快速排序大约耗时120毫秒。

最后

理解了快速排序的基本思想后，手写快速排序算法就变得没那么难了，只需要多练习几遍，相信在面试中手写快速排序算法便是小菜一碟。

排序算法：快速排序