数据结构(C语言)之对归并排序的介绍与理解

目录

一·归并排序介绍:

二·归并排序递归版本:

2.1·递归思路:

2.2·递归代码实现:

三·归并排序非递归版本:

3.1·非递归思路:

3.2·非递归代码实现:

四·归并排序性能分析:


欢迎大佬:

羑悻的小杀马特-CSDN博客羑悻的小杀马特关注c++,c语言,数据结构领域.https://blog.csdn.net/2401_82648291?spm=1011.2266.3001.5343


一·归并排序介绍:

 首先,归并排序可以理解为用分治策略的一种排序算法,这里可以用递归的思想去理解,对一个数组进行不断分割,每次分为两个子数组,直到最后剩下的是一个数据也就是不可再分割,那么就开始对末两个子数组进行归并,然后归回去,在原数组得到有序的数组。(也就是说再每次归并的两个数组一定要是有序的)。

二·归并排序递归版本:

2.1·递归思路:

实现代码的同时,首先要先分割原数组为两个子数组,这里就用到了分割方法,分割的区间为[left,mid][mid+1,right]这样分割,可以避免出现区间循环的问题([偶数,偶数+1])。

(注:其它细节见代码处注释)

2.2·递归代码实现:

//归并的时候要确保每两个区间内数据都是有序的
//这里可以是递归,但是不让它每次都开辟空间,故这里用了一个子函数来完成递归操作

//这里可以假设完成的是最后一次归并操作,通过调用两次子函数假设已经把最后两个区间排好序了,最后
//再对它们归并即可。
void _mergesort(int* a, int* tmp, int begin, int end) {
	if (begin >= end) {
		return;
	}//递归终止条件:多为不断分割区间到只剩下一个数据结束直接归并
	int mid = (begin + end) / 2;
	_mergesort(a, tmp, begin, mid);//这里由于如果选mid-1和mid的话,当区间为【偶数,偶数+1】就会分割死循环
	_mergesort(a, tmp, mid + 1, end);
	int begin1 = begin;
	int begin2 = mid + 1;
	int end1 = mid;
	int end2 = end;
	//由于每次归并都是从原数组归到tmp,而最后又要把tmp对应的位置数据copy回原数组,故当我们归并排序到tmp数组
	//应对应原数组下标放入
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {
			tmp[i++] = a[begin1++];
		}
		else {
			tmp[i++] = a[begin2++];
		}
	}
	if (begin1 > end1) {
		while (begin2 <= end2) {
			tmp[i++] = a[begin2++];
		}
	}
	else {
		while (begin1 <= end1) {
			tmp[i++] = a[begin1++];
		}
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
	//这里开辟的tmp数组,可防止原数组被覆盖,每次归并完为有序的数组copy回原数组原位置

}
//这里递归每次分割,最后成一个数据自然有序,接着每次归并后归回去。
void mergesort(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror(malloc);
		return;
	}
	_mergesort(a, tmp, 0, n - 1);
	free(tmp);
	tmp = NULL;
}

三·归并排序非递归版本:

3.1·非递归思路:

上面这个非递归的归并排序,是先是gap=1,归并当出现gap可以=2的时候再整体归并,这时整个数组并未被gap=1遍历完分好组,也是可以的,下面介绍一种直接被gap遍历完分好组再进行归并的方法:

非递归的话,就是把数组先分为一个个的每个子区间只有一个数据,然后让它们每两个成一对进行归并操作,等这一轮进行完后,从数组首开始给它们两个数据为一个区间,每两个区间就会满足区间内数据均有序,从而再次进行归并操作,依次类推,最后会生成两组有序归并完后得到原数组即为有序的原数组。

这里用gap来记录每组数据个数,通过循环来改变gap,gap定值时候用for循环来确定每次分两组情况。

而这里需要考虑的重点就是越界问题,当分区间的时候无论奇数个还是偶数个数据都会存在越界现象,而如果为奇数个的话,当gap为1的时候,最后会存在越界,而偶数的时候,可能往后面才出现越界,而画图可知道,由于每次第一组的区间首位是i不会越界故越界的是第二组要么是都越界,要么第二个区间的第二个数字越界。(其他细节见源代码注释)

画图解释:

3.2·非递归代码实现:

//这里非递归,可以从每组一个数据开始归并,然后有序,然后每两个就有序了,
// 最后会变为最后的两组要么归并要么舍弃一组
// 接着每组两个归并成四个,依次每组gap个数据调整到最后剩下两组,即再次归并得到最后有序的数组
//画图可知道每次如果出现越界只能是最后两组,而这两组的第一组的end1为i不可能越界
//故可以分数据为偶数个还是奇数个,如果偶数个那么gap为1时不越界但是之后会,为奇数时gap为1最后一组
//越界,然后出现越界肯定是第二组,然后begin2如果越,就break,而end2越界就变为n-1接着归并
//可发现gap跳的时候每次都是跳的2的多少次方,即当剩下的组区间有越界但里面有数据一定是有序的,变为n-1归并
void  mergesortNoR(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror(malloc);
		return;
	}

	for (int gap = 1; gap < n; gap = 2 * gap) {
		for (int i = 0; i < n; i += 2 * gap) {
			//两边闭区间
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			if (begin2 >= n) {
				break;
				//由于最后两组如果出现越界的话end1始终不会越界,一旦越界begin2一定越界
				//那么就防止后面的归并出错,就停止归并
			}
			if (end2 >= n) {
				end2 = n - 1;
				//当最后一次gap+的循环,肯定第二组begin2不越界,越界可能是end2,而前几次的归并
				//已经把最后一次第二组的数据排好序了那么更改end2然后再次归并就可以了
			}
			int i = begin1;
			int start = begin1;
			int last = end2;
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] < a[begin2]) {
					tmp[i++] = a[begin1++];
				}
				else {
					tmp[i++] = a[begin2++];
				}
			}
			if (begin1 > end1) {
				while (begin2 <= end2) {
					tmp[i++] = a[begin2++];
				}
			}
			else {
				while (begin1 <= end1) {
					tmp[i++] = a[begin1++];
				}
			}
			memcpy(a + start, tmp + start, sizeof(int) * (last - start + 1));


		}
	}

}

四·归并排序性能分析:

复杂度:首先由于归并排序每次是折半归,故它的时间复杂度类似于二叉树为o(n*logn),而由于多开了n个空间的数组作为归并暂存数组用来copy。空间复杂度为:o(n)。

稳定性:首先稳定性就是当用排序算法给数组排序的时候,它里面原本的相同的元素相对位置不变化就称为其的稳定性。对于归并排序而言,每次两个数组归并成一个数组,只要我们改动一下当begin1与begin2对应数字相等,就放入begin1对应的数据,这样顺序就不变了,也可以说归并排序是稳定的。

就是把<改成=。

应用:可用于正常的排序,或者大文件的排序,由于归并排序是在内存中进行,有的时候文件太大无法正常进行,可以把它分为一个个小文件到内存归为有序,最终整合使得大文件也有序。 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

51单片机-LCD液晶显示

目录 前言: 一. LCD1602模块简介 二. 代码功能实现 三.总结 前言: 本文主要是51单片机的LCD液晶显示,使用的是LCD1602.下面是详细介绍和完整代码,欢迎大家的点赞,评论和关注.感谢. 一. LCD1602模块简介 LCD1602 模块具有以下特点&#xff1a; 显示特点&#xff1a; 可以…

uniapp视频组件层级太高,解决方法使用subNvue原生子体窗口

目录 前言 先看一下uniapp官网的原话&#xff1a; subNvue的一些参数介绍 subNvues使用方法&#xff1a; 绑定id 显示 subNvue 弹出层 subNvue.show() 参数信息 subNvue.hide() 参数信息 在使用subNvue 原生子体窗口 遇到的一些问题 前言 nvue 兼容性 以及使用方式 控…

【Transformer(7)】Transformer架构解析

一、Transformer结构图 从上图可以看到&#xff1a; Transformer结构主要由编码和解码两大部分组成&#xff1a; &#xff08;1&#xff09;输入- position embedding - patch embedding &#xff08;2&#xff09;编码器 多头注意力机制 Add & NormMLP Add & Norm q,…

Python的Pillow(图像处理库)的一些学习笔记

Python的Pillow库是一个非常强大的图像处理库。 安装Pillow库&#xff1a; 在终端或命令行中输入以下命令来安装Pillow&#xff1a; pip install pillow 升级库&#xff1a; pip install pillow --upgrade 一些基础的应用 1、图像文件方面的&#xff1a; 打开文件 …

批量重命名大解放!自定义取文本左侧长度,轻松实现文件名焕新之旅!

文件管理是我们日常工作和生活中不可或缺的一部分。然而&#xff0c;面对成千上万的文件&#xff0c;手动重命名无疑是一项繁琐且耗时的任务。今天&#xff0c;我们为您推荐一款高效便捷的批量文件重命名工具——文件批量改名高手&#xff0c;让您轻松实现取文本左的长度来进行…

心链12-----队伍页业务完善+匹配算法实现随机匹配(最短距离算法)

心链 — 伙伴匹配系统 搜索队伍 我们选择vant组件库里的基础搜索框&#xff0c;复制到TeamPage页面&#xff0c;同时还有查询为空时&#xff0c;显示的无结果页面&#xff08;用户页面以写过&#xff09; 因为&#xff0c;我们一次性挂载本质性也是搜索队伍&#xff0c;所以…

探索智慧林业系统的总体架构与应用

背景&#xff1a; 随着人们对森林资源保护和管理的重视&#xff0c;智慧林业系统作为一种新兴的林业管理手段&#xff0c;正在逐渐受到广泛关注和应用。智慧林业系统的总体架构设计与应用&#xff0c;将现代信息技术与林业管理相结合&#xff0c;为森林资源的保护、管理和利用…

为什么要将Modbus转成MQTT

什么是Modbus Modbus 是一种串行通信协议&#xff0c;最初由Modicon&#xff08;现在的施耐德电气Schneider Electric&#xff09;于1979年开发&#xff0c;用于可编程逻辑控制器&#xff08;PLC&#xff09;之间的通信。Modbus协议设计简单&#xff0c;易于部署和维护&#xf…

Fort Firewall防火墙工具v3.12.13

软件介绍 Fort Firewall是一款开源系统的免费防火墙&#xff0c;体积小巧、占用空间不大&#xff0c;可以为用户的电脑起到保护作用&#xff0c;该软件可以控制程序访问网络&#xff0c;控制用户的电脑网速&#xff0c;用户可以更轻松便捷的进行网络安全防护&#xff0c;保护系…

k8s测试题

k8s集群k8s集群node01192.168.246.11k8s集群node02192.168.246.12k8s集群master 192.168.246.10 k8s集群nginxkeepalive负载均衡nginxkeepalive01&#xff08;master&#xff09;192.168.246.13负载均衡nginxkeepalive02&#xff08;backup&#xff09;192.168.246.14VIP 192…

Flowable项目启动报错#java.time.LocalDateTime cannot be cast to java.lang.String

Flowable 项目启动后报错 flow项目第一次启动创建表成功&#xff0c;但是第二次启动时报错信息如下&#xff1a; 1、Error creating bean with name ‘appRepositoryServiceBean’ defined in class 2、Error creating bean with name ‘flowableAppEngine’: FactoryBean t…

Parallels Desktop for Mac 19.4.0 (build 54570) - 在 Mac 上运行 Windows

Parallels Desktop for Mac 19.4.0 (build 54570) - 在 Mac 上运行 Windows Parallels Desktop 19 请访问原文链接&#xff1a;Parallels Desktop for Mac 19.4.0 (build 54570) - 在 Mac 上运行 Windows&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者…

深度学习课程设计:构建未来的教育蓝图

深度学习课程设计&#xff1a;构建未来的教育蓝图 在近年来&#xff0c;深度学习已经从一项前沿的技术发展成为计算机科学领域不可或缺的一部分。随着其在多个行业中的应用日益增多&#xff0c;对深度学习教育的需求也在急剧上升。对于计划将深度学习纳入学术课程的教育者而言…

socket通信(C语言+Python)

在socket文件夹下创建server.c和client.c。 服务端代码&#xff08;server.c&#xff09;&#xff1a; #include <stdio.h> #include <Winsock2.h> void main() {WORD wVersionRequested;WSADATA wsaData;int err;wVersionRequested MAKEWORD( 1, 1 );err WSAS…

Ubuntu22.04之解决:无法关机和重启问题(二百四十三)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

用 DataGridView 控件显示数据

使用DataGridView&#xff0c;可以很方便显示数据。 &#xff08;1&#xff09;Visual Studio版本&#xff1a;Visual Studio 2022 &#xff08;2&#xff09;应用程序类型&#xff1a;windows form &#xff08;3&#xff09;编程语言&#xff1a;C# 一、目标框架 .NET Fra…

问题:学生品德不良的矫正与教育可以采取以下措施()。 #其他#学习方法#微信

问题&#xff1a;学生品德不良的矫正与教育可以采取以下措施()。 A、创设良好的交流环境,消除情绪障碍 B、提高道德认识,消除意义障碍 C、锻炼学生与诱因作斗争的意志力 D、消除习惯惰性障碍 E、发现积极因素,多方法协同进行,促进转化 参考答案如图所示

numpy入门笔记

学习参考&#xff1a; 菜鸟教程 numpy入门博客 numpy入门视频 NumPy安装 默认情况使用国外线路&#xff0c;国外太慢&#xff0c;我们使用清华的镜像 pip3 install numpy scipy matplotlib -i https://pypi.tuna.tsinghua.edu.cn/simple一、创建数组 numpy.array(object, dt…

基于fabric封装一个简单的图片编辑器(vue 篇)

介绍 前言vue demo版本react 版本 前言 对 fabric.js 进行二次封装&#xff0c;实现图片编辑器的核心功能。核心代码 不依赖 ui响应式框架vue ,react 都适用。 只写了核心编辑相关代码便于大家后续白嫖二次开发 核心代码我就没有打包发布 会 和 业务代码一起放到项目中。 vu…

discuz点微同城源码34.7+全套插件+小程序前端

discuz点微同城源码34.7全套插件小程序前后端 模板挺好看的 带全套插件 自己耐心点配置一下插件 可以H5可以小程序