【优选算法】--- 分治 快速排序

一、颜色分类 / 对快排的复习

如何对一个数组进行快速排序？

他的大致思想：
（1）就是在一个数组里面随机找一个基准元素key
（2）然后将数组分块进行递归排序,小于基准元素key的在左边，大于基准元素key的在右边（升序）
（3）依次不断递归分制，直到最小单位为止。
（4）利用双指针/三指针进行遍历交换swap

1、题目解析

题目链接：颜色分类

2、算法原理

根据题目要求，我们需要把数组中的元素012按顺序排好。

采用：快排+三指针的解法

把 “ 1 ”当做key基准元素

1. 如果nums[i]==0，我们是让 nums [ left+1 ] 跟 nums[i] 交换的（最后 left 和 i 均需要++）
2. 如果nums[i]==1，i++即可
3. 如果nums[i]==2，我们是让 nums [ right-1 ] 跟 nums[i] 交换的（最后 只需要对 right --即可，因为right交换给 i 的元素是未扫描的！）
   

3、代码

class Solution 
{
public:
    void sortColors(vector<int>& nums) 
    {
        int n=nums.size();
        int left=-1,right=n,i=0;// 这里的 left和right都是数组外的！

        while(i<right)// 因为i是扫描区，扫描完之后，遇到了right，就可以结束了！
        {
            if(nums[i]==0)
            {
                swap(nums[left+1],nums[i]);
                left++;
                i++;
            }
            else if(nums[i]==1)
            {
                i++;
            }
            else
            {
                swap(nums[right-1],nums[i]);
                right--;
            }
        }
        
    }
};

二、排序数组（快排的方法）

1、题目解析

题目链接：排序数组

2、算法原理

唯一需要知道的是用随机的方式选择基准元素：
（1）在最上面的函数排序之前先种一个随机数种子：srand(time(NULL));
（2）r=rand(); 其中：r%(right-left+1)是偏移量！

3、代码

class Solution 
{
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(NULL));// 种下一个随机数种子
        qsort(nums,0,nums.size()-1);
        return nums;
    }

    void qsort(vector<int>& nums,int l,int r)
    {
        if(l>=r) return;  // 递归结束条件

        // 优化：随机找一个 基准元素key
        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+1],nums[i]);
                left++;
                i++;
            }
            else if(nums[i]==key)
            {
                i++;
            }
            else
            {
                swap(nums[right-1],nums[i]);
                right--;
            }
        }
        qsort(nums,l,left);// 分别进行 左右区间 的递归！
        qsort(nums,right,r);
    }

    int getRandom(vector<int>& nums,int left,int right)
    {
        int r=rand();
        return nums[r%(right-left+1)+left];
    }

};

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

像这种：第K个最大、第K个最小、最小的k个数、最大的k个数 ->利用的都是topK的思想！

1、题目解析

题目链接：数组中的第K个最大元素

2、算法原理

第一步：对数组排序，划分区间，【l，left】【left+1，right-1】【right，r】

3、代码

class Solution 
{
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(NULL));// 随机数种子
        return qsort(nums,0,nums.size()-1,k);
    }

    // 快排的递归函数
    int qsort(vector<int>& nums,int l,int r,int k)
    {

        // 注意细节：极端情况的处理，当区间只有一个元素的时候，直接返回
        if(l==r) return nums[l];

        // 1、找一个基准元素 将数组分三块

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

        //2、对排好序的数组，进行分类处理讨论
        int c=r-right+1,b=right-left-1,a=left-l+1;
        if(c>=k) return qsort(nums,right,r,k);// 不断地递归循环，直到找到为止
        else if(b+c>=k) return key;
        else return qsort(nums,l,left,k-b-c);// 注意细节：在最小的区间找第（k-b-c）个最大元素

    }


    int getRandom(vector<int>& nums,int left,int right)
    {
        return nums[rand()%(right-left+1)+left];
    }
};

四、库存管理 III（原：剑指 Offer . 最小的k个数）

1、题目解析

题目链接：剑指 Offer . 最小的k个数

2、算法原理

这个题的解法跟上一个题的解法是完全一样的，用的都是数组分三块的思想，只不过上一个题返回的是个数，这个题返回的是一个整体的数组。

3、代码

class Solution 
{
public:
    vector<int> inventoryManagement(vector<int>& nums, int k) 
    {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1,k);
        return{nums.begin(),nums.begin()+k};

    }
    void qsort(vector<int>& nums,int l,int r,int k)
    {
        if(l>r) return;

        //1、随机找一个基准元素，根据基准元素将数组分三块
        int key= getRandom(nums,l,r);

        // 2、以key为标准，将数组分三块
        int left=l-1,right=r+1,i=l;
        while(i<right)
        {
            if(nums[i]<key) swap(nums[++left],nums[i++]);
            else if(nums[i]==key) i++;
            else swap(nums[--right],nums[i]);
        }

        // 3、分类讨论
        int a=left-l+1,b=right-left-1,c=r-right+1;
        if(a>k) qsort(nums,l,left,k);
        else if(a+b>=k) return ;
        else qsort(nums,right,r,k-a-b);

    }


    int getRandom(vector<int>& nums,int left,int right)
    {
        return nums[rand()%(right-left+1)+left];
    }
};