归并算法详细解析

归并排序

1945年,约翰·冯·诺依曼(John von Neumann)发明了归并排序,这是典型的分治算法的应用。归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

基本思想

归并排序是使用分治算法,就是把序列分成长度相同的两个子序列,当无法继续往下分时(也就是每个子序列中只有一个数据时),就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行,直到所有子序列都归并为一个整体为止。

图形演示

为方便查看,我们用不同高度来表示不同的数字大小
在这里插入图片描述

  1. 首先我们把序列逐层对半分割

    在这里插入图片描述

直至不能再分割为止
在这里插入图片描述

  1. 分割完毕,接下来对每组元素进行合并;合并时需要将数字按照从小到大的顺序排列:
    在这里插入图片描述

每次合并时比较两个子序列的首位数字。当合并有多个数字的子序列时,要先比较首位数字,再移动较小的数字:由于3<4,所以要先移动3,接下来再比较4和7;4<7,所以移动4,再比较6和7…如此往复,左半个序列就排序好啦
在这里插入图片描述

右边也是如此,直至所有的数字都合并为一个整体为止
在这里插入图片描述

合并完成,序列的排序也就完成了

时间复杂度分析

​ 归并排序中,分割序列所花费的时间不算在运行时间内(可以当作序列本来就是分 割好的)。在合并两个已排好序的子序列时,只需重复比较首位数据的大小,然后移动较 小的数据,因此只需花费和两个子序列的长度相应的运行时间。也就是说,完成一行归 并所需的运行时间取决于这一行的数据量。 看一下上面的图便能得知,无论哪一行都是 n 个数据,所以每行的运行时间都为 O(n)。 而将长度为 n 的序列对半分割直到只有一个数据为止时,可以分成 log2n 行,因此,总 共有 log2n 行。也就是说,总的运行时间为 O(nlogn),这与前面讲到的堆排序相同。

代码实现

迭代法

public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    int block, start;

    for(block = 1; block < len*2; block *= 2) {
        for(start = 0; start <len; start += 2 * block) {
            int low = start;
            int mid = (start + block) < len ? (start + block) : len;
            int high = (start + 2 * block) < len ? (start + 2 * block) : len;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2) {
            result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            }
            while(start1 < end1) {
            result[low++] = arr[start1++];
            }
            while(start2 < end2) {
            result[low++] = arr[start2++];
            }
        }
    int[] temp = arr;
    arr = result;
    result = temp;
    }
    result = arr;       
}

递归法

static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, result, start1, end1);
    merge_sort_recursive(arr, result, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        result[k++] = arr[start1++];
    while (start2 <= end2)
        result[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = result[k];
}

public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    merge_sort_recursive(arr, result, 0, len - 1);
}

总结

​ 归并排序与选择排序一样,性能不受输入数据的影响,但时间复杂度远小于选择排序。但由于归并排序需要另外一个与原数组长度相同的数组来做辅助排序,需要占用额外的空间,空间复杂度为O(n);

参考资料:《我的第一本算法书》

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

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

相关文章

[Semi-笔记] 2023_TIP

目录 概要一&#xff1a;Conservative-Progressive Collaborative Learning&#xff08;保守渐进式协作学习&#xff09;挑战&#xff1a;解决&#xff1a; 二&#xff1a;Pseudo Label Determination for Disagreement&#xff08;伪标签分歧判定&#xff09;挑战&#xff1a;…

华工考研复试模板

华工考研复试PPT模板 前言PPT概览PPT章节展示 最后的最后 前言 前段时间&#xff0c;有考研的学弟学妹咨询选导师的相关事项。可能也有的学弟学妹在准备复试相关的PPT&#xff0c; 这里小编我打算这几天DIY一个模板&#xff0c;主要其实还是跟自己之前夏令营的答辩模板和奖学金…

ResNet《Deep Residual Learning for Image Recognition》

ResNet论文学习 引言Deep Residual Learning 深度残差学习Residual Learning 残差学习Identity Mapping by Shortcuts 通过捷径来恒等映射网络结构Plain NetworkResidual Network实现细节 实验总结代码复现Building blockBottleneckResnet 18Resnet 34Resnet 50 引言 深度网络…

23.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4]示例 2&#xff1a; 输入&#xff1a;l1 [], l2 [] 输出&#xff1a;[]示…

【计算机考研】杭电 vs 浙工大 怎么选?

想求稳上岸的话&#xff0c;其他几所学校也可以考虑&#xff0c;以留在本地工作的角度考虑&#xff0c;这几所学校都能满足你的需求。 如果之后想谋求一份好工作&#xff0c;肯定优先杭电是比较稳的&#xff0c;当然复习的时候也得加把劲。 这个也可以酌情考虑&#xff0c;报…

TikTok小店运营经验分享,美国本土小店怎么做?

作为资深跨境老玩家&#xff0c;虽不说是经验丰富&#xff0c;至少也是摸清了基本的玩法思路。TikTok作为近来的跨境新蓝海&#xff0c;他的玩法其实并不难&#xff0c;作为第一批试错玩家&#xff0c;今天也诚心给大家分享一些美国本土小店运营经验&#xff0c;感兴趣的话就看…

50、C++/类的继承和多态相关学习20240318

一、c编程实现&#xff1a; 封装一个动物的基类&#xff0c;类中有私有成员&#xff1a;姓名&#xff0c;颜色&#xff0c;指针成员年纪&#xff1b; 再封装一个狗这样类&#xff0c;共有继承于动物类&#xff0c;自己拓展的私有成员有&#xff1a;指针成员&#xff1a;腿的个…

IT部门领导的角色与责任:在挑战中塑造未来

前言 在当今快节奏的商业环境中&#xff0c;IT部门领导扮演着至关重要的角色。他们需要具备技术专长&#xff0c;同时也需要展现出卓越的领导力来有效地管理团队和应对各种挑战。 一、技术创新的引领者 1. 重要角色转变 随着信息技术的迅猛发展&#xff0c;IT部门领导已逐渐…

[QT] QTextBrowser取消默认右键菜单项 复制链接地址

setTextInteractionFlags(Qt::TextSelectableByMouse);原理 QTextBrowser默认下有三个标志位&#xff0c;QTextBrowser右键菜单相关源码如下 源码链接 if ((d->interactionFlags & Qt::LinksAccessibleByKeyboard)|| (d->interactionFlags & Qt::LinksAccessible…

【SpringSecurity】十七、OAuth2授权服务器 + 资源服务器Demo

文章目录 0、库表准备1、项目结构2、基于数据库的认证3、授权服务器配置4、授权服务器效果测试5、资源服务器配置6、其他授权模式测试6.1 密码模式6.2 简化模式6.3 客户端模式6.4 refresh_token模式 相关&#x1f4d5;&#xff1a;【Spring Security Oauth2 配置理论部分】 0、…

C++临时变量

本博客将讲述我学习过程中对临时变量的疑惑与理解 为什么写这篇文章&#xff1f; 我在学习C过程中&#xff0c;发现C在发生隐式转换时或者出现未命名的变量如字符串再或者在求值的时候&#xff0c;会出现C临时变量&#xff08;系统自动生成&#xff09;&#xff0c;而这个临时…

【Hadoop大数据技术】——ZooKeeper分布式协调服务(学习笔记)

&#x1f4d6; 前言&#xff1a;ZooKeeper是一个开源的分布式协调服务&#xff0c;它是Google Chubby的开源实现&#xff0c;其设计目标是将那些复杂且容易出错的分布式应用封装起来&#xff0c;构成一个高效可靠的原语集&#xff0c;并以一系列简单易用的接口提供给用户使用。…

C# 右键快捷菜单(上下文菜单)的两种实现方式

在C#中&#xff0c;ContextMenuStrip是一种用于创建右键菜单的控件。它提供了一种方便的方式来为特定的控件或窗体添加自定义的上下文菜单选项。有两种实现方式&#xff0c;如下&#xff1a; 一.通过ContextMenuStrip控件实现 1.从工具箱中拖一个ContextMenuStrip控件到窗体上…

尝试搭建谷粒商城 记录(四)

版权声明&#xff1a;本文为博主原创文章&#xff0c;遵循 CC 4.0 BY-SA 版权协议&#xff0c;转载请附上原文出处链接和本声明。 本文链接&#xff1a;https://blog.csdn.net/weixin_44190665/article/details/121043585 ———————————————— 版权声明&#xff1…

爬虫工作量由小到大的思维转变---<第四十九章 Scrapy 降维挖掘---中间件系列(1)>

前言&#xff1a; Scrapy是一个功能强大的网络爬虫框架&#xff0c;但在实际应用过程中&#xff0c;中间件问题可能会成为一个令人头痛的难题。为了彻底解决Scrapy中的各种疑难杂症&#xff0c;我决定进行第四次全面的学习和实践&#xff0c;并将中间件的问题一一拆解&#xff…

【DL经典回顾】激活函数大汇总(四十二)(CosReLU附代码和详细公式)

激活函数大汇总(四十二)(CosReLU附代码和详细公式) 更多激活函数见激活函数大汇总列表 一、引言 欢迎来到我们深入探索神经网络核心组成部分——激活函数的系列博客。在人工智能的世界里,激活函数扮演着不可或缺的角色,它们决定着神经元的输出,并且影响着网络的学习能…

幸运数字(第十四届蓝桥杯JavaB组省赛真题)

进制转换可以参考如下的十进制&#xff0c;基本一样的&#xff0c;只是把10变成了其他数字&#xff0c; sum就是各个数位之和 public static int myUtil(int n) {int sum 0;while(n > 0) {sum n % 10;n / 10;}return sum;} 注意&#xff1a; 如果写在同一个类里面&…

@arco.design radioGroup 组件手写 beforeChange 方法

官方是没有提供 beforeChange 事件的&#xff0c;只能自己写一个 子组件&#xff08;CustomRadioGroup&#xff09; <template><a-radio-group :model-value"modelValue" change"onRadioChange"><a-radio v-for"item in list" …

面试算法-72-删除排序链表中的重复元素

题目 给定一个已排序的链表的头 head &#xff0c; 删除所有重复的元素&#xff0c;使每个元素只出现一次 。返回 已排序的链表 。 示例 1&#xff1a; 输入&#xff1a;head [1,1,2] 输出&#xff1a;[1,2] 解 class Solution {public ListNode deleteDuplicates(ListNo…

鸿蒙一次开发,多端部署(八)典型布局场景

虽然不同应用的页面千变万化&#xff0c;但对其进行拆分和分析&#xff0c;页面中的很多布局场景是相似的。本小节将介绍如何借助自适应布局、响应式布局以及常见的容器类组件&#xff0c;实现应用中的典型布局场景。 说明&#xff1a; 在本文 媒体查询 小节中已经介绍了如何通…