归并排序

题目描述

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

912. 排序数组 https://leetcode.cn/problems/sort-an-array/

数据范围
1≤n≤100000
在这里插入图片描述

解法

class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        mergeSort(nums, 0, n - 1);
        return nums;
    }

    public void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int mid = l + r >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        int[] tmp = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) tmp[k++] = nums[i++];  // 归并排序是稳定的
            else tmp[k++] = nums[j++];
        }
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= mid) tmp[k++] = nums[j++];

        for (i = 0; i < k; ++i) nums[l + i] = tmp[i];
    }
}

讲解

mergeSort 和快排不同的是，先递归排序，然后进行后续的操作。（即先分开，再归并，合二为一）

e.g.
在这里插入图片描述
由于左边和右边的子数组都排好了，所以递归排序之后的操作相当于是合并两个排序好的数组，这里使用双指针算法即可。使用两个指针从头遍历两个数组，哪个小取哪个放入结果。

逆序对的数量（归并排序的思路）

剑指 Offer 51. 数组中的逆序对 https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

题目描述

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

数据范围
1 ≤ n ≤ 100000，
数列中的元素的取值范围 [1,109]。

在这里插入图片描述

解法

class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        return mergeSort(nums, 0, n - 1);
    }

    public int mergeSort(int[] nums, int l, int r) {
        if (l >= r) return 0;
        int mid = l + r >> 1;
        int res = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);
        int[] tmp = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else {
                tmp[k++] = nums[j++];
                res += mid - i + 1;
            }
        }
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];
        for (i = 0; i < k; ++i) nums[l + i] = tmp[i];
        return res;
    }
}