优选算法——分治（1）：三路快排

1.上期参考代码

classSolution{public:vector<int>missingTwo(vector<int>&nums){inttmp=0;for(inti=0;i<nums.size();i++){tmp^=nums[i];}for(inti=1;i<=nums.size()+2;i++){tmp^=i;}//此时tmp已经等于a^bintpos=0;while(1){if(tmp&(1<<pos))break;elsepos++;}inta=0;for(inti=0;i<nums.size();i++)if(nums[i]&(1<<pos))a^=nums[i];for(inti=1;i<=nums.size()+2;i++)if(i&(1<<pos))a^=i;tmp^=a;return{a,tmp};}};

2.本期知识点导图

3.本期要讲解的题目是

排序数组

要点：

• 不能使用内置函数，sort不能用（其实sort本质就是快排）
• 通过本题中两种快排算法，理解分治的思想
• 对于还不会基本的排序算法的同学可以

戳这里跳转到这个博主的讲解

了解一下基本的算法思想，有递归基础，学起来也快。

4.解题

4.1 快排

代码如下：

classSolution{public:vector<int>sortArray(vector<int>&nums){qsort(nums,0,nums.size()-1);returnnums;}voidqsort(vector<int>&nums,intleft,intright){if(left>=right)return;intkey=(left+right)/2;intmid=nums[key];intl=left-1,r=right+1;while(l<r){dol++;while(nums[l]<mid);dor--;while(nums[r]>mid);if(l<r)swap(nums[l],nums[r]);}qsort(nums,left,r);qsort(nums,r+1,right);}};

这个代码也能过，但是我们分析其时间复杂度，即普通快排的时间复杂度

普通快排的平均（随机）时间复杂度是O(NlogN)
最差情况即每次分区都把数组拆成「长度为 n−1 和 0/1 的两部分」（极端不平衡），递归层数是 n，每层处理需要 O(n)，总复杂度 O(n 2 )。

4.2三路快排

快排算法中，递归的每一层，我们是找一个值key，将数组分成两部分：值小于key，值大于key；

提到数组分块，不知到大家还有没有印象，我们在讲双指针的时候，第一道题就是数组分块：移动0（点击跳转）

两个指针，数组分成3块：未处理，已处理0，已处理非零，right不断向后遍历，left不断维护已处理部分的信息

双指针的好处就是通过指针遍历时的不回退性质，将遍历的的时间复杂度降至O(N)，但是这里并没有降幅时间复杂度，因为普通快排中也是通过不回退的双指针来遍历数组的。

区别：

三路快排，将数组分成了三个部分，相对于普通快排，当数组中存在大量重复元素的时候，使用这个三路快排，减少大量的遍历操作，仅仅推进i的向后遍历即可。视觉上呈现的效果应该是中间的区间越来越大，下次递归传入的区间越来越小，那么下次需要遍历的区间也会减小~，所以我们可以根据数据的特征来选择使用哪个快排。

关键思路：

我们观察快排中每一层递归做的事，其实就是将数组按照<k,=k,>k来分块，然后在这一层结束之前，还有第4块，也就是未处理的部分。

这样子就能把知识点串起来了~~快哉

与双指针算法类似，我们搞一个“三指针”，将数组分成4块：

在遍历的过程中，数组分块分布如上图

各参数和指针的作用：

• left和right：指定要排序的空间
• l：接受值小于key的元素，划定"<"区间
• r：接受值大于key的元素，划定">"区间
• i:遍历数组，处理未处理的元素，结合l和r划定"="区间，以及划定未处理的空间

注意：维护“>”区间的时候，与nums[i[交换的元素，也就是当前i位置的元素也是未处理的，与维护"<"区间的时候不同。

整体代码逻辑就是推动i遍历数组，维护好3个区间部分

5.下期要讲解的题目是：

数组中的第K个最大元素

6.嗟食

如果小编写的内容对佬有帮助，还请大佬点点三连加关注哦
佬的支持就是我前进的最大动力~

期待与佬的再次相遇~