归并排序了解吗?手撕一个我看看?

目录

  • 1- 归并排序原理
    • 1-1 主要思想
    • 1-2 实现步骤
  • 2- 归并排序代码实现(双指针)
    • ⭐ 归并排序 ——实现思路
  • 3- ACM模式实现


1- 归并排序原理

1-1 主要思想

归并排序基于分治

    1. 将序列中待排序的数数字分为若干组,每个数字分为一组
    1. 将若干组两两合并,保证合并后的数组是有序的
    1. 重复第二步操作直到只剩下一组,排序完成

时间复杂度:

  • 平均时间复杂度:O(nlogn)

稳定性

  • 归并排序是稳定的

1-2 实现步骤

  • ① 确定分界点
    • 以整个数组的中间部分为分界点,分割mid = (l+r)/2
  • ② 递归排序左边和右边
  • ③ 归并(★难点)
    • 将两个有序的数组合并成一个有序的序列

2- 归并排序代码实现(双指针)

⭐ 归并排序 ——实现思路

在这里插入图片描述

    static void merge_sort(int[] q,int l,int r){
        if(l>=r) return;

        int mid = (l+r)/2;  //1. 选择分界点

        merge_sort(q,l,mid);  // 2. 递归排序左侧和右侧,使左右两边都有序 
        merge_sort(q,mid+1,r);

        int i = l;   // i 是左侧数组起点
        int j = mid+1;  // j是右侧数组起点
        int k = 0;  // k是代表已经合并的元素个数

        int[] tmp = new int[r-l+1]; //辅助数组
        while(i <= mid && j <= r){  //3.归并左右两端 
            if(q[i]<=q[j]) tmp[k++] = q[i++];
            else tmp[k++] = q[j++];
        }

        while(i<=mid) tmp[k++] = q[i++];  //检查左侧剩下没有循环完的元素 
        while(j<=r) tmp[k++] = q[j++];  //检查右侧剩下没有循环完的元素 

        for(i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j];  // 取出辅助数组中的元素
    }

3- ACM模式实现

public class merge {


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

        int mid = (l+r)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);

        // 单层逻辑
        int i = l;
        int j = mid+1;
        int k = 0;
        int[] tmp = new int[r-l+1];

        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<=r) tmp[k++] = nums[j++];

        // 将 tmp 赋值给 q
        for(i = l,j=0; i<=r ;i++,j++){
            nums[i] = tmp[j];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入数组长度");
        int n  = sc.nextInt();
        System.out.println("输入数组值");
        int[] num = new int[n];
        for(int i = 0 ; i < n;i++){
            num[i] = sc.nextInt();
        }
        mergeSort(num,0,num.length-1);
        for(int res:num){
            System.out.print(res+" ");
        }
    }
}


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/555192.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

3D模型处理的多进程并行【Python】

今天我们将讨论如何使用 Python 多进程来处理大量3D数据。 我将讲述一些可能在手册中找到的一般信息&#xff0c;并分享我发现的一些小技巧&#xff0c;例如将 tqdm 与多处理 imap 结合使用以及并行处理存档。 NSDT工具推荐&#xff1a; Three.js AI纹理开发包 - YOLO合成数据生…

【蓝桥杯2025备赛】素数判断:从O(n^2)到O(n)学习之路

素数判断:从O( n 2 n^2 n2)到O(n)学习之路 背景:每一个初学计算机的人肯定避免不了碰到素数&#xff0c;素数是什么&#xff0c;怎么判断&#xff1f; 素数的概念不难理解:素数即质数&#xff0c;指的是在大于1的自然数中&#xff0c;除了1和它本身不再有其他因数的自然数。 …

4.18作业

顺序栈&#xff1a; #include "seq_stack.h" seq_p creat_stack() //从堆区申请顺序栈的空间 {seq_p S(seq_p)malloc(sizeof(seq_stack));if(SNULL){printf("空间申请失败\n");return NULL;}bzero(S->data,sizeof(S->data));S->top-1;return S; …

OpenGL:图元

OpenGL的图元 点 GL_POINTS: 将顶点绘制成单个的点 线 GL_LINES:将顶点用于创建线段,2个点成为一条单独的线段。如果顶点个数是奇数,则忽略最后一个。 顶点:v0, v1, v2, v3, … , vn,线段:v0-v1, v2-v3, v4-v5, … , vn-1 - vn GL_LINE_STRIP:将顶点用于创建线段,…

在Linux系统中,禁止有线以太网使用NTP服务器进行时间校准的几种方法

目录标题 方法 1&#xff1a;修改NTP配置以禁止所有同步方法 2&#xff1a;通过网络配置禁用NTP同步方法 3&#xff1a;禁用NTP服务 在Linux系统中&#xff0c;如果想要禁止有线以太网使用NTP服务器进行时间校准&#xff0c;可以通过以下几种方法之一来实现&#xff1a; 方法 …

tcp网络编程——2

1.一个服务器只能有一个客户端连接&#xff08;下面代码&#xff09; ​​​​​​​tcp网络编程&#xff08;基础&#xff09;-CSDN博客 2.一个服务器可以有多个客户端连接&#xff08;多线程&#xff09; server端创建多个线程&#xff0c;每个线程与不同的client端建立连…

代码签名证书的作用及申请

代码签名证书新兴的数字证书的一种&#xff0c;应用范围相对于传统的数字证书而言要稍微少一些。用于验证软件代码的来源和完整性&#xff0c;并提供了一种防止代码被篡改或损坏的机制。常用于软件开发上&#xff0c;代码签名证书由签名证书公钥和私钥证书两部分组成&#xff0…

day05-Elasticsearch01

1.初识elasticsearch 1.1.了解ES 1.1.1.elasticsearch的作用 elasticsearch 是一款非常强大的开源搜索引擎&#xff0c;具备非常多强大功能&#xff0c;可以帮助我们从海量数据中快速找到需要的内容 例如&#xff1a; 在 GitHub 搜索代码在电商网站搜索商品在百度搜索答案在打…

【工位ubuntu的配置】补充

软件 安装桌面图标的问题 登录密码 root的密码为&#xff1a;19980719 按照如下的链接进行配置&#xff1a; https://blog.csdn.net/zhangmingfie/article/details/131102331?spm1001.2101.3001.6650.3&utm_mediumdistribute.pc_relevant.none-task-blog-2%7Edefault%7E…

永久免费次数ChatGPT国内镜像网站【强烈建议收藏】

gctohttps://chat.tomyres.com/#/pages/web/index?n0 觉得分享的网站好用的话&#xff0c;记得点赞收藏哦。

lettcode179.最大数

问题描述&#xff1a; 给定一组非负整数 nums&#xff0c;重新排列每个数的顺序&#xff08;每个数不可拆分&#xff09;使之组成一个最大的整数。 注意&#xff1a;输出结果可能非常大&#xff0c;所以你需要返回一个字符串而不是整数。 示例一&#xff1a; 输入nums [10…

街景图片语义分割后像素类别提取,用于计算各种指标。

语义分割代码见之前博文&#xff08;免费&#xff09;&#xff1a;deeplabv3街景图片语义分割&#xff0c;无需训练模型&#xff0c;看不懂也没有影响&#xff0c;直接使用。cityscapes 语义分割之后&#xff0c;如下图&#xff0c;想要统计各类像素所占的比例&#xff0c;用于…

2024 MathorCup C 题 物流网络分拣中心货量预测及人员排班

一、问题重述 电商物流网络在订单履约中由多个环节组成&#xff0c;图1是一个简化的物流网络示意图。其中&#xff0c;分拣中心作为网络的中间环节&#xff0c;需要将包裹按照不同流向进行分拣并发往下一个场地&#xff0c;最终使包裹到达消费者手中。分拣中心管理效率的提升&…

初识 React:安装和初步使用指南

文章目录 前言一、React 是什么&#xff1f;1.组件化开发2.虚拟 DOM3.单向数据流4.生态系统丰富 二、安装1.准备工作2.下载react 三、探索 React 应用总结 前言 在当今的 Web 开发领域&#xff0c;React 已经成为了一个备受推崇的技术。它的组件化、灵活性和高效性使得它成为了…

MySQL中InnoDB的行级锁

InnoDB 实现了以下两种类型的行锁。 共享锁&#xff08;S&#xff09;&#xff1a;又称为读锁&#xff0c;简称S锁&#xff0c;共享锁就是多个事务对于同一数据可以共享一把锁&#xff0c;都能访问到数据&#xff0c;但是只能读不能修改。 排他锁&#xff08;X&#xff09;&am…

时间同步服务项目练习

一.配置server主机要求如下&#xff1a; 1.server主机的主机名称为 ntp_server.example.com 2.server主机的IP为&#xff1a; 172.25.254.100 3.server主机的时间为1984-11-11 11&#xff1a;11&#xff1a;11 4.配置server主机的时间同步服务要求可以被所有人使用 更改主机名…

Android开发基础:Activity之间的跳转 向下一个Activity传递数据 给上一个Activity返回数据

目录 一&#xff0c;使用Intent在Activity之间跳转 1.显示使用Intent 2.隐式使用Intent 二&#xff0c;携带数据的跳转 1.Bundle 三&#xff0c;返回数据给上一个Activity 1.registerForActivityResult 一&#xff0c;使用Intent在Activity之间跳转 一个Android应用中包…

APEX开发过程中需要注意的小细节5.5

oracle保留小数点后两位的函数 在日常开发中经常用到百分比做数据对比&#xff0c;但是有可能得到的数据是一个多位小数&#xff0c;结果如下所示&#xff1a; 如果想截取部分小数如保留小数点后两位可以怎么做呢&#xff1f; 在Oracle中&#xff0c;可以使用ROUND函数来四舍…

请警惕,这10本期刊已被SCI剔除,部分涉嫌灌水

科睿唯安于4月15日更新了SCIE、SSCI、AHCI、ESCI四大数据库最新收录期刊目录。 2024年第一版——2024年1月24日更新 2024年第二版——2024年2月19日更新 2024年第三版——2024年3月18日更新 2024年第四版——2024年4月15日更新 本次目录中共收录期刊23368本。 【SCIE数据…

档案集中管理的痛点怎么解决?

档案集中管理可能面临的痛点包括以下几个方面&#xff1a; 1. 档案分类和整理困难&#xff1a;档案集中管理会面临大量档案的分类和整理工作&#xff0c;可能导致混乱和困难。 解决方法&#xff1a; - 建立统一的档案分类规范和流程&#xff0c;确保所有档案都能按照规定的方式…