归并排序【C语言版-笔记】

目录

  • 一、概念
  • 二、排序流程理解
  • 三、代码实现
    • 3.1主调函数
    • 3.2 merge函数
  • 四、性能分析

一、概念

归并是一种算法思想,是将两个或两个一上的有序表合并成一个长度较大的有序表。若一开始无序表中有n个元素,可以把n个元素看作n个有序表,把它们两两合并得到 ⌈ n / 2 ⌉ 个 \lceil n/2\rceil个 n/2长度为2或1(n为奇数时)的有序表,继续重复两两合并的操作,直到剩下一个有序表,即得到最终排序的结构,这是“二路归并排序”,还有多路的归并。

二、排序流程理解

给定一个序列如下:
在这里插入图片描述

1)不断地将当前序列平均分割成2个子序列,直到不能再分割(序列中只剩1个元素)
2)不断地将2个子序列合并成一个有序序列,直到最终只剩下1个有序序列
在这里插入图片描述
要点分析:
① 处理好边界和有序表分割位置选择问题
② 合并两个子序列的过程中,如何排序使合并后的序列是一个有序序列,称之为:merge

1、有序表分割的位置(排序使用到的参数:begin,mid,end)
初始时:
begin=0,mid=(begin+end)/2,end=length
规定:
左边表范围:[begin,mid)
右边表范围:[mid,end)
当无序表元素个数为偶数时,划分的左右子表元素个数相同,
当无序表元素个数为奇数时,划分的左右子表元素个数相差1,右子表多个一
不管奇偶情况如何,左子表元素个数为:mid-begin,右子表元素个数为:end-mid2、merge过程中我们使用一个辅助数组leftArray,把位于[begin,end)范围的表中左边部分[begin,mid)之间的元素拷贝到leftArray中,用leftArray表中元素和右边部分元素依次比较,小的放入原表(即:[begin,end) )中的左边部分,直到leftArray或右边部分的元素比较完,然后把剩余的没比较的直接拷贝到原表中即可,一次merge完成。

在这里插入图片描述

◼ li == 0,le == mid – begin
◼ ri == mid,re == end

三、代码实现

3.1主调函数

void sort(int *nums,int begin,int end){if(end-begin<=1) return;//只有一个元素不用排序int mid=(begin+end)/2;//或(begin+end)>>1sort(nums,begin,mid);sort(nums,mid.begin);merge(nums,begin,mid,end);
}

3.2 merge函数

void merge(int *nums,int begin,int mid,int end){int li=0;int le=mid-begin;int ri=mid;int re=end;int ai=begin;int leftArray=(int*)malloc(le*sizeof(int));//辅助数组//初始化辅助数组for(int i=li;i<le;i++){leftArray[i]=nums[begin+i];//begin~end之间左边部分拷贝到夫leftArray}//在原存储空间上给两个有序子表重新排序(逻辑上是合并为一个有序表),两种可能:左边指针先走完(ri>=re)或右边指针先走完。//若左边先走完则直接把leftArray中li指针指向的及之后的元素复制到原存储空间(nums);若右边先走完,则结束while(li<le){if(ri<re&&nums[ri]<leftArray[li]){nums[ai++]=nums[ri++];//拷贝左边部分的元素到nums[ai]}else{nums[ai++]=leftArray[li++];//拷贝右边部分的元素到nums[ai]}}
}

四、性能分析

空间效率: merge函数中使用的辅助空间是n/2个单元,即算法的空间复杂度:O(n)
时间效率: 每趟归并的时间复杂度是O(n),总共需要进行 ⌈ l o g 2 n ⌉ \lceil log_2n\rceil log2n趟归并,总的时间复杂度:O(nlog2n)
稳定性: 不会改变相同关键字记录的相对次序(看merge函数中while循环的处理部分可知),因此二路归并排序是稳定的排序算法

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-27

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-27 目录 文章目录 计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-27目录1. VisScience: An Extensive Benchmark for Evaluating K12 Educational Multi-modal Scientific Reasoning VisScience:…

java中的强软弱虚

在java中对象的引用有强、软、弱、虚四种&#xff0c;这些引用级别的区别主要体现在对象的生命周期、回收时机的不同。 文章目录 准备工作1. 设置内存2. 内存检测 强引用软引用弱引用虚引用 准备工作 1. 设置内存 为方便调试&#xff0c;将内存设置为16MB 依次点击菜单栏的R…

初识算法 · 双指针(1)

目录 前言&#xff1a; 双指针算法 题目一&#xff1a; ​编辑 题目二: 前言&#xff1a; 本文作为算法部分的第一篇文章&#xff0c;自然是少不了简单叭叭两句&#xff0c;对于算法部分&#xff0c;多刷是少不了&#xff0c;我们刷题从暴力过度到算法解法&#xff0c;自…

【Linux】进程概念-2

文章目录 1.环境变量1.1 基本概念1.2 常见环境变量1.3 查看环境变量方法1.4 测试PATH1.5 测试HOME1.6 和环境变量相关的命令1.7 环境变量的组织方式1.8 通过代码如何获取环境变量1.9 通过系统调用获取或设置环境变量1.10 环境变量通常是具有全局属性的1.11 实验 2. 程序地址空间…

安全中心 (SOC) 与 网络运营中心 (NOC)

NOC 和 SOC 之间的区别 网络运营中心 (NOC) 负责维护公司计算机系统的技术基础设施&#xff0c;而安全运营中心 (SOC) 则负责保护组织免受网络威胁。 NOC 专注于防止自然灾害、停电和互联网中断等自然原因造成的网络干扰&#xff0c;而 SOC 则从事监控、管理和保护。 NOC 提…

微信小程序 图片的上传

错误示范 /*从相册中选择文件 微信小程序*/chooseImage(){wx.chooseMedia({count: 9,mediaType: [image],sourceType: [album],success(res) {wx.request({url:"发送的端口占位符",data:res.tempFiles[0].tempFilePath,method:POST,success(res){//请求成功后应该返…

Java在用增强for循环遍历集合时删除元素,抛出java.util.ConcurrentModificationException异常

文章目录 0. 前言1. 问题产生的背景2. Java中增强for循环的底层原理3. 为什么增强for循环不支持在遍历集合时删除元素3.1 问题排查3.2 modCount 变量的来源3.3 expectedModCount 变量的来源3.4 导致modCount变量和expectedModCount不相等的原因3.5 为什么用迭代器遍历元素时删除…

【Nacos架构 原理】内核设计之Nacos通信通道

文章目录 Nacos通信通道 &#xff08;长链接&#xff09;现状背景场景分析配置服务 长链接核心诉求功能性诉求负载均衡连接生命周期 Nacos通信通道 &#xff08;长链接&#xff09; 现状背景 Nacos 1.X 版本 Config/Naming 模块各自的推送通道都是按照自己的设计模型来实现的…

仪器数码管数字识别系统源码分享

仪器数码管数字识别检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Comput…

Glide基本用法及With方法源码解析

文章目录 引入优点 使用步骤导入依赖权限使用 其他用法占位符错误图片后备回调符圆角过渡动画大小调整gif缩略图 使用RequestOptions缓存机制设置缓存策略清理缓存 使用集成库OkHttpVolley with源码解析getRetrieverGlide.getinitializeGlide getRequestManagerRetriever Reque…

【Spine】引入PhotoshopToSpine脚本

引入 右键Photoshop图标&#xff0c;选择属性 打开文件所在位置 找到目录下的\Presets\Scripts文件夹。 找到Spine目录下的\scripts\photoshop文件夹下的PhotoshopToSpine.jsx 复制它&#xff0c;丢到Photoshop刚才找的那个目录下。 使用 打开.psd文件&#xff0c;检查不要…

ubuntu 安装harbor

#安装包 wget https://github.com/goharbor/harbor/releases/download/v2.10.3/harbor-offline-installer-v2.10.3.tgz wget https://github.com/goharbor/harbor/releases/download/v2.10.3/harbor-offline-installer-v2.10.3.tgz.asc#导入签名公钥 gpg --keyserver hkps://ke…

文心一言 VS 讯飞星火 VS chatgpt (359)-- 算法导论24.3 1题

一、在图 24-2上运行Dijkstra算法&#xff0c;第一次使用结点 s s s作为源结点&#xff0c;第二次使用结点 z z z作为源结点。以类似于图 24-6 的风格&#xff0c;给出每次while循环后的 d d d值和 π π π值&#xff0c;以及集合 S S S中的所有结点。如果要写代码&#xff0c…

计算机毕业设计Spark+PyTorch股票预测系统 股票推荐系统 股票可视化 股票数据分析 量化交易系统 股票爬虫 股票K线图 大数据毕业设计 AI

《SparkPyTorch股票预测系统》开题报告 一、研究背景与意义 随着信息技术的飞速发展和全球金融市场的日益繁荣&#xff0c;股票投资已成为广大投资者的重要选择之一。然而&#xff0c;股票市场的复杂性和不确定性使得投资者在做出投资决策时面临巨大的挑战。传统的股票分析方…

Python空间地表联动贝叶斯地震风险计算模型

&#x1f3af;要点 使用贝叶斯推断模型兼顾路径和场地效应&#xff0c;量化传统地理统计曲线拟合技术。使用破裂和场地特征等地质信息以及事件间残差和事件内残差描述数学模型模型使用欧几里得距离度量、角距离度量和土壤差异性度量确定贝叶斯先验分布和后验分布参数&#xff…

CTMO时代下的营销新力量:2+1链动模式AI智能名片商城小程序

在当今这个瞬息万变的商业世界里&#xff0c;营销领域正经历着一场深刻的变革。传统的CMO岗位似乎在时代的浪潮中逐渐失去了它的光芒&#xff0c;CTMO正在悄然取代传统CMO的岗位。 随着营销丛林现象的出现&#xff0c;企业面临着前所未有的挑战。许多企业发现&#xff0c;那些传…

【SQL】未订购的客户

目录 语法 需求 示例 分析 代码 语法 SELECT columns FROM table1 LEFT JOIN table2 ON table1.common_field table2.common_field; LEFT JOIN&#xff08;或称为左外连接&#xff09;是SQL中的一种连接类型&#xff0c;它用于从两个或多个表中基于连接条件返回左表…

动态分配内存

目录 前言 一.malloc,free函数 1.malloc,free函数原型 2.使用方法 3.具体实例 4.注意事项 二.calloc函数 1.calloc函数原型 2.主要特点 3.使用案例 三.realloc函数 1.realloc函数原型 2.使用案例 3.注意事项 前言 动态内存是指在程序运行时&#xff0c;按需分配和…

51单片机学习第六课---B站UP主江协科技

DS18B20 1、基本知识讲解 2、DS18B20读取温度值 main.c #include<regx52.h> #include"delay.h" #include"LCD1602.h" #include"key.h" #include"DS18B20.h"float T; void main () {LCD_Init();LCD_ShowString(1,1,"temp…

时序必读论文14|VLDB24 TFB:全面且公平的时间序列预测方法框架

论文标题&#xff1a;TFB: Towards Comprehensive and Fair Benchmarking of Time Series Forecasting Methods 论文链接&#xff1a;https://arxiv.org/pdf/2403.20150.pdf 代码链接&#xff1a;https://github.com/decisionintelligence/TFB 前言 五一过后读的第一篇文章…