算法：分治思想处理快排递归以及快速选择/最小K个数问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法：分治思想处理快排递归以及快速选择/最小K个数问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法原理

分治的原理就是分而治之，从原理上讲，就是把一个复杂的问题划分成子问题，再将子问题继续划分，直到可以解决

实现思路

基于分治的原理进行快速排序，区别于传统的快速排序，这里对快速排序进行改良，成为更优先的三路划分算法，可以处理一些极端场景，使快速排序的适用性更加广泛，同时引出快速选择算法，用来搭配堆排序解决topk问题

典型例题

颜色分类

算法：分治思想处理快排递归以及快速选择/最小K个数问题,C++,# 算法,习题集,算法
本题和前面在双指针算法中做的移动0的解法类似，这里其实算法原理和快速排序优化的三路划分很相似，将数组中的区域划分为三个部分，分别为0，1，2，因此解决问题的时候要先想清楚如何解决，把数据量弄清楚

对于此题来说，算法思路就是如果遇到2，就把数据扔到最后，如果遇到0，就放到最前，那么1就会被天然的隔离到最中间的部分，这是可行的

快速排序优化

算法：分治思想处理快排递归以及快速选择/最小K个数问题,C++,# 算法,习题集,算法

根据上面的原理，可以改进快速排序，快速排序的弊端在于，当他要进行处理很多相同数据的时候，就遇到十分低效的情况，基于这个原因，可以在实现它的过程中利用到一些上面的想法，这样的算法思路其实也叫做三路划分

因此可以使用这个方法来解题，否则会超时

class Solution 
{
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(0));
        quicksort(nums,0,nums.size()-1);
        return nums;
    }
    void quicksort(vector<int>& nums,int left,int right)
    {
        if(left>=right)
        {
            return;
        }
        int key=numsrandom(nums,left,right);
        int i=left,begin=left-1,end=right+1;
        while(i<end)
        {
            if(nums[i]<key)
            {
                swap(nums[++begin],nums[i++]);
            }
            else if(nums[i]==key)
            {
                i++;
            }
            else
            {
                swap(nums[--end],nums[i]);
            }
        }
        quicksort(nums,left,begin);
        quicksort(nums,end,right);
    }
    int numsrandom(vector<int>& nums,int left,int right)
    {
        int keyi=rand()%(right-left+1)+left;
        return nums[keyi];
    }
};

基于快速排序的三路划分原理，可以引申出新的思想：快速选择问题

数组中最大的K个数

算法：分治思想处理快排递归以及快速选择/最小K个数问题,C++,# 算法,习题集,算法

看到这个题第一思想是使用堆排序，因为堆排序处理TopK问题是十分有效的，但是后面的限制条件，时间复杂度必须是O(N)的算法，因此这里并不能使用TopK算法

由于前面有快速排序的基础，因此这里可以引申出一个快速选择解法

首先看思路：

在快速排序的三路划分算法中，当划分结束后，整个数组会被天然的划分为下面三个部分：

算法：分治思想处理快排递归以及快速选择/最小K个数问题,C++,# 算法,习题集,算法

假设，我们这里让蓝色区域的记作C，红色区域记作B，棕色区域记作A

那如果我们要求的这个第k个数据落在蓝色区域，那么我们只需要在C这个单位长度内寻找一次即可，如果落在红色区域，那么要找的这个数据就是key，如果落在棕色区域，则只需要在A这个单位长度寻找一次即可

由此，就引申出了快速选择算法：基于快速排序从而引申出的快速选择

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

    int quicksort(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;
        
        // 2. 三路划分
        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 c=r-right+1;
        int b=(right-1)-(left+1)+1;
        if(c>=k)
        {
            return quicksort(nums,right,r,k);
        }
        else if(b+c>=k)
        {
            return key;
        }
        else
        {
            return quicksort(nums,l,left,k-b-c);
        }
    }

    int getrandom(vector<int>& nums,int l,int r)
    {
        return nums[rand()%(r-l+1)+l];
    }
};

时间复杂度分析较为复杂，但是是严格符合题目要求的，由此其实也看出了分治的思想核心，把一个大问题转换成小问题，直到最后转换成一个我们一下就能解决的问题，不断的缩小我们需要寻找的区间，这样最终就能找到我们需要的答案

最小的K个数

算法：分治思想处理快排递归以及快速选择/最小K个数问题,C++,# 算法,习题集,算法

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

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

        // 1. 选基准元素
        int key=getrandom(nums,l,r);
        int left=l-1,right=r+1,i=l;
        
        // 2. 三路划分
        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-1)-(left+1)+1;
        if(a>k)
        {
            quicksort(nums,l,left,k);
        }
        else if(a+b>=k)
        {
            return;
        }
        else
        {
            quicksort(nums,right,r,k-a-b);
        }
    }

    int getrandom(vector<int>& nums,int l,int r)
    {
        return nums[rand()%(r-l+1)+l];
    }
};