【排序算法】归并排序

目录

一.基本思想

二.递归版本

三.非递归版本

四.特性总结

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.稳定性:稳定

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

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

相关文章

算法学习day10(贪心算法)

贪心算法&#xff1a;由局部最优->全局最优 贪心算法一般分为如下四步&#xff1a; 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解 一、摆动序列&#xff08;理解难&#xff09; 连续数字之间的差有正负的交替&…

如何将libwebsockets库编译为x86架构

在之前的文章中&#xff0c;我们已经详细介绍了如何交叉编译libwebsockets并将其部署到ELF 1开发板上。然而在调试阶段&#xff0c;发现将libwebsockets在Ubuntu环境下编译为x86架构可能更为方便和高效。 通过在主机环境中编译运用x86架构下的libwebsockets库&#xff0c;可以…

2024年,搞AI就别卷模型了

你好&#xff0c;我是三桥君 2022年11月30日&#xff0c;OpenAI发布了一款全新的对话式通用人工智能工具——ChatGPT。 该工具发布后&#xff0c;仅用5天时间就吸引了100万活跃用户&#xff0c;而在短短2个月内&#xff0c;其活跃用户数更是飙升至1亿&#xff0c;成为历史上增…

github的使用

1.如何将代码会滚到某个提交之前 在GitHub上将代码回滚到之前的版本&#xff0c;可以通过Git命令行实现。以下是几种常用的方法来实现回滚&#xff1a; 方法一&#xff1a;使用 git revert git revert 会生成一个新的提交&#xff0c;这个提交会撤销之前的某个提交的更改。这…

【ARMv8/v9 GIC 系列 1.7 -- GIC PPI | SPI | SGI | LPI 中断使能配置概述】

请阅读【ARM GICv3/v4 实战学习 】 文章目录 GIC 各种中断使能配置PPIs(每个处理器私有中断)SPIs(共享外设中断)SGIs(软件生成的中断)LPIs(局部中断)GIC 各种中断使能配置 在ARM GICv3和GICv4架构中,不同类型的中断(如PPIs、SPIs、SGIs和LPIs)可以通过不同的方式进…

allWebPlugin中间件实现ActiveX插件在谷歌、火狐、Edge浏览器使用

下载并安装allWebPlugin中间件 1、请从下面地址下载allWebPlugin中间件产品&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1xUyQDzOabh7mU7J7TYhtig?pwdz3q0 提取码&#xff1a;z3q0 如下图所示&#xff0c;下载最新allWebPlugin_x86_v2.0.0.14_stable_20240707…

CUDA原子操作

代码 #include <cuda_runtime.h> #include <stdio.h>__global__ void atomicAddAndGet(int *result, int *valueToAdd) {// 原子加法int addedValue atomicAdd(result, *valueToAdd);// 通过原子操作后读取值&#xff0c;确保是加法后的值addedValue *valueToAd…

三级_网络技术_04_中小型网络系统总体规划与设计

1.下列关于路由器技术特征的描述中&#xff0c;正确的是()。 吞吐量是指路由器的路由表容量 背板能力决定了路由器的吞吐量 语音、视频业务对延时抖动要求较低 突发处理能力是以最小帧间隔值来衡量的 2.下列关于路由器技术特征的描述中&#xff0c;正确的是()。 路由器的…

RGB LCD 彩条显示实验

目录 一.RGB TFT-LCD简介 1.1分辨率 1.2像素格式 1.3LCD屏幕接口 1.4LCD时间参数 1.5RGB LCD屏幕时序 1.6像素时钟 二.实验任务 三.模块设计与仿真 3.1读ID模块设计 3.1.1模块设计 3.1.2波形绘制 3.1.3modelsim仿真波形 3.2时钟分频模块 3.2.1模块设计 3.2.2绘制…

算法力扣刷题记录 三十七【二叉树层序遍历】

前言 二叉树递归遍历和二叉树迭代遍历 实现的前中后序遍历都归类深度搜索&#xff1b; 广度搜索如何实现&#xff1f;一层结束&#xff0c;再继续下一层搜索&#xff1a;层序遍历。 一、题目阅读 【102.二叉树的层序遍历】 给你二叉树的根节点 root &#xff0c;返回其节点值…

服务攻防——中间件Jboss

文章目录 一、Jboss简介二、Jboss渗透2.1 JBoss 5.x/6.x 反序列化漏洞&#xff08;CVE-2017-12149&#xff09;2.2 JBoss JMXInvokerServlet 反序列化漏洞&#xff08;CVE-2015-7501&#xff09;2.3 JBossMQ JMS 反序列化漏洞&#xff08;CVE-2017-7504&#xff09;2.4 Adminis…

【逆向基础】十、工具分享之DIE(Detect It Easy)

一、简介 DIE&#xff08;Detect It Easy&#xff09;是一款可以轻松检测PE文件的程序&#xff1b;其主要作用是查壳&#xff0c;并将pe文件的内容解析出来&#xff0c;包括PE文件中包含的导入函数、导出函数的名称及地址&#xff0c;入口函数地址等&#xff0c;是技术人员分析…

如何在小红书上面有效地种草?

文末领取小红书电商开店运营教程&#xff01; 小红书是一个以内容分享为主的社交平台&#xff0c;大家喜欢在这里分享自己的生活体验和心得&#xff0c;其中就包括各种产品的使用感受。 那么我们要想在小红书上有效地种草&#xff0c;首先就需要了解并掌握小红书的种草文化。 …

Elasticsearch详细介绍

B站对应视频&#xff1a; Elasticsearch01-01.为什么学习elasticsearch_哔哩哔哩_bilibili 大多数日常项目&#xff0c;搜索肯定是访问频率最高的页面之一。目前搜索功能是基于数据库的模糊搜索来实现的&#xff0c;存在很多问题。 首先&#xff0c;查询效率较低。 由于数据…

libcoap3对接华为云平台

文章目录 前言一、平台注册二、引入源码库1.libcoap仓库编译2.分析网络报文3.案例代码4.编译&运行 总结 前言 通过libcoap3开源代码库对接华为云平台&#xff0c;本文章将讨论加密与不加密的方式对接华为云平台。 一、平台注册 首先&#xff0c;你需要在华为云平台上创建…

QT之嵌入外部第三方软件到本窗体中

一、前言 使用QT开发&#xff0c;有时需要调用一些外部程序&#xff0c;但是单独打开一个外部窗口有的场合很不合适&#xff0c;最好是嵌入到开发的QT程序界面中。还有就是自己开发的n个程序&#xff0c;一个主程序托n个子程序&#xff0c;为了方便管理将各个程序独立&#xf…

安全防御---防火墙实验1

安全防御—防火墙实验1 一、实验拓扑与要求 要求&#xff1a; 1、DMZ区内的服务器&#xff0c;办公区仅能在办公时间内&#xff08;9&#xff1a;00-18:00)可以访问&#xff0c;生产区的设备全天可以访问 2、生产区不允许访问互联网&#xff0c;办公区和游客区允许访问互联网 …

华为手机联系人不见了怎么恢复?3个解决方案

华为手机联系人列表就像是我们精心编织的社交网络之网。然而&#xff0c;有时&#xff0c;这张网可能会因为各种原因而意外破损&#xff0c;联系人信息消失得无影无踪&#xff0c;让我们陷入“人脉孤岛”的困境。华为手机联系人不见了怎么恢复&#xff1f;别担心&#xff0c;我…

计算机网络——数据链路层(以太网)

目录 局域网的数据链路层 局域网可按照网络拓扑分类 局域网与共享信道 以太网的两个主要标准 适配器与mac地址 适配器的组成与运作 MAC地址 MAC地址的详细介绍 局域网的mac地址格式 mac地址的发送顺序 单播、多播&#xff0c;广播mac地址 mac帧 如何取用…

【面试八股总结】线程基本概念,线程、进程和协程区别,线程实现

一、什么是线程&#xff1f; 线程是“轻量级进程”&#xff0c;是进程中的⼀个实体&#xff0c;是程序执⾏的最小单元&#xff0c;也是被系统独立调度和分配的基本单位。 线程是进程当中的⼀条执行流程&#xff0c;同⼀个进程内多个线程之间可以共享代码段、数据段、打开的文件…