排序算法丨快速排序

前言

快速排序(QuickSort)，由 C.A.R.Hoare(东尼霍尔，Charles Antony Richard Hoare) 在 1960 年提出。
它是对冒泡排序算法的一种改进，比冒泡排序高效得多，所以叫做快速排序。
之所以快，是因为它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

排序思路

它的基本思想：

从数组中取出一个数，称之为基数（pivot）；
遍历数组，将大于或等于基数的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域；
将左右两个区域视为两个数组，重复前两个步骤，直到排序完成。（递归）

分治法

分治法，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

在快速排序中，就用到了这种方法：将一个待排序的数组，分成两个待排序的小数组，排序后再分成小数组......

基准的选择

基数的选择没有固定标准，随意选择区间内任何一个数字做基数都可以。通常来讲有三种选择方式：

选择第一个元素作为基数；
选择最后一个元素作为基数；
选择区间内一个随机元素作为基数。

选择的基数不同，算法的实现也不同。实际上第 3 种选择方式的平均时间复杂度是最优的。

如果选择第 1 种方案，那么在排列完全逆序的数组时，整个数组都没有分成两半，每一轮都只确定了基准元素的位置。
这种极端情况下，快速排序无法发挥分治法的优势，时间复杂度退化成了 O(n²)。
所以，为了避免这种情况，一般都是选择第 3 种方案——随机选择也有一定的概率选到最大值或最小值。

元素的交换移动

确定了基准元素后，比较其他元素与基准元素的大小，将其他元素移动到适合的位置。

private static int partition1(int[] arr, int startIndex, int endIndex) {
    // 取第一个位置的元素作为基准元素
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;
    // 坑的位置，初始等于pivot的位置
    int index = startIndex;
    // 大循环在左右指针重合或者交错时结束
    while (right >= left) {
        // right指针从右向左进行比较
        while (right >= left) {
            if (arr[right] < pivot) {
                arr[left] = arr[right];
                index = right;
                left++;
                break;
            }
            right--;
        }
        //left指针从左向右进行比较
        while (right >= left) {
            if (arr[left] > pivot) {
                arr[right] = arr[left];
                index = left;
                right--;
                break;
            }
            left++;
        }
    }
    arr[index] = pivot;
    return index;
}

private static int partition2(int[] arr, int startIndex, int endIndex) {
    // 取第一个位置的元素作为基准元素
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;
    while (left != right) {
        // 控制right指针比较并左移
        while (left < right && arr[right] > pivot) {
            right--;
        }
        // 控制right指针比较并右移
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        // 交换left和right指向的元素
        if (left < right) {
            int p = arr[left];
            arr[left] = arr[right];
            arr[right] = p;
        }
    }
    // pivot和指针重合点交换
    int p = arr[left];
    arr[left] = arr[startIndex];
    arr[startIndex] = p;
    return left;
}

代码实现

从 left 开始，遇到比基数大的数，记录其下标；再从 right 往前遍历，找到第一个比基准元素小的数，记录其下标；然后交换这两个数。继续遍历，直到 left 和 right 相遇。然后就交换基数和中间值，并返回中间值的下标。

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int start, int end) {
    // 如果区域内的数字少于 2 个，退出递归
    if (start >= end) {
        return;
    }
    // 将数组分区，并获得中间值的下标
    int middle = partition(arr, start, end);
    // 对左边区域快速排序
    quickSort(arr, start, middle - 1);
    // 对右边区域快速排序
    quickSort(arr, middle + 1, end);
}

// 将 arr 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
public static int partition(int[] arr, int start, int end) {
    // 取第一个数为基数；应该随机挑选一个更好
    int pivot = arr[start];
    // 从第二个数开始分区
    int left = start + 1;
    // 右边界
    int right = end;
    // left、right 相遇时退出循环
    while (left < right) {
        // 找到第一个大于基数的位置
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        // 交换这两个数，使得左边分区都小于或等于基数，右边分区大于或等于基数
        if (left != right) {
            exchange(arr, left, right);
            right--;
        }
    }
    // 如果 left 和 right 相等，单独比较 arr[right] 和 pivot
    if (left == right && arr[right] > pivot) {
        right--;
    }
    // 将基数和中间数交换
    if (right != start) {
        exchange(arr, start, right);
    }
    // 返回中间值的下标
    return right;
}

// 交换两个数字
private static void exchange(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

动画演示

演示动画来源于Visualgo

复杂度分析

平均时间复杂度为 O(nlogn)，最坏的时间复杂度为 O(n²)，空间复杂度与递归的层数有关，每层递归会生成一些临时变量，所以空间复杂度为 O(logn) ~ O(n)，平均空间复杂度为 O(logn)。

快速排序的优化

第一种就是每轮选择基数时，从剩余的数组中随机选择一个数字作为基数。这样每轮都选到最大或最小值的概率就会变得很低了（但依然存在概率）。用这种方式选择基数，其平均时间复杂度是最优的。

第二种是在排序之前，先用洗牌算法将数组的原有顺序打乱，以防止原数组正序或逆序。Java 已经将洗牌算法封装到了集合类中，即 Collections.shuffle() 函数。洗牌算法由 Ronald A.Fisher 和 Frank Yates 于 1938 年发明，思路是每次从未处理的数据中随机取出一个数字，然后把该数字放在数组中所有未处理数据的尾部。

第三种是在快速排序之前先对数组做个判断，如果已经有序则直接返回，如果是逆序则直接倒序即可。在 Java 内部封装的 Arrays.sort() 的源码中就采用了此解决方案。

参考

LeetCode
程序员小灰
 Github