前往小程序,Get更优阅读体验!
立即前往
发布
社区首页 >专栏 >【算法】归并排序

【算法】归并排序

作者头像
三三是该溜子
发布2025-01-13 08:17:11
发布2025-01-13 08:17:11
740
举报
文章被收录于专栏:该溜子的专栏

一:排序数组(归并排序)

912. 排序数组 - 力扣(LeetCode)

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

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

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

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

e3f23781ea5b4655ad2440fb37a9d21e.png
e3f23781ea5b4655ad2440fb37a9d21e.png
e39a2d6fc26d488e965c4f0759f5716f.png
e39a2d6fc26d488e965c4f0759f5716f.png
(1)代码注释详细版本
代码语言:javascript
复制
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;

        //3:把左边区间排个序,再把右边区间排个序
        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;
        // (3)分别对两个区间排序,放到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
复制
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;

        //3:把左边区间排个序,再把右边区间排个序
        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
00e101496a284a209c220c2fd464a8fa.png
40e16c21594e4ba293893ac9f5dcd2c8.png
40e16c21594e4ba293893ac9f5dcd2c8.png
4abf5db557444b8a9d94c53583042033.png
4abf5db557444b8a9d94c53583042033.png
代码语言:javascript
复制
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);

        // 3:一左一右的个数
        // 定义双指针
        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
复制
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数组需要更新的那个位置本身就有值

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

易错点:

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

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

3:降序排列,找比当前元素小的元素,是去右边数组中找那一堆

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

63291efed2b1443cb3aceb90c007929c.png
63291efed2b1443cb3aceb90c007929c.png
301fa07c1aa542e0b9376bb04de99d77.png
301fa07c1aa542e0b9376bb04de99d77.png
代码语言:javascript
复制
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];
        }

    }
}

四:计算翻转对个数

1e365292401b4332ae2edb61c2109c45.png
1e365292401b4332ae2edb61c2109c45.png

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

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

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

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

2:比较两道题的异同

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

a63936f0fe574fab81efd61fdec08f41.png
a63936f0fe574fab81efd61fdec08f41.png
06373bc5f69042e4a7935c1b20725639.png
06373bc5f69042e4a7935c1b20725639.png
243e22aae3d641c1b18dafcc4f11e579.png
243e22aae3d641c1b18dafcc4f11e579.png
b91efd14c6b346589f7072cf3210c52d.png
b91efd14c6b346589f7072cf3210c52d.png

3:降序版本

代码语言:javascript
复制
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
复制
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-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一:排序数组(归并排序)
    • (1)代码注释详细版本
    • (2)代码优化版本
  • 二:交易中的逆序对
  • 三:计算右侧小于当前元素的个数
  • 四:计算翻转对个数
    • 1:493翻转对,题目为什么统计结果和排序比较不分开的话,升序和降序都不能满足条件
    • 2:比较两道题的异同
    • 3:降序版本
    • 4:升序版本
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档