快速排序

题目描述

给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

数据范围：1 ≤ n ≤ 100000
在这里插入图片描述
912. 排序数组 https://leetcode.cn/problems/sort-an-array/

解法

class Solution {
    public int[] sortArray(int[] nums) {
        int l = 0, r = nums.length - 1;
        quickSort(nums, l, r);
        return nums;
    }

    public void quickSort(int[] nums, int l, int r) {
        if (l >= r) return;

        int x = nums[l + r >> 1], i = l - 1, j = r + 1;
        while (i < j) {
            while (nums[++i] < x);
            while (nums[--j] > x);

            if (i < j) swap(nums, i, j);
        }

        quickSort(nums, l, j);
        quickSort(nums, j + 1, r);
    }

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

讲解

在这里插入图片描述
分治的思想。

确定分界点。可以取q[l], q[r], q[(l+r)/2], 随机
调整区间，让<=x的都在>=x的左边。
递归处理左右两段。

如何优雅地执行步骤二：
双指针方法，i 和 j 分别在左右端点。当 nums[i] < x时，向右移；当nums[j] > x时，向左移；然后交换这两个元素的位置，直到 i 和 j 相遇。

e.g.
3 1 2 3 5
取x=2，得出
l 初始为0，r 初始为4；l = 0, r = 2时，进行交换，
2 1 3 3 5
此时 l = 0 < r = 2，继续移动，直到 r = 1时，进行交换，
1 2 3 3 5
此时 l = 0 < r = 1，继续移动，直到 l = r = 1，结束第一轮。

之后继续递归排序从下标0~1，以及2~4的部分。

另一个取 x = 3 的例子
在这里插入图片描述
可以看出，最后 i 和 j 是不一定相等的。
最后的结果是：
i 之前的数都是 <= x 的，j 之后的数都是 >= x 的

关于

quickSort(nums, l, j);
quickSort(nums, j + 1, r);

能否可以将 j 和 j + 1 改成 i - 1 和 i 呢？
可以！
同时也要修改 x = nums[l + r + 1 >> 1]。（是不是觉得有点儿像二分？^ ^）

类似的，如果想取 x = nums[l]，那么下面就是 j 和 j + 1；
如果想取 x= nums[r]，那么下面就是 i - 1 和 i。

总之就是：
使用 j 做边界时，不要让x取到右边界。
使用 i 做边界时，不要让x取到左边界。

第k个数（快速选择）

题目描述

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

数据范围：
1 ≤ n ≤ 100000,
1 ≤ k ≤ n

在这里插入图片描述
215. 数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/

解法

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length, l = 0, r = n - 1;
        return quickSelect(nums, l, r, k);
    }

    public int quickSelect(int[] nums, int l, int r, int k) {
        if (l == r) return nums[l];

        int i = l - 1, j = r + 1, x = nums[l + r >> 1];
        while (i < j) {
            while (nums[++i] > x);
            while (nums[--j] < x);
            if (i < j) swap(nums, i, j);
        }

        int ls = j - l + 1;
        if (k <= ls) return quickSelect(nums, l, j, k);
        else return quickSelect(nums, j + 1, r, k - ls);
    }

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

讲解

基于快速排序的思路，整体代码和快速排序类似。
计算出从 j 到 l 的距离是 j - l + 1，将其和 k 进行比较，如果 k 小，说明在前半部分，就直接搜索前半部分的第 k 个；如果 k 大，说明在后半部分，注意要搜索第 k - ls 个，因为后半部分的开始端点是 j + 1。（k - ls + j + 1 = k - j + l - 1 + j + 1 = k + l）。

快速排序的时间复杂度是：期望是O(nlongn)。
快速选择的时间复杂度是：直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n - 1，每次递归的时候又向 n−1 的集合中递归，这种情况是最坏的，时间代价是 O(n ^ 2)。我们可以引入随机化来加速这个过程，它的时间代价的期望是 O(n)。