分治算法——优选算法
本章我们要学习的是分治算法，顾名思义就是分而治之，把大问题分为多个相同的子问题进行处理，其中我们熟知的快速排序和归并排序用的就是分治算法，所以我们需要重新回顾一下这两个排序。
一、快速排序（三路划分）
1.算法思想：
首先从数列中确定一个需要排序的数（记为key），把所有key排到它的正确位置（即排序后它的位置），然后同样的方法，使用递归（分治思想）把小于key的区间与大于key的区间进行排序，直到这个区间不存在或只有一个元素时返回。
具体方法：从左到右遍历数组，并且我们使用三个变量（left，mid，right）把数组划分为四个区间，分别表示小于key，等于key，未遍历，大于key。而mid位置就是此时遍历到的数，判断这个数与key的关系，然后把它放在对应的区间。再用同样方法将大于key和小于key的区间排序。
注意：在此快速排序我使用了三路划分的优化方法，和对key取用随机值，这样比普通的快速排序效率要高得多，而且是一种很实用的分治算法。
2.代码实现：
vector<int> sortArray(vector<int>& nums) { srand((unsigned int)time(NULL)); dfs(0,nums.size()-1,nums); return nums; } void dfs(int n,int m,vector<int>& nums) { if(n>=m) return; int key=nums[n+rand()%(m-n+1)]; int left=n-1,right=m+1,mid=n; while(mid<right) { if(nums[mid]<key) swap(nums[++left],nums[mid++]); else if(nums[mid]==key) mid++; else swap(nums[mid],nums[--right]); } dfs(n,left,nums); dfs(right,m,nums); }二、归并排序
1.算法思想：
对于一个乱序的数组，我们可以把一分为二，先让两个小数组有序然后再将它们合并。那么如何让这两个小数组有序呢，同样的可以把它们分别再拆开，变成四个小组，然后继续一直往下拆，直到拆到只有一个元素，那么它必然是有序的，最后进行一一合并，这整个的思路有点像二叉树的后续遍历。
2.代码实现：
vector<int> tmp; vector<int> sortArray(vector<int>& nums) { tmp.reserve(nums.size()); dfs(0,nums.size()-1,nums); return nums; } void dfs(int left,int right,vector<int>& nums) { if(left>=right) return; int mid=(left+right)>>1; dfs(left,mid,nums); dfs(mid+1,right,nums); int p1=left,p2=mid+1; int i=left; while(p1<=mid&&p2<=right) tmp[i++]=nums[p1]<=nums[p2]?nums[p1++]:nums[p2++]; while(p1<=mid) tmp[i++]=nums[p1++]; while(p2<=right) tmp[i++]=nums[p2++]; for(int j=left;j<=right;j++) nums[j]=tmp[j]; }对于快速排序和归并排序，需要了解更多细节请参考下文：
【排序算法】—— 快速排序_快速排序方法-ZEEKLOG博客
三、快速选择算法
当我们看到这个题目的时候，可能脑子里很快想到用堆解决TopK问题，或者是使用排序来解决。 但这是一个面试题，以上两种解决方法都不足以让我们拿到offer。需要注意题目描述是任意顺序返回这k个数，而不是有序返回，那么我们就应该意识到应该还有更优的解决方法。
对于使用堆和排序，时间复杂度都为O(nlogn)，而这个题我们可以用快速选择算法，时间复杂度为O(n)，这是由快速排序延伸出的一个算法。同样使用分治思想。
算法思想：
class Solution { public: vector<int> smallestK(vector<int>& arr, int k) { srand((unsigned int)time(NULL)); dfs(0,arr.size()-1,arr,k); return {arr.begin(),arr.begin()+k}; } void dfs(int l,int r,vector<int>& arr,int k) { if(l>r) return; int key=arr[rand()%(r-l+1)+l]; int left=l-1,right=r+1,mid=l; while(mid<right) { if(arr[mid]<key) swap(arr[++left],arr[mid++]); else if(arr[mid]==key) mid++; else swap(arr[mid],arr[--right]); } int a=left-l+1,b=mid-left-1; if(k<a) dfs(l,left,arr,k); else if(k<=a+b) return; else dfs(right,r,arr,k-a-b); } };四、逆序对问题
关于这个题，最容易想到的就是暴力方法，双重循环，时间复杂度为O(n^2)，毫无疑问是通过不了这个题的，这个题我们可以利用归并排序来完成计数，时间复杂度为O(nlogn)。
算法思想：
class Solution { public: int count=0; vector<int> tmp; int reversePairs(vector<int>& record) { tmp.reserve(record.size()); dfs(0,record.size()-1,record); return count; } void dfs(int left,int right,vector<int>& nums) { if(left>=right) return; int mid=(left+right)>>1; dfs(left,mid,nums); dfs(mid+1,right,nums); int p1=left,p2=mid+1; int i=left; while(p1<=mid&&p2<=right) { if(nums[p1]<=nums[p2]) tmp[i++]=nums[p1++]; else count+=mid-p1+1, tmp[i++]=nums[p2++]; } while(p1<=mid) tmp[i++]=nums[p1++]; while(p2<=right) tmp[i++]=nums[p2++]; for(int i=left;i<=right;i++) nums[i]=tmp[i]; } };非常感谢您能耐心读完这篇文章。倘若您从中有所收获，还望多多支持呀！
