归并排序算法

1、基本思想

        归并排序是建立在归并操作上的一种有效的排序算法,它采用分治法的策略。其基本思想是将一个待排序的数组分成两个或多个子数组,先对每个子数组进行排序,然后再将已排序的子数组合并成一个最终的排序数组。

        对于两个有序的数组,很容易做到合并之后仍然有序。归并排序就是利用这一点,将待排序数组分成两个有序数组(如何保证分成的两个数组都有序:不停拆分,直到每个数组中只剩一个数,那么一定有序。)。待得到有序数组后,往回进行不停的合并操作。

2、算法步骤

2.1、算法步骤描述:

        1、分解:将待排序的数组不断地拆分成左右两个子数组,直到每个子数组只包含一个元素为止。这一步是通过不断地计算数组的中间位置来实现的,例如对于数组 arr,中间位置 mid = (left + right) / 2(这里假设 left 是数组起始索引,right 是数组结束索引),从而将数组 arr 拆分成 arr[left...mid] 和 arr[mid + 1...right] 两个子数组。

        2、排序与合并:对拆分后的子数组递归地调用归并排序算法,使其各自有序。然后将两个已经有序的子数组合并成一个更大的有序数组。合并操作是通过比较两个子数组的首元素,将较小的元素依次放入一个临时数组中,直到其中一个子数组的元素全部放入临时数组,再将另一个子数组剩余的元素全部放入临时数组,最后将临时数组中的元素复制回原数组对应的位置。

2.2、归并排序算法过程演示图:

2.3、归并排序算法动态演示图:

动态演示图来源网站URL:​​​​​​https://visualgo.net

3、代码实现

c语言代码实现如下:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define N 10
void add(int arr[], int *left, int leftlen, int *right, int rightlen)
{int i = 0, j = 0, k = 0;//分别代表左数组下标,右数组下标,合并后数组下标while(i < leftlen && j < rightlen)//两个子数组都没合并完{if(left[i] <= right[j])//每次将两子数组中最小值填入arr[k++] = left[i++];elsearr[k++] = right[j++];}//两个子数组可能不会同时完成填入//当左子数组没有完成while(i < leftlen){arr[k++] = left[i++];}//当右子数组没有完成while(j < rightlen){arr[k++] = right[j++];}
}
void sort(int arr[], int len)
{//设定递归终止条件,拆分到数组长度为一时,一定有序if(1 == len)return;int i;int mid = len/2;//确定中间位置int *left = (int *)malloc(mid * sizeof(int));//分配左数组空间int *right = (int *)malloc((len-mid) * sizeof(int));//分配右数组空间for(i = 0; i < mid ; i++)//存值到左数组中{left[i] = arr[i];}for(i = 0; i < len - mid; i++)//存值到右数组中{right[i] = arr[mid + i];}sort(left,mid);//对左右数组再进行拆分sort(right,len - mid);add(arr,left,mid,right,len - mid);//合并有序数组free(left);//回收空间free(right);
}
int main(int argc, char *argv[])
{srand(time(NULL));int a[N];int i;puts("排序前数组为:");for(i = 0; i < N; i++){a[i] = rand()%100;//为数组随机赋值printf("%d ",a[i]);//输出排序之前数组值}puts("");sort(a,N);//排序puts("排序后的数组为:");for(i = 0; i < N; i++){printf("%d ",a[i]);//输出排序之后的数组值}puts("");return 0;
}

4、时间复杂度和空间复杂度

平均时间复杂度:O(nlogn)

空间复杂度:O(n)

稳定性:稳定

5、适用情况

        1、处理大规模数据排序:其时间复杂度为O(nlogn),处理大规模数据时,能够在相对较短的时间内完成排序任务。

        2、有稳定排序的需求时:归并排序是一个稳定的排序算法,当有相等元素进行排序时,相等元素的相对顺序不会改变。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

记录解决vscode 登录leetcode中遇到的问题

1. 安装完 leetcode 点击sign in to leetcode 点击打开网站登录leetcode&#xff0c;发现网页无法打开。 解决办法&#xff1a;将leetcode.cn.js文件中的leetcode-cn.com路径都改成leetcode.cn 2. 继续点击 sign in to leetcode &#xff0c;选择使用账号登录&#xff0c;始…

机器人助力Bridge Champ游戏:1.4.2版本如何提升玩家体验

在Bridge Champ游戏中&#xff0c;机器人扮演着桥牌游戏的“无名英雄”角色&#xff0c;默默地提升玩家体验。凭借智能化的设计&#xff0c;这些机器人不仅能够陪练&#xff0c;也大大提升了比赛的流畅度与趣味性。 Bridge Champ是什么 Bridge Champ是一个基于Ignis公链的在线…

服装品牌零售业态融合中的创新发展:以开源 AI 智能名片 S2B2C 商城小程序为视角

摘要&#xff1a;本文以服装品牌零售业态融合为背景&#xff0c;探讨信息流优化和资金流创新的重要作用&#xff0c;并结合开源 AI 智能名片 S2B2C 商城小程序&#xff0c;分析其如何进一步推动服装品牌在零售领域的发展&#xff0c;提高运营效率和用户体验&#xff0c;实现商业…

redis:set集合命令,内部编码,使用场景

个人主页 &#xff1a; 个人主页 个人专栏 &#xff1a; 《数据结构》 《C语言》《C》《Linux》《网络》 《redis学习笔记》 文章目录 前言命令SADDSMEMBERSSISMEMBERSCARDSPOPSMOVESREM集合间操作SINTERSINTERSTORESUNIONSUNIONSTORESDIFFSDIFFSTORE 内部编码使用场景总结 前言…

ssm052游戏攻略网站的设计与实现+vue(论文+源码)-kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;游戏攻略网站设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本游戏攻略网站就是在这…

Java基础-JDBC

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 一、JDBC简介 1.1 什么是JDBC 1.2 JDBC的作用 1.3 JDBC的架构 二、JDBC核心接口与类 2.1 DriverManag…

好好看 3.2.3 | 纯净无广告的四端追剧软件,高清秒播

好好看是一款全新的追剧软件&#xff0c;与网飞猫同一系列&#xff0c;纯净无广告&#xff0c;支持安卓、iOS、TV和PC四端。汇集了Netflix、电影、短剧、剧集、动漫、综艺等资源&#xff0c;并且各大平台资源同步更新。内置多条超清、蓝光、优质等线路&#xff0c;支持投屏、影…

Python爬虫如何处理验证码与登录

Python爬虫如何处理验证码与登录 Python 爬虫在抓取需要登录的网站数据时&#xff0c;通常会遇到两个主要问题&#xff1a;登录验证和验证码处理。这些机制是网站用来防止自动化程序过度抓取数据的主要手段。本文将详细讲解如何使用 Python 处理登录与验证码&#xff0c;以便进…

分布式光伏电站管理的有效措施

分布式光伏电站是一种将太阳能转化为电能的系统&#xff0c;其特点是“自发自用&#xff0c;余电上网”&#xff0c;也就是说&#xff0c;白天利用太阳能进行发电&#xff0c;晚上利用电网进行互补。这种电站建设周期短&#xff0c;见效快&#xff0c;适合于有闲置屋顶或空地的…

濮良贵《机械设计》第十版课后习题答案全解PDF电子版

《机械设计》(第十版)是“十二五”普通高等教育本科国家级规划教材&#xff0c; 是在《机械设计》(第九版)的基础上修订而成的。本次修订主要做了以下几项工作&#xff1a; 1. 内容的适当更新——自本书第九版出版以来&#xff0c; 机械工程及相关领域的新理论、新技术和新标准…

python之正则表达式总结

正则表达式 对于正则表达式的学习&#xff0c;我整理了网上的一些资料&#xff0c;希望可以帮助到各位&#xff01;&#xff01;&#xff01; 我们可以使用正则表达式来定义字符串的匹配模式&#xff0c;即如何检查一个字符串是否有跟某种模式匹配的部分或者从一个字符串中将与…

算法专题:字符串

目录 1. 最长公共前缀 1.1 算法原理 1.2 算法代码 2. 最长回文子串 2.1 算法原理 2.2 算法代码 3. 二进制求和 3.1 算法原理 3.2 算法代码 4. 字符串相乘 4.1 算法原理 4.2 算法代码 1. 最长公共前缀 . - 力扣&#xff08;LeetCode&#xff09; 1.1 算法原理 有以…

[Unity Demo]从零开始制作空洞骑士Hollow Knight第十八集补充:制作空洞骑士独有的EventSystem和InputModule

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、制作空洞骑士独有的EventSystem和InputModule总结 前言 hello大家好久没见&#xff0c;之所以隔了这么久才更新并不是因为我又放弃了这个项目&#xff0c;而…

capl语言

capl:事件型语言 定时器代码 数据类型 capl运算符&#xff08;一&#xff09; capl运算符&#xff08;二&#xff09; 逻辑非&#xff1a;两个条件同时成立则为真&#xff08;1&#xff09;&#xff0c;否则为假&#xff08;0&#xff09;. 逻辑与&#xff1a;只有一个条件…

[渲染层网络层错误] net::ERR_CONTENT_LENGTH_MISMATCH 问题解决

问题描述 问题背景 微信小程序访问后端img资源的时候&#xff0c;偶尔出现这个感叹号&#xff0c;图片加载不出来&#xff0c;但是对应的url贴出来在浏览器中访问&#xff0c;或者重新加载是可以访问的。 错误描述 经查询前端报错 [渲染层网络层错误] net::ERR_CONTENT_LE…

跳蚤市场之商品发布功能

一 商品类别和小类的联动 以下是一个示例代码&#xff0c;展示了如何实现商品类别中大类和小类的联动。 商品大类选择框、小类选择框 的设计 html部分 <form id"category-form"><label for"major-category">大类&#xff1a;</label&g…

LabVIEW气体检测系统

随着工业化进程的加速&#xff0c;环境污染问题愈加严峻&#xff0c;尤其是有害气体的排放对人类生存环境构成了严重威胁。为了更好地监测这些有害气体&#xff0c;开发一个高效、准确且易于操作的气体检测系统显得尤为重要。LabVIEW软件开发的气体检测系统&#xff0c;采用激光…

【三维重建】Semantic Gaussians:开放词汇的3DGS场景理解

文章目录 摘要一、引言二、主要方法1.3D Gaussian Splatting2.其他方法2.1 Gaussian Grouping2.2 GARField 3. 2D Versatile 投影4. 3D Semantic Network4. 推理 四、实验1. 实验设置2.定量结果 论文&#xff1a;https://arxiv.org/pdf/2403.15624 摘要 开放词汇的三维场景理解…

机器学习—前向传播的一般实现

可以写一个函数来实现一个密集的层&#xff0c;那是神经网络的单层&#xff0c;所以定义稠密函数&#xff0c;它将上一层的激活作为输入以及给定层神经元的参数w和b。看下边图片所展示的例子&#xff0c;把所有这些权重向量堆叠成一个矩阵&#xff0c;wnp.array([[1,-3,5][2,4,…

Java实验六 网络和数据库

1. 利用InetAddress编写程序接受用户输入网址&#xff0c;输出这个网址的主机IP地址。 package project; import java.net.InetAddress; import java.net.UnknownHostException; import java.util.Scanner; public class GetIPAddress {public static void main(String[] args…