详解快排及其应用

912. 排序数组

215. 数组中的第K个最大元素

剑指 Offer 40. 最小的k个数

排序算法千千万，今天先讲快排！！

关于「详解归并排序及其应用」，可见 详解归并排序及其应用

算法思想

「快排」其实是先把一个元素的位置排好，然后递归该元素的两边即可

当我们把第一个元素的位置安顿好后，剩余的元素只需要递归处理即可，分别递归区间[lo, j - 1]和[j + 1, hi]

现在来分析一下「快排」的时间复杂度，先看图：

对于长度为n数组来说，树的每一层处理时间为n；如果树趋于一棵平衡二叉树，那么树高为logn

所以最终时间复杂度为o(nlogn)

但是，存在一种特殊情况，如果这颗树长歪了？？如下图所示：

那么，此时的树高变为了n，时间复杂度退化为o(n^2)

出现这种情况的例子也很简单，如果原数组已经有序，那么就会出现这种情况，不信可以手动模拟一下！！

如何解决这种情况呢？

• 可以提前把数组打乱，尽量使树趋于一棵平衡二叉树
• 每次选择一个被安顿的元素时，不取第一个，而是随机取

注意：快排是一种「不稳定」排序；归并是一种「稳定」排序！！

「不稳定」表示值相等的元素可能会被改变原来的顺序

算法框架

public class QuickSort {

    private final Random random = new Random();

    public void sort(int[] nums) {
        // 方法一：打乱
        shuffle(nums);
        sort(nums, 0, nums.length - 1);
    }

    private void sort(int[] nums, int lo, int hi) {
        if (lo >= hi) return ;
        int p = partition(nums, lo, hi);
        sort(nums, lo, p - 1);
        sort(nums, p + 1, hi);
    }

    private int partition(int[] nums, int lo, int hi) {
        // 方法二：随机取
        int p = random.nextInt(hi - lo) + lo;
        swap(nums, lo, p);
        int pivot = nums[lo];
        int i = lo + 1, j = hi;
        while (i <= j) {
            // while 结束后，[lo, i) 均 <= pivot
            while (i < hi && nums[i] <= pivot) i++;
            // while 结束后，(j, hi] 均 > pivot
            while (j > lo && nums[j] > pivot) j--;
            
            // ------ 若为降序，只需更改此处两行代码即可 ------
            // while (i < hi && nums[i] >= pivot) i++;
            // while (j > lo && nums[j] < pivot) j--;
            // ------------------- end -------------------
            
            if (i >= j) break;
            swap(nums, i, j);
        }
        swap(nums, lo, j);
        return j;
    }

    private void shuffle(int[] nums) {
        Random random = new Random();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int r = i + random.nextInt(n - i);
            swap(nums, i, r);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

算法应用

最简单的应用肯定就是给一个数组，然后排序。如题目 排序数组

今天来介绍几个难「亿」点的题目

数组中的第K个最大元素

题目详情可见 数组中的第K个最大元素

当我们安顿的元素位置恰好为K时，那么该元素即为数组中的第 K 个最小元素

x
private int k;
private Random random = new Random();
public int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    // 转化为第 n - k + 1 小
    this.k = n - k + 1;
    return sort(nums, 0, n - 1);
}
private int sort(int[] nums, int lo, int hi) {
    int p = partition(nums, lo, hi);
    // 向左边递归
    if (p > k - 1) return sort(nums, lo, p - 1);
    // 向右边递归
    if (p < k - 1) return sort(nums, p + 1, hi);
    // 找到！！
    return nums[p];
}
private int partition(int[] nums, int lo, int hi) {
    // 注意：这里存在 lo >= hi 的情况
    if (hi > lo) {
        int p = random.nextInt(hi - lo) + lo;
        swap(nums, lo, p);
    }
    int pivot = nums[lo];
    int i = lo + 1, j = hi;
    while (i <= j) {
        while (i < hi && nums[i] <= pivot) i++;
        while (j > lo && nums[j] > pivot) j--;
        if (i >= j) break;
        swap(nums, i, j);
    }
    swap(nums, lo, j);
    return j;
}
private void swap (int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

看到很多人说面试会问这种写法的时间复杂度，先给出答案o(n)

基础的快排框架下，每一层需要处理的节点数都为n，而这个题目类似于二分，每次只需要处理一半的节点数量

假设在完美的情况下，partition()中返回的p都是中间值，这样就可以完美平分节点数量

所以第一次需要处理 $n$$n$ 个节点，第二次需要处理 $\frac{n}{2}$$\frac{n}{2}$ 个节点，第三次需要处理 $\frac{n}{4}$$\frac{n}{4}$ 个节点，以此类推...

综上，一共需要处理 $n+\frac{n}{2}+\frac{n}{4}+\cdots =n+n(\frac{1}{2}+\frac{1}{4}+\cdots )$$n + \frac{n}{2} + \frac{n}{4} + \cdots = n + n(\frac{1}{2} + \frac{1}{4} + \cdots)$ 次

根据等比数列求和公式：$\frac{1}{2}+\frac{1}{4}+\cdots =1-\frac{1}{2^n}=1$$\frac{1}{2} + \frac{1}{4} + \cdots = 1 - \frac{1}{2^n} = 1$

所以一共需要处理 $2n$$2n$ 次，故时间复杂度为o(n)

剑指 Offer 40. 最小的k个数

题目详情可见 剑指 Offer 40. 最小的k个数

和上一题大同小异，当我们安顿的元素位置恰好为K时，那么该元素及其左边的元素即为数组中最小的 k 个数

private int k;
private Random random = new Random();
public int[] getLeastNumbers(int[] arr, int k) {
    if (k == 0 || arr.length == 0) return new int[0];
    this.k = k;
    return sort(arr, 0, arr.length - 1);
}
private int[] sort(int[] nums, int lo, int hi) {
    int p = partition(nums, lo, hi);
    if (p > k - 1) return sort(nums, lo, p - 1);
    if (p < k - 1) return sort(nums, p + 1, hi);
    return Arrays.copyOf(nums, k);
}
private int partition(int[] nums, int lo, int hi) {
    if (hi > lo) {
        int p = random.nextInt(hi - lo) + lo;
        swap(nums, lo, p);
    }
    int pivot = nums[lo];
    int i = lo + 1, j = hi;
    while (i <= j) {
        while (i < hi && nums[i] <= pivot) i++;
        while (j > lo && nums[j] > pivot) j--;
        if (i >= j) break;
        swap(nums, i, j);
    }
    swap(nums, lo, j);
    return j;
}
private void swap (int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}