简介

随机快排（以下简称快排），作为基于比较的排序算法之一，不仅具备高效的性能，还能大量的节省系统空间，在工程也有许多应用，比如在Java中，集合工具类Arrays，底层的实现就有使用到快排的思想，那么快排具体是怎么实现的呢？让我们一起去一步步去体会快排的思想，感受一下快排的魅力吧。

快排1.0版本

从一则问题谈起——荷兰国旗问题1.0：给你一个无序数组和一个给定值k，把不大于k的数放在数组的左边，大于k的数放在数组的右边。要求额外空间复杂度O(1)，如果没有这个硬性要求，直接申请一个辅助数组，与原数组等长，将原数组遍历一遍，不大于K的数从左往右依次填在辅助数组中，而大于K的数从右往左依次填在数组中，即可得到正确答案。

然而很明显，由于题目的硬性要求，上面的做法明显是不达标的。那么正确的流程是什么样的呢？我们先过流程，再过例子。

假设数组 arr[5,1,8,3,6] k=3，首先在脑海中想象数组有两个区域， <=k 的区域在左边，用指针lessEqual表示边界，>k 的区域（more区）在右边，开始时，指针lessEqual在-1位置（数组下标）上，然后我们从左往右遍历数组，假设当前遍历到的数为cur，cur与k进行比较，则有两种情况：

①当前数cur <= k,cur和lessEqual区的下一个数进行交换，lessEqual区向左扩，当前数跳下一个。

②当前数cur > k,当前数跳下一个。

比如当前来到0位置，在数组中arr[0] = 5, 5 > 3,命中情况②，cur直接跳下一个，来到1位置，arr[1] = 1,1 < 3,命中情况①，cur与<=K区域的下一个数进行交换，此时lessEqual在-1位置，lessEqual的下一个位置是 ++lessEqual = 0，所以 1 和 5 进行交换，1来 0 位置，5来到 1 位置，此时 arr[1,5,8,3,6] ,重复此过程直到数组遍历结束即可。在代码实现的过程中，对题目的输入用例进行了特殊的处理，但并不违反上述流程，具体代码如下:

// 数组arr，在L到R位置上，以arr[R]作为划分值
// <=arr[R]放左边  >arr[R]放右边
// 返回 <=k区的边界
public static int partition(int[] arr,int L,int R){
    if (L > R){
        return -1;
    }
    if (L == R){
        return L;
    }
    // 小于等于区域的边界
    int lessEqual = L - 1;
    // 当前位置的数
    int index = L;
    while (index < R){
        // 如果当前数不大于划分值
        if (arr[index] <= arr[R]){
            // 当前数和小于区域的下一个位置交换，当前数跳下一个
            swap(arr,index,++lessEqual);
        }
        index++;
    }
    // 使用arr[R]位置数作为划分值
    // 当while循环结束时，只是L到R-1位置上的数归位
    // 还剩下R位置的数，要记得归位
    swap(arr, ++lessEqual, R);
    return lessEqual;
}

// 可以考虑异或运算
public static void swap(int[] arr,int i,int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
复制代码

经过上述的partition过程，给定一个数组，开始时选数组的最后一个数作为划分值，我们可以得到一个边界，如果我们把这个边界作为分界线，将数组划分为两个部分，但是如果把划分出来的数组看做整体（可以把它想象成一个数），那么经过partition的调整，数组是不是在某种程度上具备一定的有序性了呢，只不过划分出来的数组内部不是有序的，那么我们只需对划分的数组也同样进行partition调整，重复此过程直到数组不可再分，那么我们最终是不是就可以得到一个有序的数组了呢？这就是快排1.0的版本。具体代码如下：

public static void quickSort1(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process1(arr, 0, arr.length - 1);
}

public static void process1(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int M = partition(arr, L, R);
    process1(arr, L, M - 1);
    process1(arr, M + 1, R);
}
复制代码

快排2.0版本

依旧是从荷兰国旗问题谈起，给定一个无序数组以及一个给定值k，请你做到数组中小于k的数放左边，等于k的数放中间，大于k的数放在右边，要求额外空间复杂度O(1)，跟上面1.0版本有点像，就是做了一次小升级，废话不多说暴力方法我们就不进行讨论了，直接上流程：

假设数组 arr[5,1,3,8,3] k=3，和上述流程类似，在脑海中想象数组有三个区域， <k 的区域在左边，用指针less表示边界，=k的区域在中间，>k 的区域在右边，用指针more表示边界，开始时，指针less在-1位置（数组下标）上，指针more在数组的最右位置上，然后我们从左往右遍历数组，假设当前遍历到的数为cur，cur与k进行比较，则有三种情况：

①当前数cur < k，当前数与less区的下一个数交换，less向左扩，当前数跳下一个。

②当前数cur = k，当前数直接跳下一个。

③当前数cur > k,当前数与more区的前一个数交换，more区向右扩，当前数不动（交换过来的数没看过）。

比如，当前来到0位置，less指针在-1位置，more指针在5位置，arr[0] = 5,5 > 3,命中情况③，5与more区的前一个数交换，即 –more = 4，既更新大于区的边界，同时算出需要交换的位置，5与arr[4]位置的数交换，当前数不动，arr更新为[3,1,3,8,5],此时当前数仍在0位置，arr[0] = 3,3=3,命中情况②，当前数直接跳下一个，来到1位置，arr[1] = 1,1<3,命中情况①，当前数与less区的下一个交换，即 ++less = 0，1与arr[0]位置的数交换，当前数跳下一个，此时arr更新为[1,3,3,8,5],继续遍历，根据命中情况调整数组，直到当前数的指针与大于区的边界（more指针）重合，流程结束。在代码实现的过程中，依旧对题目的输入用例进行了特殊的处理，但并不违反上述流程，具体代码如下:

// 在arr[L...R]上，玩荷兰国旗问题的划分，以arr[R]做划分值
// <arr[R]放左边  =arr[R]放中间  >arr[R]放右边
// 等于区的位置以数组的形式返回
public static int[] netherlandsFlag(int[] arr, int L, int R) {
    if (L > R) {
        return new int[]{-1, -1};
    }
    if (L == R) {
        return new int[]{L, R};
    }
    // 小于区边界
    int less = L - 1;
    // 大于区边界
    int more = R;
    int index = L;
    // 当前位置，不能和大于区域的左边界重合
    while (index < more) {
        if (arr[index] < arr[R]) {
            // 命中情况①的处理
            swap(arr, index++, ++less);
        } else if (arr[index] == arr[R]) {
            // 命中情况②的处理
            index++;
        } else {
            // 命中情况③的处理
            swap(arr, index, --more);
        }
    }
    // 还剩下arr[R]位置的数未归位
    // arr[R]位置的数与当前大于区域的边界位置上的数进行交换
    swap(arr, more, R);
    return new int[]{less + 1, more};
}
复制代码

经过netherlandsFlag过程进行划分，给定一个数组，选取数组的最后一个数作为划分值，我们可以将数组划分为三个区域，跟上述partition的流程相似，此时数组内的三个区域，如果把三个区域分别看作整体，数组在某种程度上是具备一定的有序性，只是划分出来的 <区 和 >区 的内部不是有序的，我们只需要在这两个区域再次进行netherlandsFlag划分，重复此过程直到数组不可再分，那么最终我们也可以得到一个有序的数组，这就是快排2.0的版本，具体代码如下：

public static void quickSort2(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process2(arr, 0, arr.length - 1);
}

public static void process2(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int[] equalArea = netherlandsFlag(arr, L, R);
    process2(arr, L, equalArea[0] - 1);
    process2(arr, equalArea[1] + 1, R);
}
复制代码

快排3.0版本

经过上面两个版本的快排算法代码实现，我们来讨论一下两版快排算法的时间复杂度，看到这里，相信大家会说快排的时间复杂度不是O(N *log N)吗？首先，快排的时间复杂度的确是O(N *log N)，但上述两个版本的快排算法的时间复杂度是O(N^2),这是为什么呢？因为估计一个算法的时间复杂度，要根据最差的数据状况去估计，要怎么理解呢？以上面两个版本的快排实现为例，给定一个数组，每次都是选取数组的最后一个数作为划分值，根据上述的流程，我们是希望选取划分值，经过调整之后，可以将数组划分为对应的区间，理想的情况是选取的划分值大小处在数组所有数的中间位置，每次调整之后都可以得到一个与原数组数据量相对而言，较小的数据范围，从而提速后续过程中的调整，而在相对极端的情况下，如果我们选取的划分值刚好是全部数据量中的极端值，比如在快排2.0版本中，给定数组[4,3,2,1]，每次选取数组的最后一个位置的数作为划分值去进行调整，每次调整后的数据量与前一次调整的数据量对比，呈现等差数列状态，所以上述两个版本的快排算法的时间复杂度是O(N^2)。

那么如何做到快排的时间复杂度是O(N *log N)呢？或者说上面两个版本的算法的不足之处在哪里呢？追究根源，就是在划分值的选取上，划分值取得好，算法的时间复杂度就好，划分值取得差，算法的时间复杂度就差，而算法的时间复杂度是具备稳定性的，这种情况要怎么去评估算法的时间复杂度呢？其实做法很简单，对于划分值的选取，我们把它随机化，把好情况和差情况随机化，最终通过数学的方法证明，把好情况和差情况随机，在数学的长期期望上，算法的时间复杂度就收敛于O(N *log N)，所以快排3.0，时间复杂度就是O(N *log N)。代码如下：

// 随机快排  最终版  时间复杂度：O(N *log N)
public static void quickSort3(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process3(arr, 0, arr.length - 1);
}

public static void process3(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    // 在 L...R 的范围上，随机选取一位和 arr[R] 进行交换
    // 目的：把好情况和差情况随机化
    swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
    int[] equalArea = netherlandsFlag(arr, L, R);
    process3(arr, L, equalArea[0] - 1);
    process3(arr, equalArea[1] + 1, R);
}
复制代码

// 随机快排 非递归版本
// 辅助类
// 记录处理哪个范围的排序
public static class Op {
    int l;
    int r;

    public Op(int left, int right) {
        l = left;
        r = right;
    }
}

public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int N = arr.length;
    // 在 L...R 的范围上，随机选取一位和 arr[R] 进行交换
    swap(arr, (int) (Math.random() * N), N - 1);
    int[] equalArea = netherlandsFlag(arr, 0, N - 1);
    int el = equalArea[0];
    int er = equalArea[1];
    // 申请栈用以记录调整的边界范围
    Stack<Op> stack = new Stack<>();
    stack.push(new Op(0, el - 1));
    stack.push(new Op(er + 1, N - 1));
    while (!stack.isEmpty()) {
        Op op = stack.pop();
        if (op.l < op.r) {
            // 在 L...R 的范围上，随机选取一位和 arr[R] 进行交换
            swap(arr, op.l + (int) (Math.random() * (op.r - op.l + 1)), op.r);
            equalArea = netherlandsFlag(arr, op.l, op.r);
            el = equalArea[0];
            er = equalArea[1];
            stack.push(new Op(op.l, el - 1));
            stack.push(new Op(er + 1, op.r));
        }
    }
}
复制代码