【算法】分治 - 归并排序

快乐的流畅：个人主页

个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

引言

分治的两大排序算法，一个是快速排序，另一个则是归并排序。形象地说，在处理数据的顺序方面，快速排序是先序遍历，而归并排序是后序遍历。

一、排序数组

思路：

• 递归出口：区间只有一个元素
• 分治：继续递归[begin, mid]，[mid + 1, end]两个区间
• 归并：合并两个有序数组
• 恢复：将临时数组tmp的数据，拷贝回原数组nums

class Solution
{
    vector<int> tmp;
public:
    void mergeSort(vector<int>& nums, int begin, int end)
    {
        if(begin == end) return;

        int mid = begin + (end - begin) / 2;
        mergeSort(nums, begin, mid);
        mergeSort(nums, mid + 1, end);

        int begin1 = begin, end1 = mid, begin2 = mid + 1, end2 = end, k = begin;
        while(begin1 <= end1 && begin2 <= end2)
        {
            if(nums[begin1] < nums[begin2]) tmp[k++] = nums[begin1++];
            else tmp[k++] = nums[begin2++];
        }

        while(begin1 <= end1) tmp[k++] = nums[begin1++];
        while(begin2 <= end2) tmp[k++] = nums[begin2++];

        for(int i=begin; i<=end; i++) nums[i] = tmp[i];
    }

    vector<int> sortArray(vector<int>& nums)
    {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

二、交易逆序对

思路：

1. 看到这道题，最简单的思路肯定是暴力枚举，两层for循环。但是，作为一道困难题，这么简单就被做出来岂不是太没面子了？所以这种暴力解法肯定是超时的。
2. 那么，这题为什么可以想到用归并排序呢？关键在于，归并排序中，两段区间都是有序的。根据这个有序性（单调性），我们可以利用同向双指针进行优化。
3. 这里有两种对称的优化思路：

• 升序，找某个元素之前，有多少元素比它大
  
  • 当nums[cur1] <= nums[cur2]时，cur1++
  • 当nums[cur1] > nums[cur2]时，cur1后面的元素都要大于nums[cur2]，所以可以一次统计多个逆序对（优化），ret += mid + 1 - cur1，cur2++
• 降序，找某个元素之后，有多少元素比它小
  
  • 当nums[cur1] <= nums[cur2]时，cur2++
  • 当nums[cur1] > nums[cur2]时，cur2后面的元素都要小于nums[cur1]，所以可以一次统计多个逆序对（优化），ret += end + 1 - cur2，cur1++

升序版本：

class Solution
{
    int ret;
    vector<int> tmp;
public:
    void mergeSort(vector<int>& nums, int begin, int end)
    {
        if(begin >= end) return;

        int mid = begin + (end - begin) / 2;
        mergeSort(nums, begin, mid);
        mergeSort(nums, mid + 1, end);

        int cur1 = begin, cur2 = mid + 1, k = begin;
        while(cur1 <= mid && cur2 <= end)
        {
            if(nums[cur1] <= nums[cur2]) tmp[k++] = nums[cur1++];
            else
            {
                tmp[k++] = nums[cur2++];
                ret += mid + 1 - cur1;
            }
        }

        while(cur1 <= mid) tmp[k++] = nums[cur1++];
        while(cur2 <= end) tmp[k++] = nums[cur2++];

        for(int i=begin; i<=end; i++) nums[i] = tmp[i];
    }

    int reversePairs(vector<int>& nums)
    {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

三、计算右侧小于当前元素的个数

思路：

1. 经过上道题求逆序对，我们总结了两种方法。而这道题，明显使用降序版本，找当前元素的后面有多少个小于它的。
2. 当然，除此之外，本题还有一大难点，便是找到了右侧小于当前元素的个数，如何找到该元素的原始下标。因为归并排序后，元素已经被打乱。
3. 所以，我们可以创建index数组，存储对应元素的原始下标。当元素排序时，index中的下标也跟着同步变化，这样就可以通过当前下标找到原始下标了。
4. 因为要给nums和index两个数组归并排序，所以分别要创建tmp和tmpi两个临时数组进行辅助。

class Solution
{
    vector<int> ret;
    int tmp[100005];
    int index[100005];
    int tmpi[100005];
public:
    void mergeSort(vector<int>& nums, int begin, int end)
    {
        if(begin >= end) return;

        int mid = begin + (end - begin) / 2;
        mergeSort(nums, begin, mid);
        mergeSort(nums, mid + 1, end);

        int cur1 = begin, cur2 = mid + 1, k = begin;
        while(cur1 <= mid && cur2 <= end)
        {
            if(nums[cur1] <= nums[cur2])
            {
                tmpi[k] = index[cur2];
                tmp[k++] = nums[cur2++];
            }
            else
            {
                ret[index[cur1]] += end + 1 - cur2;
                tmpi[k] = index[cur1];
                tmp[k++] = nums[cur1++];
            }
        }

        while(cur1 <= mid)
        {
            tmpi[k] = index[cur1];
            tmp[k++] = nums[cur1++]; 
        }
        while(cur2 <= end)
        {
            tmpi[k] = index[cur2];
            tmp[k++] = nums[cur2++];
        }
        for(int i=begin; i<=end; i++)
        {
            nums[i] = tmp[i];
            index[i] = tmpi[i];
        }
    }

    vector<int> countSmaller(vector<int>& nums)
    {
        int n = nums.size();
        ret.resize(n);
        for(int i=0; i<n; i++) index[i] = i;

        mergeSort(nums, 0, n - 1);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

四、翻转对

思路：

1. 本题和求逆序对很像，只不过条件变为nums[cur1] > 2 * nums[cur2]
2. 由于该条件和归并排序时合并两个有序数组不同，所以不能写在一起，而是要分开写。先计算翻转对，再进行归并。
3. 这里选取升序版本：
   • 当nums[left] <= 2 * nums[right]时，left++
   • 当nums[left] > 2 * nums[right]时，ret += mid + 1 - left，right++

class Solution
{
    int ret;
    int tmp[50005];
public:
    void mergeSort(vector<int>& nums, int begin, int end)
    {
        if(begin >= end) return;

        int mid = begin + (end - begin) / 2;
        mergeSort(nums, begin, mid);
        mergeSort(nums, mid + 1, end);

        int left = begin, right = mid + 1;
        while(left <= mid && right <= end)
        {
            //因为分类条件与归并不同，所以要分开写
            if(nums[left] <= 2 * (long long)nums[right]) left++;//强转long long，防止溢出
            else
            {
                ret += mid + 1 - left;
                right++;
            }
        }

        int cur1 = begin, cur2 = mid + 1, k = begin;
        while(cur1 <= mid && cur2 <= end)
        {
            if(nums[cur1] <= nums[cur2]) tmp[k++] = nums[cur1++];
            else tmp[k++] = nums[cur2++];
        }

        while(cur1 <= mid) tmp[k++] = nums[cur1++];
        while(cur2 <= end) tmp[k++] = nums[cur2++];
        for(int i=begin; i<=end; i++) nums[i] = tmp[i];
    }

    int reversePairs(vector<int>& nums)
    {
        mergeSort(nums, 0, nums.size() - 1);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

真诚点赞，手有余香