算法笔记【8】-合并排序算法
文章目录
- 一、前言
- 二、合并排序算法基本原理
- 三、实现步骤
- 四、优缺点分析
一、前言
合并排序算法通过采用分治策略和递归思想,实现了高效、稳定的排序功能。本文将深入探讨合并排序算法的原理、实现步骤,并讨论其优缺点。
二、合并排序算法基本原理
合并排序算法采用了分治策略,将一个大问题分解为若干个小问题,并通过递归地解决这些小问题来达到整体解决的目的。具体而言,合并排序首先将待排序的数组不断划分为两个子数组,直到每个子数组只包含一个元素,然后将这些子数组进行两两合并,同时按照大小顺序排列,最终得到完全有序的数组。
三、实现步骤
以数组为例,其算法流程原理如图所示。

由图可知,合并排序算法的实现步骤可大致分为三步:
- 第一步-》递归划分:将待排序数组不断划分为两个子数组,直到每个子数组只包含一个元素。
- 第二步-》合并操作:将两个有序的子数组合并为一个有序数组,同时按照大小顺序排列。
- 第三步-》重复上述步骤,直到整个数组排序完成。
以下是使用matlab编写的合并排序算法示例代码:
- 合并排序算法函数
%% 合并排序算法函数
function sorted_array = mergeSort(arr)% 检查输入数组是否为空或只有一个元素if length(arr) <= 1sorted_array = arr;return;end% 将输入数组分为两个子数组mid = fix(length(arr)/2);left_array = arr(1:mid);right_array = arr(mid+1:end);% 递归调用mergeSort函数对子数组进行排序left_sorted = mergeSort(left_array);right_sorted = mergeSort(right_array);% 合并两个已排序的子数组sorted_array = merge(left_sorted, right_sorted);
end%% 子数组排序合并函数
function merged_array = merge(arr1, arr2)% 初始化指针和合并后的数组i = 1; j = 1; k = 1;merged_length = length(arr1) + length(arr2);merged_array = zeros(1, merged_length);% 比较两个数组的元素,并按顺序将较小的元素放入合并后的数组中while i <= length(arr1) && j <= length(arr2)if arr1(i) <= arr2(j)merged_array(k) = arr1(i);i = i + 1;elsemerged_array(k) = arr2(j);j = j + 1;endk = k + 1;end% 将剩余的元素复制到合并后的数组中while i <= length(arr1)merged_array(k) = arr1(i);i = i + 1;k = k + 1;endwhile j <= length(arr2)merged_array(k) = arr2(j);j = j + 1;k = k + 1;end
end
- 调用
clc;
clear;
arr = [79,88,70,37,92,6,28,54];
%% 快速排序函数调用
sortedArr= mergeSort(arr);
disp("***********合并排序*****************************");
disp("排序前的数组:");
disp(arr);
disp("排序后的数组:");
disp(sortedArr);
- 结果

四、优缺点分析
优点:
- 合并排序算法具有稳定性,相同元素的相对顺序不会改变。
- 在平均情况下,合并排序的时间复杂度为O(nlogn),较低的时间复杂度保证了其高效性。
- 可以处理大规模数据的排序,适用于各种数据类型。
缺点:
- 合并排序算法需要额外的空间来存储中间结果,空间复杂度为O(n)。
- 对于小规模数据,合并排序的性能可能略低于其他简单的排序算法,由于递归调用的开销。
结论:
合并排序算法通过巧妙地利用分治策略和递归思想,实现了高效、稳定的排序功能。它在实际应用中被广泛使用,并且适用于各种数据类型和规模。然而,在面对特别大的数据集时,需要考虑额外的空间开销。了解合并排序的原理和实现方式,对于深入理解分治策略以及扩展排序算法的知识面都是非常有益的。
相关文章:
算法笔记【8】-合并排序算法
文章目录 一、前言二、合并排序算法基本原理三、实现步骤四、优缺点分析 一、前言 合并排序算法通过采用分治策略和递归思想,实现了高效、稳定的排序功能。本文将深入探讨合并排序算法的原理、实现步骤,并讨论其优缺点。 二、合并排序算法基本原理 合…...
蓝桥杯每日一题2023.10.30
题目描述 日志统计 - 蓝桥云课 (lanqiao.cn) 题目分析 本题可以使用双指针来维护时间段的区间,在维护的时间段内确定是否为热帖 #include<bits/stdc.h> using namespace std; typedef long long ll; const int N 2e5 10; struct node {int t, id; }tiee…...
macOS M1安装wxPython报错‘tiff.h‘ file not found的解决方法
macOS12.6.6 M1安装wxPython失败: 报错如下: imagtiff.cpp:37:14: fatal error: tiff.h file not found解决办法: 下载源文件重新编译(很快,5分钟全部搞定),分三步走: 第一步&…...
多路转接之epoll
本篇博客介绍: 多路转接之epoll 多路转接之epoll 初识epollepoll相关系统调用epoll的工作原理epoll服务器编写成员变量构造函数 循环函数HandlerEvent函数epoll的优缺点 我们学习epoll分为四部分 快速理解部分概念 快速的看一下部分接口讲解epoll的工作原理手写epo…...
删除排序链表中的重复节点II(C++解法)
题目 给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。 示例 1: 输入:head [1,2,3,3,4,4,5] 输出:[1,2,5]示例 2: 输入:head [1…...
uniapp自定义tab切换css样式、uni-forms中input下拉等标签字体、过宽、溢出样式一系列调整(附加实战举例)
一、uniapp自定义tab切换css样式 <view class="tabs-container"><view class="tabs-list">...
windows server 2016-IIS静态服务器-设置详细过程
文章目录 1.打开仪表盘新建角色2.iis功能模块3.启动服务器4.优点 1.打开仪表盘新建角色 2.iis功能模块 能选上的尽量选上,除非知道自己用不上。 然后确认,下一步,安装。 3.启动服务器 搜索IIS,启动IIS管理器。 启动网站。 右…...
不一样的编程方式 —— 协程(设计原理与汇编实现)
主要通过以下9个方面来了解协程的原理: 目录 1、为什么使用协程 1.3、协程的适用场景 2、协程的原语操作 3、协程的切换 3.1、汇编实现 4.协程的运行流程 5.协程的结构体定义(我们其实可以参照线程或者进程的状态来设计) 5.1、多状态集合设计 6.协程的调度…...
Thinkphp6项目在虚拟机无法指向pulic的目录访问的方法
以阿里云虚拟主机为例,服务器环境为 LAMP,Apache2.4 php7.2 mysql5.7 1.根目录新建 index.php 文件,将以下内容放入文件中 <?php include ./public/index.php;2.将 public 目录下的 admin.php、backend 文件夹、static 文件夹、tinymc…...
数据结构(超详细讲解!!)第十八节 串(堆串)
1.定义 假设以一维数组heap [MAXSIZE] 表示可供字符串进行动态分配的存储空间,并设 int start 指向heap 中未分配区域的开始地址(初始化时start 0) 。在程序执行过程中,当生成一个新串时,就从start指示的位置起&#…...
idea集成测试插件替代postman
idea集成测试插件替代postman 兄弟萌,你再测试接口是否无bug是否流畅的时候是否还在使用“postman”来回切换进行测试呢? 页面切换进行测试,有没有感觉很麻烦呢? 打开postman,输入接口地址,有没有感觉很麻烦…...
clusterprolifer go kegg msigdbr 富集分析应该使用哪个数据集,GO?KEGG?Hallmark?
关注微信:生信小博士 5 Overview of enrichment analysis Chapter 5 Overview of enrichment analysis | Biomedical Knowledge Mining using GOSemSim and clusterProfiler 5.1.2 Gene Ontology (GO) Gene Ontology defines concepts/classes used to describ…...
Linux学习笔记1-入门
前言:之前的基于单片机的闭环控制步进电机项目其实已经完成了,但很多时间都花在调试和生产上,实在没时间去做总结笔记,现在又开始做新项目了,从单片机到了Linux,想用这个平台来督促自己继续学习,…...
怎样更有效的运营Etsy店铺?
大家都知道,Etsy作为一个重要的电商平台,给很多人提供了不少机会。但是如何取得etsy店铺运营的成功呢?第一步就是选好辅助工具。 什么是指纹浏览器? VMLogin指纹浏览器(www.vmlogin.com.cn) 是一种工具,通过伪装用户…...
Vue 项目中如何使用Bootstrap5(简单易懂)
Vue 项目中如何使用Bootstrap5(简单易懂) 安装在 src/main.js 文件下引入包在vue文件中使用 Bootstrap官网(中文):https://www.bootcss.com/ Bootstrap5文档:https://v5.bootcss.com/docs/getting-started/…...
k8s 资源预留
KUBERNETES资源管理之–资源预留 Kubernetes 的节点可以按照 Capacity 调度。node节点本身除了运行不少驱动 OS 和 Kubernetes 的系统守护进程,默认情况下 pod 能够使用节点全部可用容量, 除非为这些系统守护进程留出资源,否则它们将与 pod 争…...
微信小程序自定义弹窗阻止滑动冒泡catchtouchmove之后弹窗内部内容无法滑动
自定义弹窗 如图所示: 自定义弹窗内部有带滚动条的盒子区域 问题: 在盒子上滑动,页面如果超出一屏的话,也会跟着一起上下滚动 解决方案:给自定义弹窗 添加 catchtouchmove 事件,阻止冒泡即可 网上不少…...
Linux 命令速查
Network ping ping -c 3 -i 0.01 127.0.0.1 # -c 指定次数 # -i 指定时间间隔 日志 一般存放位置: /var/log,包含:系统连接日志 进程统计 错误日志 常见日志文件说明 日志功能access-logweb服务访问日志acct/pacct用户命令btmp记录失…...
第22期 | GPTSecurity周报
GPTSecurity是一个涵盖了前沿学术研究和实践经验分享的社区,集成了生成预训练 Transformer(GPT)、人工智能生成内容(AIGC)以及大型语言模型(LLM)等安全领域应用的知识。在这里,您可以…...
JavaScript前端 console 控制台详细解析与代码实例
JavaScript Console(控制台)是一个重要的工具,可以用于调试和测试 JavaScript 代码。在浏览器中,你可以使用控制台来查看 JavaScript 输出、测试代码、调试错误等。在本文中,我们将详细介绍控制台的常用功能和代码实例…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
