【优选算法---分治】快速排序三路划分（颜色分类、快速排序、数组第K大的元素、数组中最小的K个元素）

一、颜色分类

题目链接:

75. 颜色分类 - 力扣（LeetCode）

题目介绍：

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

思路：

这个题目的要求其实就是将0放到最左边，将1放到中间将2放到最后边，思路就是将数组划分为三个部分

设数组大小为 n ，定义三个指针 left, cur, right :

在 cur 往后扫描的过程中，保证：

[0, left）内的元素都是 0
[left , cur - 1] 内的元素都是 1 ；
[cur, right] 内的元素是待定元素；
（right, n] 内的元素都是 2 。

当cur遍历到0，交换nums[cur]和nums[left],由于交换前left所指元素一定是1，所以cur和left都可以++。

当cur遍历到1，cur++;

当cur遍历到2，交换nums[cur]和nums[right],right可以--，但是由于交换前right所指元素依旧是待定元素，所以cur不能++，还要判断一下

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;
        int cur=left;
        while (cur <= right) {
            if (nums[cur] ==0) {
                swap(nums[left], nums[cur]);
                left++;
                cur++;
            } else if (nums[cur] == 1) {
                cur++;
            } else {
                swap(nums[cur], nums[right]);
                right--;
            }
        }
    }
};

二、快速排序

题目链接:

912. 排序数组 - 力扣（LeetCode）

题目介绍：

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

1 <= nums.length <= 5 * 10^4
-5 * 104 <= nums[i] <= 5 * 10^4

思路：

与上面的题思路相同，不过我们需要先选择一个基准元素，让这个基准元素左边都是小于他的值，右边都是大于他的值，这样这个基准元素在数组中就排序好了。接下来就是排序左边的区间和右边的区间。

注意，数组中选择的那个基准元素可能存在很多个，一轮排序后 [left,right] 区间都是key，所以这段区间都不需要排序了，只需要排【begin，left-1】和【right+1，end】区间。

假设一个数组全是一样的值，这样三路划分的效率就很块，因为cur就会不断向后遍历，直到碰到right(end),其效率就是O(N)

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        qsort(nums,0,nums.size()-1);
        return nums;
    }
    void qsort(vector<int>& nums, int begin, int end) {
        // 进了这个区间一定能找到
        if (begin >= end)
            return;
        int key = nums[begin];
        int left = begin;
        int right = end;

        int cur = left + 1;
        // 分成三块
        while (cur <= right) {
            if (nums[cur] < key) {
                swap(nums[left++], nums[cur++]);
            } else if (nums[cur] == key) {
                cur++;
            } else {
                swap(nums[right--], nums[cur]);
            }
        }
        qsort(nums, begin, left - 1);
        qsort(nums, right + 1, end);
    }
};

三、数组的第K个最大元素

题目链接：

215. 数组中的第K个最大元素 - 力扣（LeetCode）

题目介绍：

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

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

1 <= k <= nums.length <= 105
-104 <= nums[i] <= 10

思路：

首先我们可以选择一个基准元素，采用三路划分排序一遍，此时 key的位置就排序好了，虽然此时他的左右两边都是无序的，但是此时我们可以判断一下，如果右边的元素个数大于等于k，那说明第k大的元素就在右边，那我们就不用管左边了，如果中间的元素加上右边的元素才大于等于k，那说明第k大的元素就是key，否则我们就到左边找第( k-右边元素数量-中间元素数量)大的元素，这样的算法是非常快的，因为我们不需要将数组完全的排好序。

其次，只要进入到了某个区间找元素，那就说明这值一定在这个区间中，所以当begin>=end时我们就可以返回nums[begin]

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return qsort(nums,0,nums.size()-1,k);
    }

    int qsort(vector<int>& nums,int begin,int end,int k)
    {
        //进了这个区间一定能找到
        if(begin>=end)return nums[begin];

        int key=nums[begin];
        int left=begin;
        int right=end;

        int cur=left+1;
        //分成三块
        while(cur<=right)
        {
            if(nums[cur]<key)
            {
                swap(nums[left++],nums[cur++]);
            }
            else if(nums[cur]==key)
            {
                cur++;
            }
            else
            {
                swap(nums[right--],nums[cur]);
            }
        }
        int c=end-right;
        int b=right-left+1;
        if(c>=k)return qsort(nums,right+1,end,k);
        else if(b+c>=k)return key;
        else return qsort(nums,begin,left-1,k-b-c);
    }
};

四、数组中最小的k个数

题目链接:

LCR 159. 库存管理 III - 力扣（LeetCode）

题目介绍：

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

思路：

与上一题的思路一样，我们先选择一个基准元素采用三路划分，将数组分为左中右三部分，如果左边的数量大于等于k，那说明最小的k个数就在左边，就到左边找，中间和右边不管了。如果左边和中间加起来的数量才大于等于k，那就可以直接返回，因为前k个元素已经在左边和中间了，虽然他们不是完全有序的。否则的话，我们就要到右边找最小的（k-a-b）个数了

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& nums, int k) {
        qsort(nums,0,nums.size()-1,k);
        return {nums.begin(),nums.begin()+k};
    }
    void qsort(vector<int>& nums,int begin,int end,int k)
    {
        if(begin>=end) return;

        int key=nums[begin];

        int left=begin,right=end;
        int cur=left+1;
        //分为三块
        while(cur<=right)
        {
            if(nums[cur]<key)
            swap(nums[left++],nums[cur++]);
            else if(nums[cur]==key)
            cur++;
            else
            swap(nums[right--],nums[cur]);
        }
        // 判断
        int a=left-begin;
        int b=right-left+1;

        if(a>=k) qsort(nums,begin,left-1,k);
        else if(a+b>=k) return;
        else qsort(nums,right+1,end,k-a-b);
    }
};