快速选择 & 三向切分快排

概述

标题这两个算法，一个是阉割版的快排，另一个是特殊优化过的快排。既然都跟快排有关系，那本文就从最基础的快速排序开始讲起吧。本文中提到的排序都将以升序为例。

快速排序

快速排序是一位叫 C. A. R. Hoare （中文名：霍尔）的强者发明的。

1960年，霍尔在对俄语词典进行排序的过程中发明了这个算法，当时他才26岁。根据霍尔的自述：“解决词典排序时，我第一个想法是使用冒泡排序，但非常幸运的是，我第二个方法就想到了快速排序。”我们完全赞同他的自我评价：“我是幸运的，以发明一种新的排序方法开始一个人的计算机职业生涯实在是太美妙了！”——《算法设计与分析基础（第三版）》

快速排序的中心思想是分治。每一轮排序中，选取一个基准数，把小于这个基准数的都放到数组的左边，把大于这个基准数的都放到数组的右边，然后把基准数放在二者的交界处。这样，我们就相当于把这个基准数放到了它排完序后该放的地方。然而此时这个数左边和右边的区间都还处于无序的状态，所以我们递归地对左右区间进行排序，最终使整个数组有序。平均而言，快速排序的时间复杂度是 O(nlogn) ，空间复杂度是 O(logn) ，但是最差的情况下，每次选取基准数时刚好是区间内的最大/最小值（比如对一个降序数组进行升序排序），这样就需要递归 n-1 次。所以有写法为了尽量降低极端情况的影响，采用随机选择基准数的策略。而我比较习惯用Lomuto划分来写，就是选取区间左边第一个数作为基准数。

代码

void QuickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return; //递归终止条件
    int i = left; int j = right;
    int key = left;
    while (i < j) {
        while (nums[j] >= nums[key] && i < j) j--;
        while (nums[i] <= nums[key] && i < j) i++;
        swap(nums[i], nums[j]);
    }
    swap(nums[key], nums[i]);
    QuickSort(nums, left, i - 1);
    QuickSort(nums, i + 1, right);
}

下面通过两个例题来介绍标题里的两个算法。

---

例题 1

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

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1：

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2：

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

---

题解 1

这道题就是快速选择算法的经典应用场景了，它可以在 O(n) 的时间复杂度下找到这个数组第K大的数。我前面之所以说快速选择是阉割版的快速排序，是因为这两个算法的思路是一毛一样的，快速选择解决的问题可以说是快排的子问题。在快速排序中，每轮排序可以确定基准数在排序后数组中的位置，就相当于它的大小排序。例如在某一轮排序中，我们确定了基准数 a 是数组中第 k' 大的数，那么：

• 如果 k' = k ，说明当前的基准数就是数组第 k 大的数。

• 如果 k' < k ，说明我们要找的数比当前的基准数要小一些，所以我们递归地在基准数左边的区间里继续查找，而右边的区间就可以放着不动了。

• 如果 k' > k ，说明我们要找的数比当前的基准数要大一些，所以我们递归地在基准数右边的区间里继续查找，而左边的区间就可以放着不动了。

在理想情况下，我们每次可以将数组对半分，此时我们需要查找的次数最大是一个首项为 n ，项数为 log₂n ，公比为 1/2 的等比数列的和，即 2n-2 次，所以本算法的时间复杂度是 O(n) 。

代码：

class Solution {
private:
    int partition(vector<int>& nums, int l, int r, int k) {
        int i = l; int j = r;
        while (i < j) {
            while (nums[j] >= nums[l] && i < j) j--;
            while (nums[i] <= nums[l] && i < j) i++;
            swap(nums[i], nums[j]);
        }
        swap(nums[l], nums[i]);
        if (i == k) return nums[i];
        else if (i > k) return partition(nums, l, i - 1, k);
        else return partition(nums, i + 1, r, k);
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return partition(nums, 0, n - 1, n - k);
    }
};

注意： 每轮排序时，要先减小 j 的值，再增大 i 的值，这样可以保证 i 和 j 重合时对应的值一定是小于 key 的，这样就可以拿 key 和 nums[i] 直接交换。

---

例题 2

LeetCode 324. 摆动排序 II

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

示例 1：

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

示例 2:

输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]

进阶： 使用 O(n) 时间复杂度或原地 O(1) 额外空间来实现。

---

题解 2

在特殊情况下，待排序数组可能是一个有很多重复元素的数组，而常规的快排依然会进行 logn 次遍历。而三向切分则是快速排序针对此场景的优化方案，每轮排序把小于基准数的放左边，大于基准数的放右边，而等于基准数的全部汇总放中间，这样未排序的部分就可以大大缩小。

回到正题，本题最简单的解法就是先排个序，然后左边较小的部分和右边较大的部分穿插起来排。但是当数组中重复元素等于数组长度的一半时，就会出现两个相同的数字挨着的情况，这种情况不满足题设的严格大于/小于。为了避免这种情况，我们可以将左子数组和右子数组逆序一下再穿插。

例如针对数组 [1,1,2,2,2,3] ，如果直接排序然后穿插的话，左子数组是 [1,1,2] ，右子数组是 [2,2,3] ，穿插后是 [1,2,1,2,2,3] ，不满足题目条件。而逆序后，左子数组就是 [2,1,1] ，右子数组就是 [3,2,2] ，穿插后是 [2,3,1,2,1,2] ，满足题目条件。这种算法的时间复杂度是 O(nlogn) 。

想要优化，就需要用到上面提到的三向切分快排了。稍加思索就能发现我们其实根本不需要保证两个子数组是有序的，只要能让可能挨着出现的数字一个在这头一个在那头就可以了。这个挨着出现的数字肯定是同时出现在左子数组和右子数组里的数字，而这种数字一定是数组的中位数。结合快速查找算法，我们可以预先查到这个数组的中位数是多少，然后再用三向切分的思想把中位数全部集中到数组中间，这时再把数组从中间切开穿插排列，就可以得到题目要求的数组了。

代码：

class Solution {
private:
    int QuickSelect(vector<int>& nums, int l, int r, int k) {
        int i = l; int j = r;
        while (i < j) {
            while (nums[j] >= nums[l] && i < j) j--;
            while (nums[i] <= nums[l] && i < j) i++;
            swap(nums[i], nums[j]);
        }
        swap(nums[l], nums[i]);
        if (i == k) return nums[i];
        else if (i > k) return QuickSelect(nums, l, i - 1, k);
        else return QuickSelect(nums, i + 1, r, k);
    }
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return;
        int key = QuickSelect(nums, 0, n - 1, n - n / 2);
        int left = 0; int right = n - 1; int mid = 0;
        while (mid < right) {
            if (nums[mid] < key) {
                swap(nums[mid], nums[left]);
                left++;
                mid++;
            }
            else if (nums[mid] > key) {
                swap(nums[mid], nums[right]);
                right--;
            }
            else mid++;
        }
        int m = n - n / 2;
        vector<int> temp1(nums.begin(), nums.begin() + m);
        vector<int> temp2(nums.begin() + m, nums.end());
        for (int i = 0; i < temp1.size(); i++) nums[i * 2] = temp1[temp1.size() - i - 1];
        for (int i = 0; i < temp2.size(); i++) nums[i * 2 + 1] = temp2[temp2.size() - i - 1];
        return;
    }
};

其中，快速选择找到的中位数是后面三向切分的基准数。由于三向切分只进行了一轮，所以时间复杂度是 O(n) ，而快速选择的时间复杂度是 O(n) ，所以整个算法的时间复杂度也是 O(n) 。

---

有的没的

在学Linux

开始学Linux了，没有闲置的设备就在电脑里装了虚拟机。每次从Linux回到Windows都有一种如释重负的轻松的感觉，刚开始转换操作系统真别扭。但是在Shell里敲指令还是很带感的！

放暑假了

19号就考完了，24号交了论文之后就正式开始暑假了。看大家的去向，好多人都找了实习，而我暑假除了社会调查的作业以外剩下的时间都能自己安排。这个暑假是这辈子过的最长的暑假了，接近三个月。要好好珍惜最后的闲暇了，退休前是不可能再有这么长的空闲了。在这里立一些暑期flag，也不追求全部都能完成，能认真地做完一两项都是好的，就是希望能好好利用这个暑假吧。

• 《鸟哥的Linux私房菜 基础学习篇》

• 《计算机网络 自顶向下方法》

• 学习数据库和SQL的相关知识

• 《STL源码剖析》

• 找一些实战项目练练手

• LeetCode坚持刷题，每日一题的基础上再加练

暂时就想到这些。8说了，开卷！

没事听点歌（Jam - 七月上）