快速排序算法详解

一、什么是快速排序算法

快速排序是对冒泡排序的一种改进，由 C.A.R.Hoare（Charles Antony Richard Hoare，东尼·霍尔）在 1962 年提出。

快速排序基本思想：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

快速排序原理：

排序算法的思想非常简单，在待排序的数列中，我们首先要找一个数字作为基准数（这只是个专用名词）。

注意：这里的基准数为每一趟比较的中枢，该数的选取将决定快排算法的速度快慢

为了方便，我们一般选择第 1 个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。

这是典型的分治思想，即分治法。

二、快速排序的实现

1.单指针

问题引入：

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。

思路：

通过指针确定一个 小于区域（该区域内所有元素均小于num，初始下标为 -1）

依次遍历数组，若当前遍历元素小于或等于num，则将当前遍历元素(下标为i) 与小于区域的下一个位置元素 (下标为 less + 1) 进行交换

若当前遍历元素大于num则继续遍历

边界情况考虑：

若第一个元素需要交换则 自己和自己交换。符合题意

代码实现：

public static void arrange(int[] arr, int num) {
    // 初始 x 区域的下标 => 指针
    int less = -1;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] <= num) {
            // 前++是先自加再使用, 而后++是先使用再自加
            // x 先 + 1， 然后与 i 位置上的值交换 =>  i 与 x 的下一个位置进行交换
            swap(arr, i, ++less);
        }
    }
}

public static void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

2.双指针

问题引入：

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边，等于num的数放中间

思路：

通过头指针less确定一个 小于区域(该区域内所有元素均小于num，初始下标为 -1)

通过尾指针more确定一个 大于区域（该区域内所有元素均大于num，初始下标为 arr.length ）

依次遍历数组，若当前遍历元素小于或等于num，则将当前遍历元素（下标为i）与 小于区域的下一个位置元素(下标为 less + 1)进行交换；若当前遍历元素大于num，则将当前遍历元素(下标为i)与大于区域的下一个位置元素(下标为 more - 1)进行交换；即头指针向后走，尾指针向前走，当遍历到尾指针时循环结束（所有元素均已比较）

代码实现：

public static void sortColors(int[] arr, int n) {
    // 小于区域指针
    int less = -1;
    // 大于区域指针
    int more = arr.length;
    // 数组指针
    int i = 0;
    // 指针遇到大于区域的前一个位置 => 停止循环
    while (i < more) {
        // 当前数字大于给定数字，当前数字与大于区域的下一个交换
        if (arr[i] > n) {
            swap(arr, i, --more);
        }else if (arr[i] < n) {
            // 当前数字小于给定数字，当前数字与小于区域的下一个交换
            swap(arr, i, ++less);
        }else {
            // 当前数字等于给定数字，指针向后移动
            i++;
        }
    }
}

public static void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

3.快速排序算法实现

理解了单指针和双指针，接下来让我们使用分治的思想，利用递归来解决快速排序问题

在双指针问题上，我们已经可以做到让一个数的左右有序（左边的值均小于右边的值）

那么如果继续在该数的左右两边再次使用该方法，我们便又可以确定两个数，使得这两个数的左右有序

以此类推，继续下去，我们便可以让更多的数有序，这便是利用递归实现快速排序的基本思想

让我们先来实现主方法：

传入一个数组，若该数组为空或少于两个元素则直接返回；

否则开始使用快速排序算法进行排序 (传入初始元素下标0 和 末尾元素下标)

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

接着让我们来实现快速排序算法：

接收到主方法传入的参数后，首先利用partition方法确定中间的位置，即先让一个数的左右两边有序并返回此时中枢的下标；

接着让左边有序；

最后让右边有序；

public static void qicksortV1(int[] arr, int L, int R) {
    // 双指针基础上 左右递归进行
    if (L < R) {
        // 局部确定中枢
        int pivotloc = partition(arr,L,R);
        // 局部左边有序
        qicksortV1(arr,L,pivotloc - 1);
        // 局部右边有序
        qicksortV1(arr,pivotloc + 1, R);
    }
}

我们可以看到算法十分的简洁，但问题是如何寻找到当前传入数组的中枢位置并返回？让我们来看看partition方法的实现

/**
 * 快速排序确定中枢位置
 * @param: arr 传入的数组
 * @param: low 要确定中枢区域的头指针
 * @param: high 要确定中枢区域的尾指针
 * @return: 中枢位置
 */
public static int partition(int[] arr, int low, int high) {
    // 以最左侧为基准放在中间 (该数的选择会影响快速排序的效率)
    int pivot = arr[low];
    while (low < high) {
        // 尾指针的值大于中枢，尾指针 --
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        // 循环停止，当前尾指针所指元素小于中枢元素 => 搬到前面
        arr[low] = arr[high];
        // 头指针的值小于中枢，头指针 ++
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        // 循环停止，当前头指针所指元素大于中枢元素 => 搬到后面
        arr[high] = arr[low];
    }
    // 循环结束 此时 low 和 high 相等 => 该位置用于放置中枢位置
    arr[low] = pivot;
    // 返回中枢位置
    return low;
}

可以看到该方法与双指针例题极为相似，双指针需要交换，而该方法则是需要返回中枢的位置。

完整的快速排序代码：

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

public static void qicksortV1(int[] arr, int L, int R) {
    // 双指针基础上 左右递归进行
    if (L < R) {
        // 局部确定中枢
        int pivotloc = partition(arr,L,R);
        // 局部左边有序
        qicksortV1(arr,L,pivotloc - 1);
        // 局部右边有序
        qicksortV1(arr,pivotloc + 1, R);
    }
}

/**
 * 快速排序确定中枢位置
 * @param arr 传入的数组
 * @param low 要确定中枢区域的头指针
 * @param high 要确定中枢区域的尾指针
 * @return 中枢位置
 */
public static int partition(int[] arr, int low, int high) {
    // 以最左侧为基准放在中间
    int pivot = arr[low];
    while (low < high) {
        // 尾指针的值大于中枢，尾指针 --
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        // 循环停止，当前尾指针所指元素小于中枢元素 => 搬到前面
        arr[low] = arr[high];
        // 头指针的值小于中枢，头指针 ++
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        // 循环停止，当前头指针所指元素大于中枢元素 => 搬到后面
        arr[high] = arr[low];
    }
    // 循环结束 此时 low 和 high 相等 => 该位置用于放置中枢位置
    arr[low] = pivot;
    return low;
}

代码分析：

经典快排：

从上述代码我们可以看到一次只搞定一个数，每次将初始的左侧数作为基准放在中间，<基准数的放左边，>=基准数的放右边；这样会导致右边会包含等于基准值的若干个数。接着返回基准值的左边部分和右边部分，再对左右部分进行上述操作，最终对数组完成排序。经典快排可能导致子区域划分极不平均。
当数据为{1,2,3, 4,5,6,7}时，每次将第一个数作为基准，所需时间复杂度：O（N*N）

那如何挑选基准，使得挑选中枢的时间缩短呢？

改进后的经典快排：

改进后的快排一次搞定一部分数（=pivot的那部分），总体来说，经典快排每次递归调用只有一个数不动，其他的需要进行二次甚至多次递归；而改进后的则是=pivot的一部分数全都不动，只需递归 <x 或者 >x的数即可。
为了避免经典快排可能导致子区域划分极不平均，改进后的快排则是随机抽取数组中的一个数作为基准值对数组进行排序。

其时间和空间复杂度依次为：

时间复杂度O(N*logN)，空间复杂度O(logN);

递归过程（改进的快速排序）

中枢位置为一个数组，即中枢开始的位置和中枢结束的位置

public static void qicksortV2(int[] arr, int L, int R) {
    // 双指针基础上 左右递归进行
    if (L < R) {
        //先随机取出一个数放到最后(取出下标)
        int randloc = (int) (Math.random() * (R - L + 1));
        swap(arr, L + randloc, R);
        // 局部确定中枢 （0位置为第一个中枢位置，1位置为最后一个中枢位置）
        int[] pivotloc = partition(arr, L, R);
        // 局部左边有序
        qicksortV2(arr, L, pivotloc[0] - 1);
        // 局部右边有序
        qicksortV2(arr, pivotloc[1] + 1, R);
    }
}

partition 过程

/**
 * 快速排序确定中枢位置 （中枢开始的位置和结束的位置） => 双指针经典用法
 *
 * @param arr
 * @param low
 * @param high
 * @return
 */
public static int[] partition(int[] arr, int low, int high) {
    // 小于区域指针
    int less = low - 1;
    // 大于区域指针
    int more = high;
    // low为数组指针
    while (low < more) {
        // 当前数字大于给定数字，当前数字与大于区域的下一个交换
        if (arr[low] > arr[high]) {
            // 前++是先自加再使用, 而后++是先使用再自加
            swap(arr, low,--more);
        } else if (arr[low] < arr[high]) {
            // 当前数字小于给定数字，当前数字与小于区域的下一个交换，指针向前移动
            swap(arr, low++, ++less);
        } else {
            // 当前数字等于给定数字，指针向后移动
            low++;
        }
    }
    // 循环结束，less指向中枢的前一个位置，more指向中枢的后一个位置
    // 将最后位置的中枢与more交换，此时more即为中枢的最后一个位置
    swap(arr,more,high);
    return new int[]{less + 1, more};
}

改进的快速排序完整代码：

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

public static void qicksortV2(int[] arr, int L, int R) {
    // 双指针基础上 左右递归进行
    if (L < R) {
        //先随机取出一个数放到最后(取出下标)
        int randloc = (int) (Math.random() * (R - L + 1));
        swap(arr, L + randloc, R);
        // 局部确定中枢 （0位置为第一个中枢位置，1位置为最后一个中枢位置）
        int[] pivotloc = partition(arr, L, R);
        // 局部左边有序
        qicksortV2(arr, L, pivotloc[0] - 1);
        // 局部右边有序
        qicksortV2(arr, pivotloc[1] + 1, R);
    }
}

/**
 * 快速排序确定中枢位置 （中枢开始的位置和结束的位置） => 双指针经典用法
 *
 * @param arr
 * @param low
 * @param high
 * @return
 */
public static int[] partition(int[] arr, int low, int high) {
    // 小于区域指针
    int less = low - 1;
    // 大于区域指针
    int more = high;
    // low为数组指针
    while (low < more) {
        // 当前数字大于给定数字，当前数字与大于区域的下一个交换
        if (arr[low] > arr[high]) {
            // 前++是先自加再使用, 而后++是先使用再自加
            swap(arr, low,--more);
        } else if (arr[low] < arr[high]) {
            // 当前数字小于给定数字，当前数字与小于区域的下一个交换，指针向前移动
            swap(arr, low++, ++less);
        } else {
            // 当前数字等于给定数字，指针向后移动
            low++;
        }
    }
    // 循环结束，less指向中枢的前一个位置，more指向中枢的后一个位置
    // 将最后位置的中枢与more交换，此时more即为中枢的最后一个位置
    swap(arr,more,high);
    return new int[]{less + 1, more};
}

三、快速排序的特点及性能

快速排序是在冒泡排序的基础上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式的交换，交换的距离很大，因此总的比较和交换次数少了很多，速度也快了不少。

但是快速排序在最坏情况下的时间复杂度和冒泡排序一样，是 O(n2)，实际上每次比较都需要交换，但是这种情况并不常见。我们可以思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是 O(nlogn)，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。这种算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来。

快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的空间复杂度为 O(logn)，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O(n)。所以我们一般认为快速排序的空间复杂度为 O(logn)。

快速排序是一个不稳定的算法，在经过排序之后，可能会对相同值的元素的相对位置造成改变。

快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。