数据结构与算法-归并排序

引言

        在计算机科学的广阔领域中,数据结构与算法犹如两大基石,支撑着软件系统高效运行。本文将深度剖析一种基于分治策略的排序算法——归并排序,并探讨其原理、实现步骤以及优缺点,以期帮助读者深入理解这一高效的排序方法。

一、什么是归并排序?

        归并排序(Merge Sort) 是由约翰·冯·诺依曼于1945年提出的,它采用“分而治之”的思想,将待排序序列不断地分割成小部分,直到每个部分只剩下一个元素为止。然后对这些小部分进行排序,最后通过合并操作将已排序的小部分组合成一个完整的有序序列。

二、归并排序详细步骤

  1. 分解:将原始序列递归地拆分成两半,直到每部分仅包含一个元素,此时认为是有序的。

  2. 排序子序列:对上述得到的每一个子序列进行排序。由于它们只有一个元素,所以天然有序。

  3. 合并:将两个已经排序好的子序列合并为一个有序序列。这个过程采用合并操作,比较两个子序列中的最小元素,将较小者放入新数组,直至所有元素都被处理完毕。

三、归并排序的时间复杂度与空间复杂度分析

  • 时间复杂度:无论输入的数据如何分布,归并排序都能保证O(n log n)的时间复杂度,这是因为每次都将问题规模缩小一半,并且合并操作需要线性时间。

  • 空间复杂度:归并排序不是原地排序算法,它需要额外的空间来存储临时结果,因此其空间复杂度为O(n),其中n为待排序序列的长度。

四、归并排序的优缺点

优点

  • 稳定排序算法,对于含有相等元素的序列,排序后相对顺序不变。
  • 性能稳定,无论输入数据是否有序,其时间复杂度均为O(n log n),适用于大规模数据排序。

缺点

  • 需要额外的内存空间用于合并操作,不适用于内存资源有限的情况。
  • 由于采用了递归实现,当数据规模较大时可能导致较深的递归栈,对系统资源要求较高。

五、归并排序的图解过程  

 

图解小结 

        归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略(分治法将问题分为成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案修补在一起,即分而治)。

六、归并排序的代码实践 

1.合并方法

    //    合并方法

    /**
     * @param arr   排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param right 右边索引
     * @param mid   中间索引
     * @param temp  中转数组
     */
    public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
        int i = left;      //初始化i,表示左边有序序列的初始索引
        int j = mid + 1;   //初始化j,表示右边有序序列的初始索引
        int t = 0;         //指向temp数组的当前索引

//        (一)
//        先把左右两边(有序)的数组按照规则填充到temp数组
//        直到左右两边的有序序列,有一边处理完毕为止
        while (i <= mid && j <= right) {
//            如果左边的有序序列当前元素小于等于右边的有序序列当前元素
//            即将左边的元素加入到中转数组
//            然后t++ i++
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else {
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }
//        (二)
//        把剩余数据一边的数据依次全部填入到temp
        while (i <= mid) {   //左边的有序序列还有剩余的
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) {   //右边的有序序列还有剩余的
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
//        (三)
//        拷贝temp数组到arr
        t = 0;
        int tempLift = left;
        while (tempLift <= right) {
            arr[tempLift] = temp[t];
            t += 1;
            tempLift += 1;
        }
    }

2.分+合方法 

    //    分 + 合方法
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
//           向左递归分解
            mergeSort(arr, left, mid, temp);
//            向右递归分解
            mergeSort(arr, mid + 1, right, temp);
//            到合并
            merge(arr, left, right, mid, temp);
        }
    }

七、总结   

        尽管归并排序在空间效率上略逊于原地排序算法,但在许多实际场景下仍被广泛采用。例如,在大量数据的离线处理任务中,如数据库管理系统、大数据计算平台等,归并排序凭借其稳定的性能和良好的可扩展性成为首选排序方法之一。此外,归并排序也是许多其他高级排序算法(如堆排序结合归并排序形成的归并排序改进版本)的基础组成部分。

        归并排序作为一种典型的分治算法,通过巧妙地运用“分治”策略,成功解决了大规模数据排序的问题。虽然在某些特定条件下存在一定的局限性,但其内在逻辑简洁明了,易于理解和实现,且在实践中具有较高的实用价值。通过对归并排序的学习和研究,我们可以深刻理解分治策略在解决复杂问题时的优越性,并为今后设计和优化算法提供重要启示。

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

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

相关文章

用开发CesiumJS模拟飞机飞行应用(一,基本功能)

本部分向您展示如何构建您的第一个 Cesium 应用程序&#xff0c;以可视化模拟从旧金山到哥本哈根的真实航班&#xff0c;并使用 FlightRadar24收集的雷达数据。您将学习如何&#xff1a; 在网络上设置并部署您的 Cesium 应用程序。 添加全球 3D 建筑物、地形和图像的基础图层。…

MySQL 学习笔记(基础篇 Day2)

「写在前面」 本文为黑马程序员 MySQL 教程的学习笔记。本着自己学习、分享他人的态度&#xff0c;分享学习笔记&#xff0c;希望能对大家有所帮助。推荐先按顺序阅读往期内容&#xff1a; 1. MySQL 学习笔记&#xff08;基础篇 Day1&#xff09; 目录 3 函数 3.1 字符串函数 3…

PostgreSQL开发与实战(6.2)体系结构2

作者&#xff1a;太阳 二、逻辑架构 graph TD A[database] -->B(schema) B -->C[表] B -->D[视图] B -->E[触发器] C -->F[索引] tablespace 三、内存结构 Postgres内存结构主要分为 共享内存 与 本地内存 两部分。共享内存为所有的 background process提供内…

VI-ORBSLAM2编译运行

ORB-SLAM2编译运行 源码地址电脑配置环境配置编译轨迹保存为tum格式运行结果Euroc数据集 源码地址 源码链接&#xff1a;https://github.com/jingpang/LearnVIORB 电脑配置 Ubuntu 18.04 ROS Melodic GTSAM 4.0.2 CERES 1.14.0 pcl1.8vtk8.2.0opencv3.2.0 环境配置 之前…

简易版手淘视频播放器开发心路历程

需求背景 简单描述一下这个功能&#xff1a;在一个走马灯组件里面第一屏是一个视频&#xff0c;第二屏第三屏是图片&#xff0c;点击播放视频&#xff0c;播放过程中滚动窗口&#xff0c;视频 fixed 在窗口顶部&#xff0c;回到顶部&#xff0c;视频还原&#xff0c;两个窗口视…

Aigtek:功率放大器的选型技巧有哪些

功率放大器在电子设备中扮演着重要的角色&#xff0c;它能够将输入信号放大到所需要的功率水平。在选择功率放大器时&#xff0c;我们需要考虑多个因素&#xff0c;包括功率需求、频率响应、失真和稳定性等。本文将介绍功率放大器选型的一些技巧&#xff0c;帮助您找到适合的功…

基于OpenCV的图形分析辨认05(补充)

目录 一、前言 二、实验内容 三、实验过程 一、前言 编程语言&#xff1a;Python&#xff0c;编程软件&#xff1a;vscode或pycharm&#xff0c;必备的第三方库&#xff1a;OpenCV&#xff0c;numpy&#xff0c;matplotlib&#xff0c;os等等。 关于OpenCV&#xff0c;num…

java基础-锁之volatilesynchronized

文章目录 volatilevolatile内存语义volatile的可见性volatile无法保证原子性volatile禁止重排优化硬件层的内存屏障volatile内存语义的实现下面是基于保守策略的JMM内存屏障插入策略。下面是保守策略下&#xff0c;volatile写插入内存屏障后生成的指令序列示意图下图是在保守策…

数据结构——lesson6二叉树基础

前言 hellohello~这里是土土数据结构学习笔记&#x1f973;&#x1f973; &#x1f4a5;个人主页&#xff1a;大耳朵土土垚的博客 &#x1f4a5; 所属专栏&#xff1a;数据结构学习笔记 &#x1f4a5;对于数据结构顺序表链表有疑问的都可以在上面数据结构的专栏进行学习哦~感…

JuiceSSH结合Cpolar实现公网远程SSH访问内网Linux系统

文章目录 1. Linux安装cpolar2. 创建公网SSH连接地址3. JuiceSSH公网远程连接4. 固定连接SSH公网地址5. SSH固定地址连接测试 处于内网的虚拟机如何被外网访问呢?如何手机就能访问虚拟机呢? cpolarJuiceSSH 实现手机端远程连接Linux虚拟机(内网穿透,手机端连接Linux虚拟机) …

echarts 模拟时间轴播放效果

x,y轴为数值轴&#xff0c;通过设置bar的数据模拟时间播放。标签可通过formatter自定义为时间&#xff0c;播放/停止/速度可通过setInterval来控制(待完善) 代码可直接放echart官方示例执行 let data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,100]; option {color: [#3398DB],toolti…

代码随想录算法训练营第二天|977、有序数组的平方

977. 有序数组的平方 已解答 简单 相关标签 相关企业 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输入&#xff1a;nums [-4,-1,0,3,10] 输出&#xff1a;[0,1,9,16,…

Linux Ubuntu系统安装MySQL并实现公网连接本地数据库【内网穿透】

文章目录 前言1 .安装Docker2. 使用Docker拉取MySQL镜像3. 创建并启动MySQL容器4. 本地连接测试4.1 安装MySQL图形化界面工具4.2 使用MySQL Workbench连接测试 5. 公网远程访问本地MySQL5.1 内网穿透工具安装5.2 创建远程连接公网地址5.3 使用固定TCP地址远程访问 前言 本文主…

基于Flask的宠物领养系统的设计与实现

基于Flask的宠物领养系统的设计与实现 涉及技术&#xff1a;python3.10flaskmysql8.0 系统分为普通用户和管理员两种角色&#xff0c;普通用户可以浏览搜索宠物&#xff0c;申请领养宠物&#xff1b;管理员可以分布宠物信息&#xff0c;管理系统等。 采用ORM模型创建数据&am…

chrome浏览器插件content.js和background.js还有popup都是什么,怎么通讯

popup 在用户点击扩展程序图标时&#xff08;下图中的下载图标&#xff09;&#xff0c;都可以设置弹出一个popup页面。而这个页面中自然是可以包含运行的js脚本的&#xff08;比如就叫popup.js&#xff09;。它会在每次点击插件图标——popup页面弹出时&#xff0c;重新载入。…

高并发服务器模型

高并发服务器模型 1.高并发服务器模型--select2.高并发服务器模型--poll3.epoll模型3.1 epoll原理3.2epoll反应堆 1.高并发服务器模型–select 我们知道实现服务器的高并发&#xff0c;可以用多线程或多进程去实现。但还可以利用多路IO技术:select来实现&#xff0c;它可以同时…

html唐诗鉴赏

<!DOCTYPE html> <html> <head><title>文字网页</title> </head> <body><h2 align"center">唐诗鉴赏</h2><hr width"100%" size"1" color"#00ffee"><p align"…

“2024第九届国际发酵培养基应用与发展技术论坛”圆满落幕

3月5日&#xff0c;“2024第九届国际发酵培养基应用与发展技术论坛”在济南圆满落幕。论坛吸引了来自发酵行业400多名代表现场参会&#xff0c;1600多名代表线上参会。本次论坛由中国生物发酵产业协会主办&#xff0c;安琪酵母股份有限公司承办。中国生物发酵产业协会理事长于学…

抽奖小程序怎么一键生成_揭秘这款火爆的抽奖小程序

一键生成&#xff0c;梦想触手可及&#xff01;揭秘这款火爆的抽奖小程序 在快节奏的现代生活中&#xff0c;每个人都渴望找到一份属于自己的幸运与惊喜。而今天&#xff0c;我要为大家介绍的这款抽奖小程序&#xff0c;正是实现这一愿望的神器&#xff01;它不仅操作简单&…

Linux服务器安装nvm

1、 首先查看服务器有没有安装git git --version 2、如果没有安装&#xff1a;在Linux上是有yum安装Git&#xff0c;非常简单&#xff0c;只需要一行命令 yum -y install git 3、git安装完成后&#xff0c;使用以下其中一个命安装NVM # 能访问github的话&#xff0c;使用这…