【水调歌头·排序篇】--体验快排与归并的奥妙

快排算法篇

一、快排
- 1 .1颜色分类
- 1.2数组中第k个最大元素
二、归并排序
- 2.1排序数组
- 2.2翻转对
- 2.3交换逆序对总数

在这里插入图片描述

一、快排

使用快排的思想就是将一段区域分为3段，在选取一个基准元素key。让这三段分别小于key,等于key，大于key.

1 .1颜色分类

颜色分类
在这里插入图片描述

由于本体只会出现3个数字，并且结果要求输出 0，1，2这样的。很容易解出来。

这里使用的思想就是数组划分三段。定义3个指针，i指针遍历数组，left指针标记最左侧。right标记最右侧。
分类讨论，遍历时候如果nums[i]是0的话，交换swap(nums[++left],nums[i]) 并且都向后移动;如果是1，不用交换，i++继续向后移动；如果是2，交换右边的跟当前的swap(nums[right–],nums[i])，此时i不用向后移动，继续对当前交换后的数进行判断。

在这里插入图片描述

代码片：

class Solution {
public:void sortColors(vector<int>& nums) {int n=nums.size();int left=-1,right=n,i=0;while(i<right){if(nums[i]==0)  swap(nums[++left],nums[i++]);else if(nums[i]==1) i++;else if(nums[i]==2) swap(nums[--right],nums[i]);}}
};

1.2数组中第k个最大元素

数组中的第k个最大元素

这里使用的快排的思想。我们先选个随机标准数key，根据key值将数组分三块，小于key值放最左边，等于key值放右边，大于key值放最右边。题目要求求第k大元素，这个k可能落在这三个其中某一块区域。我们得确定k落在哪个区域，我们设第一个区域元素有a个，第二个区域有b个，第三个区域有c个。如果c>=k，在【right，r】区间找第k大元素。（因为最右边都是大的元素，大的元素有c个，如果第k大比c小的话，那第k大元素一定落在该区域）。b+c>=k，返回key值。以上都不成立，就在第一个区间找第k-b-c大元素（因为我们要在整个区间找第k大元素，但是大元素都不是我们要的结果，接下来在这个小区间时候，要把大区间元素个数抛弃掉）。

草图：

在这里插入图片描述

代码篇：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {//快排srand(time(NULL));return qsort(nums,0,nums.size()-1,k);}int qsort(vector<int>& nums,int l,int r,int k){if(l==r)    return nums[l];//选随机标准数int key=getRodm(nums,l,r);int left=l-1,right=r+1,i=l;while(i<right){if(nums[i]<key)   swap(nums[++left],nums[i++]);else if(nums[i]==key)   i++;else swap(nums[--right],nums[i]);}//找出那个数int b=right-left-1,c=r-right+1;if(c>=k)  return qsort(nums,right,r,k);else if(b+c>=k)   return key;else return qsort(nums,l,left,k-b-c);}int getRodm(vector<int>& nums,int left,int right){int r=rand();return nums[r%(right-left+1)+left]; }
};

1.3

二、归并排序

归并排序，也用到了递归思想。一段区间，选取中间点，分别从左右两区间排序(根据题目要求决定升序降序)，排序完之后合并俩有序数组，再返回上一层。在这里插入图片描述

2.1排序数组

排序数组
题目描述：
在这里插入图片描述

讲解篇：
本体讲解下归并的方法。我们将数组分为两部分。[left,mid] [mid+1,right].定义俩指针 cur1 、 cur2，分别指向两个区域的开始位置。因为这道题本身要求是返回一个升序数数列。所以我们直接在合并俩有序数组这一步处理，如果cur1小于cur2值，将nums[cur1]赋给新数组，然后cur1向后移动，移动到一个新数，再去比较。否则，反之。最后将排序tmp中的数给到nums数组中。

草图：
在这里插入图片描述

代码篇：

class Solution 
{vector<int> tmp;
public:vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergesort(nums,0,nums.size()-1);return nums;}void mergesort(vector<int>& nums,int left,int right){if(left>=right) return ;//选择中间点划分区间int mid=(left+right)>>1;//[left,mid],[mid+1,right]//2\把左右区间排序mergesort(nums,left,mid);mergesort(nums,mid+1,right);//3、合并两个有序数组int cur1=left,cur2=mid+1,i=0;while(cur1<=mid && cur2<=right){tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];}//4处理没有遍历完的数组while(cur1<=mid)    tmp[i++]=nums[cur1++];while(cur2<=right)  tmp[i++]=nums[cur2++];//for(int i=left;i<=right;i++){nums[i]=tmp[i-left];}}
};

2.2翻转对

翻转对

本题的解题思路用到的是归并法。题目的意思是计算当前元素后面有多少数2倍比我还小。将该数组划分为两段，定义俩个区间的指针，先固定cur1，让cur2向后遍历，如果当前数2倍比cur1值大，继续向后遍历寻找。如果刚好比cur1小。那么cur2后面的数肯定也比cur1小。因为找的时候对数组降序排序了。剩下的操作都是归并排序里通用的思路。

在这里插入图片描述

class Solution {int tmp[50010];
public:int reversePairs(vector<int>& nums) {return mergesort(nums,0,nums.size()-1);}int mergesort(vector<int>& nums,int left,int right){if(left>=right) return 0;int res=0;//划分区间int mid=(left+right)>>1;res+=mergesort(nums,left,mid);res+=mergesort(nums,mid+1,right);int cur1=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(int j=left;j<=right;j++){nums[j]=tmp[j];}return res;}
};

2.3交换逆序对总数

交换逆序对的总数
在这里插入图片描述

题目解析：
这里其实意思就是求数组中的逆序对个数。方法还是归并排序。

这里使用的是归并的思想。将一段数组分成两块进行分析（这俩块按升序排序）。定义俩指针cur1、cur2，分别指向left和right.一直遍历循环。找到该数之前，统计有多少个数比我大。当cur2当前的值比cur1当前的值大或者等于。说明cur2指向的值第一次比他大，cur1继续向后走，当cur1指向的值比cur2大。找到该数了并且cur1后面的值肯定都比cur2指向的值大。统计个数。然后继续向后走。直到不走出边界位置。

在这里插入图片描述

class Solution 
{vector<int>tmp;
public:int reversePairs(vector<int>& nums) {tmp.resize(nums.size());return mergesort(nums,0,nums.size()-1);}int  mergesort(vector<int>& nums,int left,int right){if(left>=right) return 0;int ret=0;int mid=(left+right)>>1;//左边的个数+排序+右边的个数+排序ret+=mergesort(nums,left,mid);ret+=mergesort(nums,mid+1,right);//一左一右的个数int cur1=left,cur2=mid+1,i=0;while(cur1<=mid && cur2<=right){if(nums[cur1]<=nums[cur2])  tmp[i++]=nums[cur1++];else{ret+=mid-cur1+1;tmp[i++]=nums[cur2++];}}//4、处理下排序while(cur1<=mid) tmp[i++]=nums[cur1++];while(cur2<=right)  tmp[i++]=nums[cur2++];//for(int j=left;j<=right;j++){nums[j]=tmp[j-left];}return ret;}
};