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

一、快排

使用快排的思想就是 将一段区域分为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;
    }
};

总结;
我们在写归并排序题时候会发现都会有相同之处。但是对于不同的题，具体问题得具体分析。归并排序的空间复杂度：O(n)，因为在合并过程中需要额外的空间来存储临时数组。时间复杂度为O(n log n）