【算法】归并排序

2025-07-27 14:21:30

【算法】归并排序一：排序数组（归并排序） 912. 排序数组 - 力扣（LeetCode）归并排序，可以理解成后序遍历，把根的左子树和右子树分别排序好了之后，在合并为排序好的根快速排序，可以理解成前序遍历，把在根层选定一个key值划分好两个排序好的区间，分别在给左子树和右子树，女少啊！！！~~~易错点：int[] tem = new int[right-left+1] 而不是 new int

【算法】归并排序

一：排序数组（归并排序）

912. 排序数组 - 力扣（LeetCode）

归并排序，可以理解成后序遍历，把根的左子树和右子树分别排序好了之后，在合并为排序好的根

快速排序，可以理解成前序遍历，把在根层选定一个key值划分好两个排序好的区间，分别在给左子树和右子树，女少啊！！！~~~

易错点：int[] tem = new int[right-left+1] 而不是 new int[nums.length];

优化点：tem数组只是一个中间商，不用每次递归都new一个，给他提出来作为全局变量，首次进mergeSort的时候new一个就可以了，会节约不少的资源开销

ef2781ea5b4655ad2440fb7a9d21e.png

e9a2d6fc26d488e965c4f0759f5716f.png

（1）代码注释详细版本

代码语言：javascript代码运行次数：0运行复制

class Solution {
    public int[] sortArray(int[] nums) {
        //归并排序
        //传入的参数：数组，左边界，右边界
        int left = 0 , right = nums.length-1;
        mergeSort(nums,left,right);//对整个区间进行排序
        return nums;
    }
    public void mergeSort(int[] nums , int left , int right){
        //1:定义出口
        if(left >= right) return;

        //2：把数组分成两个区间 [left,mid] [mid+1,right]
        int mid = (left + right)/2;

        //:把左边区间排个序，再把右边区间排个序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        //4：合并排序好的两个区间

        // （1）使用一个tem数组来作为中间人存储排序好的结果
        // int[] tem = new int[nums.length];//new一个数组长度是当前划分的区间长度，这一点点代码不优化就跑不过去
        int[] tem = new int[right-left+1];

        // （2）定义双指针
        int cur1 = left , cur2 = mid + 1 , i = 0;
        // （）分别对两个区间排序,放到tem中
        while(cur1 <= mid && cur2 <= right){
            tem[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        // (4)处理没有遍历完的数组
        while(cur1 <= mid) tem[i++] = nums[cur1++];
        while(cur2 <= right) tem[i++] = nums[cur2++];

        // 5：将tem中的值copy给nums
        for(int j = left ; j <= right ; j++){
            nums[j] = tem[j-left];
        }
    }
}

（2）代码优化版本

代码语言：javascript代码运行次数：0运行复制

class Solution {
    int[] tem;
    public int[] sortArray(int[] nums) {
        //归并排序
        //传入的参数：数组，左边界，右边界
        int left = 0 , right = nums.length-1;
        tem = new int[nums.length];
        mergeSort(nums,left,right);
        return nums;
    }
    public void mergeSort(int[] nums , int left , int right){
        //1:定义出口
        if(left >= right) return;

        //2：把数组分成两个区间 [left,mid] [mid+1,right]
        int mid = (left + right)/2;

        //:把左边区间排个序，再把右边区间排个序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        //4：合并排序好的两个区间
        int cur1 = left , cur2 = mid + 1 , i = 0;
        while(cur1 <= mid && cur2 <= right){
            tem[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while(cur1 <= mid) tem[i++] = nums[cur1++];
        while(cur2 <= right) tem[i++] = nums[cur2++];

        // 5：将tem中的值copy给nums
        for(int j = left ; j <= right ; j++){
            nums[j] = tem[j-left];
        }
    }
}

二：交易中的逆序对

LCR 170. 交易逆序对的总数

易错点：ret的定义

00e101496a284a209c220c2fd464a8fa.png

40e16c21594e4ba2989ac9f5dcd2c8.png

4abf5db557444b8a9d94c5580420.png代码语言：javascript代码运行次数：0运行复制

class Solution {
    int[] tmp;//全局变量节约资源
    public int reversePairs(int[] record) {
        // 利用归并排序解决问题
        int n = record.length;
        tmp = new int[n];
        return mergeSort(record,0,n-1);

    }
    public int mergeSort(int[] nums , int left , int right){
        if(left >= right){
            return 0;
        }
        int ret = 0;//用来存储逆序对的个数
        // 1:选择一个中间节点，将数组划分为两个部分
        int mid = (left + right)/2;
        // [left,mid][mid+1,right]

        // 2：左半部分的个数 + 排序 + 右边部分的个数 + 排序
        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;
    }
}

降序

代码语言：javascript代码运行次数：0运行复制

while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]){  //试一下用大的部分在右半部分中（降序）
                tmp[i++] = nums[cur2++];
            }else{
                ret += right - cur2 + 1;
                tmp[i++] = nums[cur1++]; 
            }
        }

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

这道题的几个重点

1：中间数组需要创建两个，一个放元素，一个放元素的下标

2：创建结果数组ret，在归并的时候，ret是+=因为可能在归并过程中ret数组需要更新的那个位置本身就有值

：数组一定是呈现为降序排列

易错点：

1：在第一遍写这个代码的时候，没有注意到下标也需要创建一个中间数组，最后也需要合并更新

2：for循环注意，写代码的时候不要图快，稳最重要。

：降序排列，比当前元素小的元素，是去右边数组中那一堆

15. 计算右侧小于当前元素的个数

6291efed2b144cbaceb90c007929c.png

01fa07c1aa542e0b976bb04de99d77.png代码语言：javascript代码运行次数：0运行复制

class Solution {
    int[] index;
    int[] ret;
    int[] tmp;// 中间数组得搞两个分别记录数值和下标
    int[] tmpIndex;

    public List<Integer> countSmaller(int[] nums) {
        // 这道题的核心在于，需要的原下标下更改数值，创建一个index数组保存下标
        // 准备工作
        int n = nums.length;

        tmp = new int[n];
        index = new int[n];
        ret = new int[n];
        tmpIndex = new int[n];

        for (int i = 0; i < n; i++) {
            index[i] = i;
        }

        mergeSort(nums, 0, n - 1);

        List<Integer> l = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            l.add(ret[j]);
        }
        return l;

    }

    public void mergeSort(int nums[], int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;

        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // [left , mid] [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];
                ret[index[cur1]] += right - cur2 + 1; // 可能原来的位置上已经有数值了，所以是+=
                tmpIndex[i++] = index[cur1++];
            } else if (nums[cur1] <= nums[cur2]) {
                tmp[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];// 记录这个元素原来的下标,放到中转下标数组中
            }
        }
        while (cur1 <= mid) {
            tmp[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while (cur2 <= right) {
            tmp[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }
        // 合并数组(元素和下标都要合并)
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
            index[j] = tmpIndex[j - left];
        }

    }
}

四：计算翻转对个数

1e65292401b42ae2edb61c2109c45.png

1:49翻转对，题目为什么统计结果和排序比较不分开的话，升序和降序都不能满足条件

核心问题不在于比较，而在于不成立时，加入tmp数组中就不是降序或者升序了，下面举例展示

上面通过举例左半部分【7，9，10】右半部分【，4】说明了升序不能到一个就直接到一堆这样的算法，我来解释，例如 7 > 2* 因为是升序所以去左边统计共计有7,9,10三个符合条件的数字，7统计完，放入tmp中间数组中（tmp本应也是升序数组tmp【】）右指针移动到4，此时，7<2*4条件不满足，按照程序逻辑，不满足就把7扔进tmp，然后移动指针到9。tmp【,7】,继续按照逻辑执行9>4*2，此时可以到一堆9和10，两个符合条件。然后把4扔进tmp【,7,4】出问题了，tmp不是升序的了。

同理降序也是这个问题，这就是这道题核心的本质。需要把排序统计和合并数组两个逻辑分开处理的原因

2：比较两道题的异同

我明白了，为什么不能沿用计算右侧小于当前元素的个数这个题的思路，而要把比较和排序两个逻辑分开，举例如下。最核心的一点是比较的逻辑被破坏了，可能左边【10】，右边【8,4,1】

a696f0fe574fab81efd61fdec08f41.png

067bc5f69042e4a795c1b2072569.png

24e22aaed641c1b18dafcc4f11e579.png

b91efd14c6b46589f7072cf210c52d.png

：降序版本

代码语言：javascript代码运行次数：0运行复制

class Solution {
    int[] tmp;

    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];

        return mergeSort(nums, 0, n - 1);
    }

    public int mergeSort(int[] nums, int left, int right) {
        // 函数出口
        if (left >= right) {
            return 0;
        }

        // 划分两部分[left,mid][mid+1,right]
        int mid = (left + right) / 2;
        int ret = 0; // ret统计最后结果

        // 统计左边部分的翻转对，在统计右边的
        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]/2.0 <= nums[right]) {
                break;
            }
            while (cur2 <= right && nums[cur1]/2.0 <= nums[cur2]) {
                cur2++;
            }
            ret += right - cur2 + 1;
            cur1++;
        }

        // 合并排序好的两个部分
        cur1 = left;
        cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] > nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        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;
    }
}

4：升序版本

代码语言：javascript代码运行次数：0运行复制

class Solution {
    int[] tmp;

    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];

        return mergeSort(nums, 0, n - 1);
    }

    public int mergeSort(int[] nums, int left, int right) {
        // 函数出口
        if (left >= right) {
            return 0;
        }

        // 划分两部分[left,mid][mid+1,right]
        int mid = (left + right) / 2;
        int ret = 0; // ret统计最后结果

        // 统计左边部分的翻转对，在统计右边的
        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[mid]/2.0 <= nums[cur2]) {
                break;
            }
            while (cur1 <= mid && nums[cur1]/2.0 <= nums[cur2]) {
                cur1++;
            }
            ret += mid - cur1 + 1;
            cur2++;
        }

        // 合并排序好的两个部分
        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 - left];
        }
        return ret;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。原始发表：2025-01-1，如有侵权请联系 cloudcommunity@tencent 删除算法统计int排序数组

#感谢您对电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格的认可，转载请说明来源于"电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格

本文地址：http://www.dnpztj.cn/biancheng/1184086.html

本站网友肠镜检查	20分钟前发表
最后也需要合并更新2：for循环注意
本站网友全房	22分钟前发表
9
本站网友孕中期	15分钟前发表
mid + 1
本站网友 37度医学网	9分钟前发表
放到中转下标数组中 } } while (cur1 <= mid) { tmp[i] = nums[cur1]; tmpIndex[i++] = index[cur1++]; } while (cur2 <= right) { tmp[i] = nums[cur2]; tmpIndex[i++] = index[cur2++]; } // 合并数组(元素和下标都要合并) for (int j = left; j <= right; j++) { nums[j] = tmp[j - left]; index[j] = tmpIndex[j - left]; } } }四：计算翻转对个数1e65292401b42ae2edb61c2109c45.png1
本站网友厨房装修风水	20分钟前发表
不满足就把7扔进tmp
本站网友湿湿的梦	21分钟前发表
tmp不是升序的了
本站网友 eu7	24分钟前发表
right = nums.length-1; tem = new int[nums.length]; mergeSort(nums
本站网友本溪房产网	14分钟前发表
不满足就把7扔进tmp
本站网友滋阴补肾	6分钟前发表
比当前元素小的元素
本站网友郑州二手房出售	25分钟前发表
而在于不成立时
本站网友江苏男科	15分钟前发表
两个符合条件
本站网友网站友情链接	2分钟前发表
这一点点代码不优化就跑不过去 int[] tem = new int[right-left+1]; // （2）定义双指针 int cur1 = left

【算法】归并排序