四大排序算法之归并排序

说明

为了自己学习方便,我这里总结了四大排序算法涵盖了七种排序算法

分类算法名称时间复杂度      空间复杂度稳定性
插入排序

直接插入排序

希尔排序

O(n^2)   O(1)

O(n^2/3)   O(1)

稳定

不稳定

选择排序

选择排序

堆排序

O(n^2)   O(1)

O(nlogn)  O(1)

不稳定

不稳定

交换排序

冒泡排序

快速排序

O(n^2)   O(1)

全部有序最坏O(n^2)    O(1)

稳定

不稳定

归并排序归并排序O(nlogn)  O(n)稳定

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

下面看代码

public static void mergeSort(int[] arr,int L,int R,int[] temp){
        if(arr.length==0 || arr.length==1){
            return;
        }
        if(L<R){
            //分为两半
            int mid=L+((R-L)>>1);
            //排左边
            mergeSort(arr,L,mid,temp);
            //排右边
            mergeSort(arr,mid+1,R,temp);
            //合并
            merge(arr,L,mid,R,temp);
        }


    }
//    合并两个有序数组  
    public static void merge(int[] arr,int L,int mid,int R,int[] temp){
        int i=L,j=mid+1;
        int m=mid,n=R;
        int k=0;
        while (i<=m && j<=n){
            //将两个数组中较小的加入temp
            if(arr[i]<arr[j]){
                temp[k++]=arr[i++];
            }else {
                temp[k++]=arr[j++];
            }
        }
        //一个数组已经遍历完了,另一个数组如果有元素直接加入temp
        while (i<=m){
            temp[k++]=arr[i++];
        }
        while (j<=n){
            temp[k++]=arr[j++];
        }
       //将temp中的元素覆盖到arr中
        for (int l = 0; l < k; l++) {
            arr[L+l]=temp[l];
        }
    }

需要注意的是,归并排序需要创建一个临时数组,空间复杂度为O(n)
 

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

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

相关文章

linux查看进程、端口

1、先查看进程pidps -ef | grep 进程名如果已知pid&#xff0c;想看详情&#xff0c;则用 ps -ef pid2、通过pid查看占用端口(mac)netstat -na | grep 端口netstat -nap tcp | grep 进程pidnetstat -nap udp | grep 进程pid不加tcp或者udp的话mac上会报错&#xff1a;netstat常…

基于ASP的反垃圾邮件管理系统的设计与实现

随着Internet的迅速普及&#xff0c;电子邮件以其快捷、方便、低成本的特点逐渐成为人们进行信息交流的主要媒介之一&#xff0c;但是随之而来的垃圾邮件也越来越泛滥。垃圾邮件占用了有限的存储、计算和网络资源&#xff0c;耗费了用户大量的处理时间&#xff0c;影响和干扰了…

程序员OKR学习法

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl OKR管理法 OKR&#xff08;Objectives and Key Results&#xff09;管理法是一种目标管理方法&#xff0c;旨在通过制定明确的目标和可量化的关键结果来帮助组织、团队和个人…

RocketMQ的架构图

文章目录RocketMQ 技术架构中有四大角色 NameServer 、Broker 、Producer 、Consumer 。我来向大家分别解释一下这四个角色是干啥的。 Broker&#xff1a; 主要负责消息的存储、投递和查询以及服务高可用保证。说白了就是消息队列服务器嘛&#xff0c;生产者生产消息到 Broker…

Hive实战 --- 电子商务消费行为分析

目录 数据结构 Customer表 Transaction表 Store表 Review表 上传数据 创建目录用于存放数据 把本地文件上传到HDFS上 创建外部表 创建数据库 创建表 数据清洗 对transaction_details中的重复数据生成新ID 过滤掉store_review中没有评分的数据 找出PII (personal …

【web前端初级课程】第八章 什么是事件?

目录 一、事件情况汇总 二、标签绑定 三、使用DOM0事件模型 四、使用DOM2事件模型 五、相关练习&#xff1a;图片切换 一、事件情况汇总 事件分为三部分&#xff1a;事件源&#xff1a;绑定事件的标签、事件对象&#xff1a;就是事件产生的相关数据、事件处理函数 二、标…

Java使用功能方法交换a,b的值,通过构造方法输出姓名、年龄、家庭地址

目录 前言 一、使用功能方法交换a&#xff0c;b的值 1.1运行流程&#xff08;思想&#xff09; 1.2代码段 1.3运行截图 二、通过构造方法输出姓名、年龄、家庭地址 1.1运行流程&#xff08;思想&#xff09; 1.2代码段 1.3运行截图 前言 1.因多重原因&#xff0c;所以我…

愚人节,聊聊那些正在坑人的“新型AI”

几年前的一个愚人节&#xff0c;我们和大家聊过AI技术被作为诈骗工具的情况。很不幸&#xff0c;当时讨论的一些苗头&#xff0c;现在都成了电诈犯罪中屡见不鲜的手段。更可气的是&#xff0c;随着AI技术与应用本身的发展&#xff0c;犯罪分子的AI手段不减反增。一些“新型AI”…

(七)Tomcat源码阅读:Host组件分析

一、概述 Host类中比较重要的类就是HostConfig其它类实现的功能和之前的组件差不多&#xff0c;这里就不多介绍了。 二、阅读源码 1、HostConfig &#xff08;1&#xff09;重要方法 lifecycleEvent&#xff1a; 根据对应的方法设置对应的属性&#xff0c;并调用对应的方…

自己写gpt的软件教程-国内最好的chatgpt软件

GPT-3是一种非常强大的自然语言处理技术&#xff0c;可以为用户生成高质量的文本内容。虽然GPT-3最初是为英文而设计的&#xff0c;但是近年来&#xff0c;GPT-3在中文领域也变得越来越流行。在本篇教程中&#xff0c;我们将详细介绍如何在GPT-3中生成中文内容。 一、准备工作 …

第二天并发篇

一、线程状态 1.新建&#xff08;New&#xff09;&#xff1a;创建线程对象时 2.就绪&#xff08;Runnable&#xff09;&#xff1a;线程调用start方法&#xff0c;有执行资格没有执行权 3.运行&#xff1a;当就绪状态时抢到cpu的执行权之后&#xff0c;进入运行状态 4.阻塞&am…

过程控制系统中的模块技术MTP

在过程自动化行业中&#xff0c;模块化设备概念近年来越来越受欢迎。其中最热门的是MTP。MTP称为模块类型封装&#xff0c;它是过程工业自动化技术用户协会&#xff08;NAMUR&#xff09;提出的过程自动化行业的模块化标准&#xff0c;通过这种模型&#xff0c;开发工作的重点从…

C++(Qt)软件调试---linux下生成/调试Core文件(3)

#软件调试 C(Qt)软件调试—linux下生成/调试Core文件&#xff08;3&#xff09; 文章目录C(Qt)软件调试---linux下生成/调试Core文件&#xff08;3&#xff09;前言1、C生成Core和使用GDB调试1、环境2、C生成Core文件3、使用gdb工具调试core可定位段错误位置&#xff1b;4、修…

【创作赢红包】你是真的“C”——C语言中文件操作函数使用的详细讲解【上篇】

你是真的“c”——C语言中文件操作函数使用的详细讲解~&#x1f60e;前言&#x1f64c;一、 为什么使用文件&#xff1a;&#x1f64c;二、 什么是文件&#xff1a;&#x1f64c;2.1 程序文件2.2 数据文件2.3 文件名3. 文件的打开和关闭3.1 文件指针3.2 文件的打开和关闭4. 文件…

【ansible】实施任务控制

目录 实施任务控制 一&#xff0c;循环&#xff08;迭代&#xff09;--- loop 1&#xff0c;利用loop----item循环迭代任务 2&#xff0c;item---loop循环案例 1&#xff0c;定义item循环列表 2&#xff0c;通过变量应用列表格式 3&#xff0c;字典列表&#xff08;迭代嵌套子…

一个ESP32小东西

之前发了ESP8266&#xff0c;有人评论说玩下ESP32然后就买了几个回来&#xff0c;当然&#xff0c;也想着和大家一起玩介绍下这个开发板开发板Github项目链接https://github.com/Xinyuan-LilyGO/T-QT把仓库的代码下载到本地我们可以用ESP-IDF和Arduino两个SDK来开发ESP32S3ESP-…

回溯算法思想、回溯算法解题模板与回溯算法题目索引(不断更新)

回溯算法 回溯算法是一种试探性的搜索算法&#xff0c;它在解决某些组合问题、优化问题、路径问题等&#xff0c;非常有效。回溯算法的核心思想是通过递归和深度优先搜索&#xff08;DFS&#xff09;来搜索问题的解空间。 细说一下这些问题&#xff1a; 组合问题&#xff1a;N…

初级网络工程师这30道面试题一定得会,建议小白收藏!

你好&#xff0c;这里是网络技术联盟站。 后台有小伙伴想让瑞哥整理一下初级网络工程师面试题&#xff0c;今天我整理出来了&#xff0c;针对初级网络工程师&#xff0c;我们在面试的时候主要考察的是基础概念&#xff0c;下面列举的希望大家可以收藏&#xff0c;平时多看看&a…

活动选择问题 | 贪心算法 1

贪心法是一种算法范式&#xff0c;它逐个构建解决方案&#xff0c;始终选择下一个提供最明显和最直接好处的部分。贪心算法用于优化问题。 如果问题具有以下属性&#xff0c;则可以使用 Greedy 解决优化问题&#xff1a; 在每一步中&#xff0c;我们都可以做出当前看起来最好…

MongoDB 6.0 (四)聚合操作

一、 聚合框架的作用 1. 什么是MongoDB 聚合框架 MongoDB 聚合框架(Aggregation Framework)是一个计算框架,它可以: • 作用在一个或几个集合上; • 对集合中的数据进行的一系列运算; • 将这些数据转化为期望的形式; 从效果而言,聚合框架相当于SQL 查询中的: …
最新文章