当前位置: 首页 > news >正文

【排序算法】归并排序

目录

一.基本思想

二.递归版本

三.非递归版本

四.特性总结

1.时间复杂度:O(N*logN)

2.空间复杂度:O(N)

3.稳定性:稳定


一.基本思想

归并排序是采用分治法的一个非常典型的应用。它将已经有序的序列合并为完全有序的序列,即先使得每一个子序列有序,再让子序列之间有序。归并排序建立在归并操作上,以下动图能很好的演示归并排序中归并的过程:

但上图只展示了归并排序中归并的过程,没有对拆分过程的展示,接下来我将具体介绍归并排序的核心步骤。

已知对于两个已经有序的序列而言,使用p1和p2来比较,p1和p2中较小的一个一定就是当前最小的,放入临时数组tmp中,随后指向的p向后移动,再次进行比较,如此就能将两个有序的序列合并为一个有序序列,这就做到了排序。

然而,如何得到两个已经有序的序列呢?这是类似问题,与排序整个序列的主问题是类似的,很明显,已经可以猜到要使用递归来实现了,那么只需要将两个无序序列进行再次拆分,直到序列中仅剩一个数据,那么此时就可以看作是有序的了,这就是拆分过程。 

拆分结束后,就进行归并,每两个已有序的序列合并到一起,再和其他已合并的序列进行合并,最终合并为一个序列,这就是排序后得到的最终结果,下图展示了整个过程:

 具体应该如何拆分?拆分也是有讲究的,不注意会产生问题。一般都会想到取中分割,取序列左端为begin,右端为end,mid自然等于(begin+end)/2,那么就可以围绕mid拆分为左右两个序列,其中mid应该包含在左端,否则会造成死循环,也就是应该分为[begin,mid]和[mid+1,end],证明如下:

二.递归版本

//归并排序-主体
void _Merge(int* a, int* tmp, int begin, int end)
{//结束条件if (begin >= end)return;//拆分int mid = (begin + end) / 2;_Merge(a, tmp, begin, mid);_Merge(a, tmp, mid + 1, end);//归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}//归并排序
void Merge(int* a, int n)
{//创建临时数组int* tmp = (int*)malloc(sizeof(int) * n);_Merge(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}

三.非递归版本

对于非递归版本,就不用考虑拆分的过程了,直接将一个数组看作单个有序的状态开始归并。使用gap来模拟归并的过程,如下所示:

根据上述过程可以得到以下代码,但这样的写法却存在一些问题 ,不妨打印出来看看

//归并排序-主体-(非递归)
void Merge_NonR(int* a, int n)
{//创建临时数组int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//gap控制每组归并的数据个数int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;printf("[%d %d],[%d,%d]", begin1, end1, begin2, end2);int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;printf("\n");}
}

 

可以很明显的看到,在只有10个数据的时候(有效下标为0到9),发生了数组越界的问题 ,那么这就还需要在程序中加入对应的解决方法,从上图可以发现,只要是begin2(上图的10和12)出现了越界(大于等于n)那么后一个序列就是非法的,也就不用归并了,此时可以直接跳出循环直接到下一个gap,那么到最后一轮,end2是越界的(如上图15)此时8到9是有序的,只需要调整end2为9(即n-1)即可。完整实现的代码如下:

//归并排序-主体-(非递归)
void Merge_NonR(int* a, int n)
{//创建临时数组int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//gap控制每组归并的数据个数int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;if (begin2 >= n)break;if (end2 >= n)end2 = n - 1;printf("[%d %d],[%d,%d]", begin1, end1, begin2, end2);int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;printf("\n");}
}

四.特性总结

1.时间复杂度:O(N*logN)

依据二分往下递归,类似于二叉树,总共有LogN层,每层总的归并合计起来可以看作O(N),因此总的时间复杂度可以看作是:O(N*logN)

2.空间复杂度:O(N)

由于开辟了一个大小为N的额外数组,因此归并排序的空间复杂度为O(N)

3.稳定性:稳定

相关文章:

【排序算法】归并排序

目录 一.基本思想 二.递归版本 三.非递归版本 四.特性总结 1.时间复杂度&#xff1a;O(N*logN) 2.空间复杂度&#xff1a;O(N) 3.稳定性&#xff1a;稳定 一.基本思想 归并排序是采用分治法的一个非常典型的应用。它将已经有序的序列合并为完全有序的序列&#xff0c;即…...

游戏AI的创造思路-技术基础-决策树(2)

上一篇写了决策树的基础概念和一些简单例子&#xff0c;本篇将着重在实际案例上进行说明 目录 8. 决策树应用的实际例子 8.1. 方法和过程 8.1.1. 定义行为 8.1.2. 确定属性 8.1.3. 构建决策树 8.1.4. 实施行为 8.1.5. 实时更新 8.2. Python代码 8. 决策树应用的实际例子…...

vue缓存页面,当tab切换时保留原有的查询条件

需求&#xff1a; 切换tab时&#xff0c;查询条件不变 路由页面&#xff1a; 单个页面上加这句话&#xff1a;...

PythonConda系列(亲测有效):【解决方案】Collecting package metadata (current_repodata.json): failed

【解决方案】Collecting package metadata (current_repodata.json&#xff09;: failed 问题描述解决方案小结参考文献 问题描述 在cmd下运行&#xff1a;conda install pylint -y&#xff0c;报错如下&#xff1a; C:\Users\apr> conda install --name apr pylint -y Co…...

web前端开发——标签一(注释、标题、段落、换行、格式、图片)

今天我来针对web前端开发讲解标签一 目录 html标签_标题&段落&换行 注释标签&#xff1a;Ctrl/ 标题标签&#xff1a; h1-h6 段落标签&#xff1a; 换行标签: 格式标签 图片标签_src属性 html标签_标题&段落&换行 注释标签&#xff1a;Ctrl/ Ctrl/ &…...

Django 常见的操作符

在filter() 方法&#xff0c;exclude() 方法中使用大于&#xff0c;小于&#xff0c;模糊匹配等操作符。 常见的操作符如下&#xff1a; 操作符含义示例等于Book.objects.filter(price10)! 或 __ne不等于用于查找字段不等于特定值的记录。但更常用exclude()方法。__gt大于用于…...

AJAX是什么?原生语法格式?jQuery提供分装好的AJAX有什么区别?

ajax 的全称 Asynchronous JavaScript and XML (异步 JavaScript 和 XML)。 AJAX是一种创建交互式网页应用的网页开发技术。其中最核心的依赖是浏览器提供的 XMLHttpRequest 对象&#xff0c;是这个对象使得浏览器可以发出 HTTP 请求与接收 HTTP 响应。实现了在页 面不刷新的…...

docker基础知识以及windows上的docker desktop 安装

记录以供备忘 基础概念&#xff1a; 什么是docker 将程序和环境一起打包&#xff0c;以在不同操作系统上运行的工具软件 什么是基础镜像 选一个基础操作系统和语言后&#xff0c;将对应的文件系统、依赖库、配置等打包为一个类似压缩包的文件&#xff0c;就是基础镜像 什么是…...

【深度学习基础】环境搭建 linux系统下安装pytorch

目录 一、anaconda 安装二、创建pytorch1. 创建pytorch环境&#xff1a;2. 激活环境3. 下载安装pytorch包4. 检查是否安装成功 一、anaconda 安装 具体的安装说明可以参考我的另外一篇文章【环境搭建】Linux报错bash: conda: command not found… 二、创建pytorch 1. 创建py…...

【Sql Server】sql server 2019设置远程访问,外网服务器需要设置好安全组入方向规则

大家好&#xff0c;我是全栈小5&#xff0c;欢迎来到《小5讲堂》。 这是《Sql Server》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 目录 前言1、无法链接…...

idea启动vue项目一直卡死在51%,问题分析及其如何解决

如果你的项目也一直卡在百分之几十&#xff0c;你可以参考下面的方法&#xff0c;试一试能否解决 问题描述&#xff1a; 通过在idea终端中输入命令 npm run serve 启动vue项目&#xff0c;启动进程一直卡在51% 如何解决&#xff1a; 检查 < template > 标签中的html内容…...

基于STM32设计的智能喂养系统(ESP8266+微信小程序)175

基于STM32设计的牛羊喂养系统(微信小程序)(175) 文章目录 一、前言1.1 项目介绍【1】项目功能介绍【2】项目硬件模块组成【3】ESP8266工作模式配置【4】上位机开发【5】项目模块划分1.2 项目功能需求1.3 项目开发背景1.4 开发工具的选择1.5 系统框架图1.6 系统原理图1.7 硬件实…...

第三方支付平台如何完美契合游戏行业?

在数字经济的浪潮中&#xff0c;游戏行业以其独特的魅力和创新能力&#xff0c;成为全球文化和经济交流的重要桥梁。然而&#xff0c;海外游戏商在进军中国市场时&#xff0c;常面临一系列难题。本文将通过一个故事案例&#xff0c;揭示第三方支付平台PASSTO PAY如何帮助海外游…...

计算机网络 5.6网桥与交换机

第六节 网桥与交换机 一、认识网桥 1.功能&#xff1a;连接两个具有相同或相似的网络结构的网络&#xff0c;解决网络之间距离太远问题&#xff0c;提高网络可靠性&#xff0c;还可以起过滤帧的作用而提高网络的性能。 2.适用场合&#xff1a;同构网。 3.特点&#xff1a; …...

CDH实操--集群卸载

作者&#xff1a;耀灵 1、停止正在运行的服务 a、控制台停止集群服务 b、控制台停止Cloudera Management Service c、命令行停止cm服务 systemctl stop cloudera-scm-agent #所有节点执行 systemctl stop cloudera-scm-server #cdh01节点执行2、主线并移除Parcles rm -r…...

5G RedCap调查报告

一、5G RedCap技术背景 5G RedCap(Reduced Capability缩写,轻量化5G),是3GPP标准化组织定义下的5G裁剪版本,是5G面向中高速率连接场景的物联网技术,它的能力介于5G NR(含eMBB和uRLLC)和LPWA(如LTE-M和NR-IoT)之间,如图1所示,是5G-A(5G Advanced)的关键技术之一。…...

模型(卷积、fc、attention)计算量 MAC/FLOPs 的手动统计方法

文章目录 简介背景为什么理解神经网络中的MAC和FLOPs很重要&#xff1f;资源效率内存效率能耗功耗效率 模型优化性能基准研究与发展 FLOPs 和 MACs 定义1. 全连接层 FLOPs 计算步骤 1&#xff1a;识别层参数步骤 2&#xff1a;计算 FLOPs 和 MACs步骤 3&#xff1a;总结结果使用…...

Git 删除包含敏感数据的历史记录及敏感文件

环境 Windows 10 Git 2.41.0 首先备份你需要删除的文件&#xff08;如果还需要的话&#xff09;&#xff0c;因为命令会将本地也删除将项目中修改的内容撤回或直接提交到仓库中&#xff08;有修改内容无法提交&#xff09; 会提示Cannot rewrite branches: You have unstaged …...

vue-tabs标签页引入其他页面

tabs页面 <template> <div class"app-container"> <el-tabs v-model"activeName" type"card" tab-click"handleClick"> <el-tab-pane label"套餐用户列表" name"first"> <user-list r…...

U-net和U²-Net网络详解

目录 U-Net: Convolutional Networks for Biomedical Image Segmentation摘要U-net网络结构pixel-wise loss weight U-Net: Going Deeper with Nested U-Structure for Salient Object Detection摘要网络结构详解整体结构RSU-n结构RSU-4F结构saliency map fusion module -- 显著…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...