算法原理
分治的原理就是分而治之，从原理上讲，就是把一个复杂的问题划分成子问题，再将子问题继续划分，直到可以解决
实现思路
基于分治的原理进行快速排序，区别于传统的快速排序，这里对快速排序进行改良，成为更优先的三路划分算法，可以处理一些极端场景，使快速排序的适用性更加广泛，同时引出快速选择算法，用来搭配堆排序解决topk问题
典型例题
颜色分类
本题和前面在双指针算法中做的移动0的解法类似，这里其实算法原理和快速排序优化的三路划分很相似，将数组中的区域划分为三个部分，分别为0，1，2，因此解决问题的时候要先想清楚如何解决，把数据量弄清楚
对于此题来说，算法思路就是如果遇到2，就把数据扔到最后，如果遇到0，就放到最前，那么1就会被天然的隔离到最中间的部分，这是可行的
快速排序优化
根据上面的原理，可以改进快速排序，快速排序的弊端在于，当他要进行处理很多相同数据的时候，就遇到十分低效的情况，基于这个原因，可以在实现它的过程中利用到一些上面的想法，这样的算法思路其实也叫做三路划分
因此可以使用这个方法来解题，否则会超时
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个数
看到这个题第一思想是使用堆排序，因为堆排序处理TopK问题是十分有效的，但是后面的限制条件，时间复杂度必须是O(N)的算法，因此这里并不能使用TopK算法
由于前面有快速排序的基础，因此这里可以引申出一个快速选择解法
首先看思路：
在快速排序的三路划分算法中，当划分结束后，整个数组会被天然的划分为下面三个部分：
假设，我们这里让蓝色区域的记作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个数
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];
}
};
对于这个题来说，解法多种多样，可以采用很多方法，topk，直接排序，快速选择，这里依旧选择快速选择来写
原理和前面类似，由于返回的是前k个数不一定要有序，因此三路划分后可以直接进行条件判断，满足需求就可以跳出循环文章来源：https://www.toymoban.com/news/detail-690038.html
总结
分治思想用以快速排序，可以引申出快速选择这个算法，而这个算法在实际应用中有很大的作用，对于解决前k个数或第k个数都有很大的算法意义，下篇会总结分治思想用以解决归并问题文章来源地址https://www.toymoban.com/news/detail-690038.html
到了这里，关于算法：分治思想处理快排递归以及快速选择/最小K个数问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
