快排是一个较为常见的排序算法

快排的思路

有一个乱序的数组

[2 , 3 , 1 , 6 , 4 , 7 , 8 , 9 , 5]

首先以这个数组的最后一个数5进行分开，将这个数组进行成一个分块处理，第一部分是小于5，中间是等于5，后面是大于5。在三个区间内数字可以是无序的。

我们先不关心如何实现这个操作，假设这个操作可以实现。将这个操作作为一个基本操作

那么现在数组将会变为

[2 , 3 , 1 , 4 , 5 , 8 , 9 , 6 , 7]

再将5之前的4位数再进行一次基础操作，5之后也进行一次基础操作

[2 , 3 , 1 , 4 , 5 , 6 , 7 , 8 , 9]

如此递归进行下去，如果数组只有3位，那么它进行一次基础操作之后，它必将有序

那么重点就是这个基础操作如何实现

基础操作的实现

我们现在的目标是将按数组最后一个数将一个数组分为三个区域。

我们设定四个规则

还是这个数组[2 , 3 , 1 , 6 , 4 , 7 , 8 , 9 , 5]，小于区用红色标记，大于区用绿色标记

当前数从下标0开始，2<5，小于区的下一个就是下标0，无需交换，下标调下一个

[2 , 3 , 1 , 6 , 4 , 7 , 8 , 9 , 5]

下标1，3<5，与小于区下一个交换，跳下一个

[2 , 3 , 1 , 6 , 4 , 7 , 8 , 9 , 5]

下标2，1<5，与小于区下一个交换，跳下一个

[2 , 3 , 1 , 6 , 4 , 7 , 8 , 9 , 5]

下标3，6>5，与大于区上一个交换，下标不动

[2 , 3 , 1 , 9 , 4 , 7 , 8 , 6 , 5]

下标3，9>5，与大于区上一个交换，下标不动

[2 , 3 , 1 , 8 , 4 , 7 , 9 , 6 , 5]

下标3，8>5，与大于区上一个交换，下标不动

[2 , 3 , 1 , 7 , 4 , 8 , 9 , 6 , 5]

下标3，7>5，与大于区上一个交换，下标不动

[2 , 3 , 1 , 4 , 7 , 8 , 9 , 6 , 5]

下标3，4<5，与小于区下一个交换，跳下一个

[2 , 3 , 1 , 4 , 7 , 8 , 9 , 6 , 5]

大于区与小于区相遇时，最后一个数与大于区第一个数交换

[2 , 3 , 1 , 4 , 5 , 8 , 9 , 6 , 7]

可能会觉得这个与小于区下一个进行交换是多余的，但事实是并不多余，假如有多个相同的数字触发等于的操作，就会出错

比如

[2 , 3 , 1 , 2]

下标为0，进行不交换的操作，下标往后调

[2 , 3 , 1 , 2]

下标为1，3>2，与大于区上一个交换，下标不动

[2 , 1 , 3 , 2]

下标为1，1<2，不交换的话，跳下一个，小于区右扩，那么小于与大于就相碰了

进行完结束操作，交换2与3，那么操作就结束了

如果交换，小于区的下一个为2，当前为1，交换一下就可以将1调回小于区

代码实现

这个基础操作传入三个参数，一个数组，一个需要进行操作的左端点，进行操作的右端点

public static int[] partition(int[] arr, int L, int R)

我们还需要三个变量

一个作为行走的下标index

一个作为小于区的最右端lessR

一个作为大于区的最左端moreL

public static int[] partition(int[] arr, int L, int R) 

按照上述的操作前三个规则走完的终结是index碰到了moreL。、

然后就是三个规则的实现swap是单独写的交换函数。

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

很好理解的一段简单代码

        while (index < moreL) {
            if (arr[index] < arr[R]) {
                swap(arr, index, lessR + 1);
                lessR++;
                index++;
            } else if (arr[index] == arr[R]) {
                index++;
            } else {
                swap(arr, index, moreL - 1);
                moreL--;
            }
        }

这时需要去返回一个数组，去返回等于区域的范围

return new int[]{lessR + 1, moreL};

用基础操作去递归实现快排

递归依然使用peocess方法。

因为返回了相同数字的范围。递归就是弄两边

    public static void process(int[] arr, int L, int R) {
        if (L > R) {
            return;
        }
        int[] equalE = partition(arr, L, R);
        //equalE[0]  等于区域的第一个数
        //equalE[1]  等于区域的最后一个数
        process(arr, L, equalE[0] - 1);
        process(arr, equalE[1] + 1, R);
    }

接着去真正的QuickSort去调用这个方法，并判断边界条件

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

时间复杂度分析

快速排序的时间复杂度取决于划分子数组的方式。

最优划分（平均情况）的时间复杂度为O（nlogn），

最差情况（当数组已经排序时）的时间复杂度为O（n^2）。