一、快速排序的概念

​ 快速排序实现简单适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。快速排序引人注目得特点包括它是原地排序（只需要一个很小得辅助栈），且将长度为N的数组排序所需的时间和NlgN成正比。

​ 另外快速排序的内循环比大多数排序算法都要短小，这意味着它无论是在理论上还是在实际中都要更快。

​ 它的主要缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能。

二、基本算法

​ 快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。

​ 快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了

​ 在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后。在归并排序中，一个数组被等分为两半；在快速排序中，切分的位置取决于数组的内容。

三、代码实现

快速排序：

java">public class Quick {

    public static void sort(Comparable[] arr) {

        // 打乱数组的顺序
        Random rand = new Random(47);
        List list = Arrays.asList(arr);
        Collections.shuffle(list, rand);
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(Comparable[] arr, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(arr, lo, hi);
        sort(arr, lo, j - 1);
        sort(arr, j + 1, hi);
    }

    private static int partition(Comparable[] arr, int lo, int hi) {
        // 将数组切分成arr[lo...i-1]，a[i],a[i+1...hi]
        // 左右扫描指针
        int i = lo, j = hi + 1;
        // 切分元素
        Comparable v = arr[lo];
        while (true) {
            while (SortUtil.less(arr[++i], v)) {
                if (i == hi) {
                    break;
                }
            }
            while (SortUtil.less(v, arr[--j])) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
        }
        SortUtil.exch(arr, lo, j);
        return j;
    }
}

工具类：

java">public class SortUtil {

    // 对元素进行比较
    public static boolean less(Comparable v, Comparable w) {
        // 返回-1/0/1：表示v小于/等于/大于w
        return v.compareTo(w) < 0;
    }

    // 将元素交换位置
    public static void exch(Comparable[] arr, int i, int j) {
        Comparable t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // 展示数组
    public static void show(Comparable[] arr) {
        for (Comparable comparable : arr) {
            System.out.println(comparable + "");
        }
    }

    // 判断数组是否有序
    public static boolean isSorted(Comparable[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (less(arr[i], arr[i - 1])) {
                return false;
            }
        }
        return true;
    }
}

四、快速排序算法解析

​ 快速排序递归地将子数组a[lo…hi]排序，先用partition()方法将a[j]放到一个合适位置，然后再用递归将其他位置的元素排序。

引用《算法》(第四版)

​ 该方法的关键在于切分，这个过程使得数组满足下面三个条件：

​ 1、对于某个j，a[j]以及排定

​ 2、a[lo]到a[j-1]中的所有元素都不大于a[j]

​ 3、a[j+1]到a[hi]中的所有元素都不小于a[j]

​ 通过递归调用切分来排序，因为切分过程总是能排定一个元素，用归纳法不难证明递归能够正确地将数组排序：如果左子数组和右子数组都是有序的，那么由左子数组（有序且没有任何元素大于切分元素）、切分元素和右子数组（有序且没有任何元素小于切分元素）组成的结构数组也一定是有序的。

​ 要完成这个实现，需要实现切分方法。将数组随机打乱后，取a[lo]作为切分元素，然后从数组的左端开始向右扫描直到找到一个大于等于它的原始，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因此我们交换他们的位置。如此继续，就可以保证左指针的左侧元素都不大于切分元素，右指针j的右侧元素都不小于切分元素。当两个指针相遇时，只需要将切分元素a[lo]和左子数组最右侧的元素（a[j]）交换然后返回j即可。

五、快速排序算法的基本性质

​ 1、将长度为N的无重复数组排序，快速排序平均需要~2NlnN次比较（以及1/6的交换）。

​ 2、快速排序最多需要约N^2/2次比较，但随机打乱数组能预防这种情况。