使用快排的思想就是 将一段区域分为3段，在选取一个基准元素key。找到该数了 并且cur1后面的值肯定都比cur2指向的值大。
分类讨论，遍历时候 如果nums[i]是0的话，交换swap(nums[++left],nums[i]) 并且都向后移动;如果是1，不用交换，i++继续向后移动；如果是2，交换右边的跟当前的swap(nums[right–],nums[i])，此时i不用向后移动，继续对当前交换后的数进行判断。cur2，分别指向left和right.一直遍历循环。说明cur2指向的值第一次比他大，cur1继续向后走， 当cur1指向的值比cur2大。找到该数之前，统计有多少个数比我大。一段区间，选取中间点，分别从左右两区间排序(根据题目要求决定升序降序)，排序完之后合并俩有序数组，再返回上一层。直到不走出边界位置。统计个数。

2.1排序数组

排序数组
题目描述：

讲解篇：
本体讲解下归并的方法。因为找的时候对数组降序排序了。定义3个指针，i指针遍历数组，left指针标记最左侧。b+c>=k，返回key值。

classSolution{inttmp[50010];public:intreversePairs(vector<int>&nums){returnmergesort(nums,0,nums.size()-1);}intmergesort(vector<int>&nums,intleft,intright){if(left>=right)return0;intres=0;//划分区间intmid=(left+right)>>1;res+=mergesort(nums,left,mid);res+=mergesort(nums,mid+1,right);intcur1=left,cur2=mid+1,i=left;//计算翻转对的数量while(cur1<=mid){while(cur2<=right&&nums[cur2]>=nums[cur1]/2.0)cur2++;if(cur2>right)break;res+=right-cur2+1;cur1++;}//合并  降序cur1=left,cur2=mid+1;while(cur1<=mid&&cur2<=right){tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur2++]:nums[cur1++];}//未处理完的时候while(cur1<=mid)tmp[i++]=nums[cur1++];while(cur2<=right)tmp[i++]=nums[cur2++];//还原数组for(intj=left;j<=right;j++){nums[j]=tmp[j];}returnres;}};

2.3交换逆序对总数

交换逆序对的总数

题目解析：
这里其实意思就是求数组中的逆序对个数。如果c>=k，在【right，r】区间找第k大元素。

草图：

代码篇：

classSolution{public:intfindKthLargest(vector<int>&nums,intk){//快排srand(time(NULL));returnqsort(nums,0,nums.size()-1,k);}intqsort(vector<int>&nums,intl,intr,intk){if(l==r)returnnums[l];//选随机标准数intkey=getRodm(nums,l,r);intleft=l-1,right=r+1,i=l;while(i<right){if(nums[i]<key)swap(nums[++left],nums[i++]);elseif(nums[i]==key)i++;elseswap(nums[--right],nums[i]);}//找出那个数intb=right-left-1,c=r-right+1;if(c>=k)returnqsort(nums,right,r,k);elseif(b+c>=k)returnkey;elsereturnqsort(nums,l,left,k-b-c);}intgetRodm(vector<int>&nums,intleft,intright){intr=rand();returnnums[r%(right-left+1)+left];}};

1.3