算法原理
分治的原理就是分而治之，从原理上讲，就是把一个复杂的问题划分成子问题，再将子问题继续划分，直到可以解决
实现思路
基于分治的原理进行快速排序，区别于传统的快速排序，这里对快速排序进行改良，成为更优先的三路划分算法，可以处理一些极端场景，使快速排序的适用性更加广泛，同时引出快速选择算法，用来搭配堆排序解决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个数不一定要有序，因此三路划分后可以直接进行条件判断，满足需求就可以跳出循环
总结
分治思想用以快速排序，可以引申出快速选择这个算法，而这个算法在实际应用中有很大的作用，对于解决前k个数或第k个数都有很大的算法意义，下篇会总结分治思想用以解决归并问题
