本章我们要学习的是分治算法，顾名思义就是分而治之，把大问题分为多个相同的子问题进行处理，其中我们熟知的快速排序和归并排序用的就是分治算法，所以我们需要重新回顾一下这两个排序。

一、快速排序（三路划分）

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
        {
            if(nums[mid]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];
    }

对于快速排序和归并排序，需要了解更多细节请参考下文：

【排序算法】—— 快速排序_快速排序方法-CSDN博客

【排序算法】—— 归并排序-CSDN博客

三、快速选择算法

        当我们看到这个题目的时候，可能脑子里很快想到用堆解决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
        {
            if(arr[mid]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(kdfs(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];
    }
};

非常感谢您能耐心读完这篇文章。倘若您从中有所收获，还望多多支持呀！