【C/C++算法】从浅到深学习---分治算法之快排思想（图文兼备 + 源码详解）

绪论：冲击蓝桥杯一起加油！！

每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”

绪论​：本章是针对快速排序进行的优化和再次理解快排思想，将会通过4道题目带你再次深入的了解。
————————
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。

分治（快排思想）

分治的本质就是：

• 通过将大问题分成子问题的思想
• 然后将所有小问题解决后
• 就相当于解决了大问题！
• （具体下图）
  

具体训练：

首先通过一题颜色分类，来为后面的快排中的优化做铺垫
快排有个缺点就是当多个数据相同时，它的时间复杂度将会大大增加

1. 颜色分类

题目：

分析题目

解法：

1. 使用一个双指针（三指针）‘
2. 将数组划分为三分
3. 其中划分内容如下图红色方框
4. 这样最终划分的三块就是最终的结果
   

而具体的解决方法/移动方法如下图：

1. 本质通过2个指针left、right将一个数组分成三分
2. 再通过一个指针i进行遍历
3. 将等于0的放到left左边
4. 等于2的放到right右边
5. 这样等于1的自然就仍然在中间了

题解核心逻辑：

具体步骤见注释：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        //使用三指针的方法将数组分成 3 块
        //    left ~ i-1 ：0
        // i ~ right - 1 ：1
        // right ~ n - 1 ：2

        //那么就需要使用 三个指针
        //left：0的最左边的区间
        //right：2的最右边的区间
        //i：进行遍历，遍历到的值存到 left、right 区间

        for(int left = -1,right = nums.size(),i = 0; i < right ;){
            if(nums[i] == 0){
                swap(nums[++left],nums[i++]);
                //++left,放入新值
                //i++，将继续向后查找 
            }
            else if(nums[i] == 2){
                swap(nums[--right],nums[i]);
                //--right：放入新值
                //i不变：因为交换来的值仍然需要判断
            }
            else{
                i++;//当是 i == 0 的时候 i++即可
            }
        } 
    }
};

下面将把颜色划分的逻辑套用到快排中

2. 排序数组

题目：

分析题目

本题很好理解，就是排序，将一个无序的数组排成升序

本题将使用快速排序来进行解决，
它也是一个八大排序中的非常重要的思想
快排的主要逻辑如下图：

1. 通过一个key值，将数组划分为左右两块
2. 左区间严格 小于等于 key
3. 右区间严格 大于key
4. 然后再去左右区间中重复上述步骤
5. 只到数组只剩一个数后返回，此时返回时因为前面的操作所以最终对于这个数组来说是已经拍好序的了
   
   但当所有相等是就会变成 O(N²)的复杂度：

• 他每次都找到了最后这个数（因为他是 刚好 <= key的）
  
• 所以需要进行优化：将数组同样划分为 3 块（而非 2 块！）
  
• 移动的方法同上题的颜色划分：
  
  它具体怎么优化了呢？

快排的缺点是：当所有值都是重复的，也就是 <= key 时会不断找到最后，所以这里是不太合理的，所以现在将 == 的情况也单独的拿出来（具体如下图），这样的话就不会出现上面的情况，因为这种 == key 情况，它也是有单独的区域的，看公式就知道，最终会不断 i++直接遍历完成！！

对于选key值优化：

1. 用随机的方式选择基准元素（是比较快的相对于三数取中）
2. 生成随机数 r (rand() + srand(time(NULL)))
3. 0 ~ n - 1：r % (right - left + 1)+ left

题解核心逻辑：

class Solution {
public:
    int getRandom(vector<int>& nums,int l,int r){
        int ra = rand() ;
        return nums[ra % (r - l + 1) + l];
    }
    void qsort(vector<int>& nums,int l,int r){
        if(l >= r) return ;

        int key = getRandom(nums,l,r);//随机数

        int i = l, left = l - 1,right = r + 1;
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left],nums[i++]);
            else if( nums[i] == key) i++;
            else swap(nums[--right],nums[i]);
        }

        qsort(nums,l,left);//处理左区间
        qsort(nums,right,r);//处理右区
    }

    vector<int> sortArray(vector<int>& nums) {
        //快速排序思想 + 划分 3 块
        //生成随机值：
        
        // [0 ~ left]
        // [left + 1 ~ i] 
        // [right ~ n - 1]

        // 先将数组划分成 3 分，然后再 分治 0 ~ left 和 right ~ n -1 即可
        
        //划分方法：
        // i < k : swap(nums[++left],nums[i++])
        // i == k : i++
        // i > k : swap(nums[--right],nums[i])

        // 对于基准值 key（用于划分的值）
        //使用随机生成的形式
        srand(time(NULL));
        qsort(nums,0,nums.size()-1);
        return nums;
    }
};

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

题目：

题解核心逻辑：

本题解题思路和是通过快排的方式，将数组不断的划分，并且在划分过程中寻找第K大的值
具体步骤如下：

1. 快排思想 + 划分成3块 + 随机取key值
2. 此时因为会划分成3块，而这三块他们的属性如下：
   1. 0 ~ left：小于key值
   2. left ~ right - 1：等于key值
   3. right ~ n - 1：大于key值
3. 我们就能通过记录这三块区间中元素的个数，来快速的缩小区间查找
   

更多细节和注释见下代码：

class Solution {
public:
    int qsort(vector<int>& nums, int k, int l, int r)
    {
        if (l == r)
            return nums[r];

        int key = nums[rand() % ( r - l + 1) + l];

        int a = 0, b = 0, c = 0;
        // 划分区间
        int i = l, left = l - 1, right = r + 1;
        while (i < right)
        {
            if (nums[i] < key) 
            {
                swap(nums[++left], nums[i++]);
                a++;
            } 
            else if (nums[i] == key) 
            {
                i++;
                b++;
            } 
            else 
            {
                swap(nums[--right], nums[i]);
                c++;
            }
        }

//如果：第k大的元素 <= c的个数(代表最在右边的区间)
//那么继续在该区间中去找
        if (k <= c)
            return qsort(nums, k, right, r);
        else if (k <= b + c)//若 k <= b + c （代表k是在等于key值的区间，此时他和key值相等所以返回key即可）
            return key;//最终不断的划分，最差的结果是在最后一次划分后得到答案
        else//最后就是在最左边的区间去找，此处第k大的需要减去 left 左边区间元素个数
            return qsort(nums, k - b - c, l, left);
    }

    int findKthLargest(vector<int>& nums, int k) 
    {
        // 使用 快速选择 解决
        // 将数组划分成 三分：
        // 0 ~ left : <key（个数为 c 个）
        // left + 1 ~ right - 1 : == key（个数为b个）
        // right ~ n - 1 : >key（个数为a个）

        // 化成三分之后，判断 第k大的元素，在那个区间： a / b / c
        // 判断方法：
        // c 中存到是最大的前几：那么如果 k < c 代表 k
        // 在c中（c中的个数代表的就是前几大） b 若不在c中则在 b 区间中找，此时 k
        // < c + b 就代表在 b中（因为已经不在c中了，所以前面的要加上） a ... k <
        // a + b + c
        srand(time(NULL));
        return qsort(nums, k, 0, nums.size() - 1);
    }
};

4. 库存管理 III

题目：

题解核心逻辑：

本题和上题类似，就不过述了，具体见注释：

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        //同样 使用 快速 分三块 + 随机基准值
        srand(time(NULL));
        qsort(stock,cnt,0,stock.size()-1);
        //通过找到第cnt个小的数后，将数组划分成了 三块
        return {stock.begin(),stock.begin() + cnt};
    }

    void qsort(vector<int>& stock, int cnt,int l,int r){
        if(l == r) return ;

        int key = stock[rand() % (r - l + 1) + l];
        
        int i = l,left = l - 1,right = r + 1;
        while(i < right)
        {
            if(stock[i] < key) {
                swap(stock[++left],stock[i++]);
                
            }
            else if(stock[i] == key){
                i++;
    
            }
            else{
                swap(stock[--right],stock[i]);
            }
        }


        int a = left - l + 1,b = right - left - 1;
//找前k个小的
//若 cnt < a 代表前面 a 个元素个数比 cnt 的个数大，所以只需要在前 l ~ left 区间找即可
        if(cnt < a){//面存了a个小的
            return qsort(stock,cnt,l,left);
        }
        else if(cnt <= a + b)// 3 < 2 + 1
            return ;
        else
            return qsort(stock,cnt - a - b,right,r);
        
    }
};