【归并排序】C++数据结构实现归并排序完整代码

2023-05-16

归并排序（Merging Sort）

定义：把两个或者多个有序的序列合并为一个。

递归调用方式实现方式实现代码：

一、归并排序函数入口

//归并排序入口
template <typename T>
void MergingSort(T myarray[], int length)
{
	T* pResult = new T[length];//新数组，用于保存结果
	MergingSort(myarray, pResult, 0, length - 1, length);//调用重载函数
	delete[]pResult;//释放内存
	return;
}

二、归并排序重载函数

//归并排序重载函数
template <typename T>
void MergingSort(T myarray[], T* pResult,int left,int right,int length)//length是为了显示信息
{
	if (left >= right)
	{
		return;
	}//递归出口
	int mid = (left + right) / 2;//从中间分开
	MergingSort(myarray, pResult, left, mid, length);//对左半部分归并排序
	MergingSort(myarray, pResult, mid + 1, right, length);//对右半部分归并排序
	//上面因为左半部分归并排序完成，右半部分归并排序完成，所以下面是合并左半部分和右半部分了
	Merge(myarray, pResult, left, mid, right, length);
	return;
}

三、归并函数

//2路归并函数，用于把两个有序子序列归并为一个
//left指向第一个序列开头元素
//mid指向第一个序列末尾元素
//right指向第二个序列末尾元素
template <typename T>
void Merge(T myarray[], T* pResult, int left, int mid, int right, int length)
{
	cout << "Merge():left=" << left << "right=" << right << "mid=" << mid << endl;
	cout << "元素值begin:" << endl;
	for (int i = 0; i < length; i++)
	{
		cout << myarray[i] << ' ';
	}
	//把myarray指定的left到right 的范围内的数据享福知道pResult（临时空间）中
	for (int i = left; i <= right; ++i)
	{
		pResult[i] = myarray[i];
	}
	cout << endl;
	int curpos1 = left;//第一个序列的开始元素
	int curpos2 = mid + 1;//第二个序列的开始元素
	int curpos3 = left;//最终合并好的序列的开始元素
	while (curpos1 <= mid && curpos2 <= right)
	{
		if (pResult[curpos1] <= pResult[curpos2])//使用<=是为了算法的稳定性
		{
			myarray[curpos3] = pResult[curpos1];
			curpos1++;
			curpos3++;
		}
		else
		{
			myarray[curpos3] = pResult[curpos2];
			curpos2++;
			curpos3++;
		}
	}
	while (curpos1 <= mid)//子序列1比子序列2长
	{
		//直接把子序列1中剩余的内容放入myarray中
		myarray[curpos3] = pResult[curpos1];
		curpos1++;
		curpos3++;
	}
	while (curpos2 <= right)//子序列2比子序列1长
	{
		//直接把子序列1中剩余的内容放入myarray中
		myarray[curpos3] = pResult[curpos2];
		curpos2++;
		curpos3++;
	}
	cout << "元素值end:" << endl;
	for (int i = 0; i < length; i++)
	{
		cout<< myarray[i]<<" ";
	}
	cout << endl;
	return;
}

四、算法时间复杂度

归并排序的时间复杂度是： O ( n l o g n ) O(nlogn) O(nlogn)

五、算法空间复杂度

归并排序的空间复杂度是： O ( n + l o g n ) = O ( n ) O(n+logn)=O(n) O(n+logn)=O(n)

六、递归调用实现归并排序完整代码

#include <iostream>
using namespace std;
//2路归并函数，用于把两个有序子序列归并为一个
//left指向第一个序列开头元素
//mid指向第一个序列末尾元素
//right指向第二个序列末尾元素
template <typename T>
void Merge(T myarray[], T* pResult, int left, int mid, int right, int length)
{
	cout << "Merge():left=" << left << "right=" << right << "mid=" << mid << endl;
	cout << "元素值begin:" << endl;
	for (int i = 0; i < length; i++)
	{
		cout << myarray[i] << ' ';
	}
	//把myarray指定的left到right 的范围内的数据享福知道pResult（临时空间）中
	for (int i = left; i <= right; ++i)
	{
		pResult[i] = myarray[i];
	}
	cout << endl;
	int curpos1 = left;//第一个序列的开始元素
	int curpos2 = mid + 1;//第二个序列的开始元素
	int curpos3 = left;//最终合并好的序列的开始元素
	while (curpos1 <= mid && curpos2 <= right)
	{
		if (pResult[curpos1] <= pResult[curpos2])//使用<=是为了算法的稳定性
		{
			myarray[curpos3] = pResult[curpos1];
			curpos1++;
			curpos3++;
		}
		else
		{
			myarray[curpos3] = pResult[curpos2];
			curpos2++;
			curpos3++;
		}
	}
	while (curpos1 <= mid)//子序列1比子序列2长
	{
		//直接把子序列1中剩余的内容放入myarray中
		myarray[curpos3] = pResult[curpos1];
		curpos1++;
		curpos3++;
	}
	while (curpos2 <= right)//子序列2比子序列1长
	{
		//直接把子序列1中剩余的内容放入myarray中
		myarray[curpos3] = pResult[curpos2];
		curpos2++;
		curpos3++;
	}
	cout << "元素值end:" << endl;
	for (int i = 0; i < length; i++)
	{
		cout<< myarray[i]<<" ";
	}
	cout << endl;
	return;
}
//归并排序重载函数
template <typename T>
void MergingSort(T myarray[], T* pResult,int left,int right,int length)//length是为了显示信息
{
	if (left >= right)
	{
		return;
	}//递归出口
	int mid = (left + right) / 2;//从中间分开
	MergingSort(myarray, pResult, left, mid, length);//对左半部分归并排序
	MergingSort(myarray, pResult, mid + 1, right, length);//对右半部分归并排序
	//上面因为左半部分归并排序完成，右半部分归并排序完成，所以下面是合并左半部分和右半部分了
	Merge(myarray, pResult, left, mid, right, length);
	return;
}
//归并排序入口
template <typename T>
void MergingSort(T myarray[], int length)
{
	T* pResult = new T[length];//新数组，用于保存结果
	MergingSort(myarray, pResult, 0, length - 1, length);//调用重载函数
	delete[]pResult;//释放内存
	return;
}
int main()
{
	int arr[] = { 16,1,45,23,99,2,18 ,67,42,10 };
	int length = sizeof(arr) / sizeof(arr[0]);
	MergingSort(arr, length);
	cout << "归并排序的结果为：";
	for (int i = 0; i < length; i++)
	{
		cout << arr[i] << " ";
	}
	return 0;
}

七、运行图片

非递归调用方式实现归并排序

一、主要代码

//非递归实现归并排序
template <typename T>
void MergingSort_noRecu(T myarray[], int length)
{
	if (length <= 1)
	{
		return;
	}
	T* pResult = new T[length];//新数组，用于保存数据
	//表示两个子序列位置
	int left, mid, right;
	int distence = 1;//间隔，开始时元素是紧挨着的两个进行比较，两个元素之间下表间隔1
	int subseqTotal = length;//当前子序列数量，开始是把一个元素算一个子序列
	int times = 0;//归并次数
	while (subseqTotal > 1)//只要没有最终合并成1个序列，就一直循环
	{
		times++;
		cout << "-----------这是第" << times << "次归并------------。" << endl;
		for (int i = 0; i < length; i += (distence * 2))
		{
			left = i;
			mid = left + distence - 1;
			if (mid >= length)
			{
				break;
			}
			right = 2 * mid - left + 1;
			if (right >= length)//保证right合法
			{
				right = length - 1;
			}
			//必须要保证数据都合法
			if (left <= mid && right > left && right > mid)
			{
				//肯定是两个序列，能合并
				Merge(myarray, pResult, left, mid, right, length);
				subseqTotal--;//两个序列合并成一个，序列数目减少
			}
			else
			{
				//数据出错，不能合并，直接退出
				break;
			}
		}//end for i
		distence *= 2;
	}//end while
	delete[]pResult;
	return;
}

二、完整代码

#include <iostream>
using namespace std;
//2路归并函数，用于把两个有序子序列归并为一个
//left指向第一个序列开头元素
//mid指向第一个序列末尾元素
//right指向第二个序列末尾元素
template <typename T>
void Merge(T myarray[], T* pResult, int left, int mid, int right, int length)
{
	cout << "Merge():left=" << left << "right=" << right << "mid=" << mid << endl;
	cout << "元素值begin:";
	for (int i = 0; i < length; i++)
	{
		cout << myarray[i] << ' ';
	}
	//把myarray指定的left到right 的范围内的数据享福知道pResult（临时空间）中
	for (int i = left; i <= right; ++i)
	{
		pResult[i] = myarray[i];
	}
	cout << endl;
	int curpos1 = left;//第一个序列的开始元素
	int curpos2 = mid + 1;//第二个序列的开始元素
	int curpos3 = left;//最终合并好的序列的开始元素
	while (curpos1 <= mid && curpos2 <= right)
	{
		if (pResult[curpos1] <= pResult[curpos2])//使用<=是为了算法的稳定性
		{
			myarray[curpos3] = pResult[curpos1];
			curpos1++;
			curpos3++;
		}
		else
		{
			myarray[curpos3] = pResult[curpos2];
			curpos2++;
			curpos3++;
		}
	}
	while (curpos1 <= mid)//子序列1比子序列2长
	{
		//直接把子序列1中剩余的内容放入myarray中
		myarray[curpos3] = pResult[curpos1];
		curpos1++;
		curpos3++;
	}
	while (curpos2 <= right)//子序列2比子序列1长
	{
		//直接把子序列1中剩余的内容放入myarray中
		myarray[curpos3] = pResult[curpos2];
		curpos2++;
		curpos3++;
	}
	cout << "元素值end:";
	for (int i = 0; i < length; i++)
	{
		cout<< myarray[i]<<" ";
	}
	cout << endl;
	return;
}
//归并排序重载函数
template <typename T>
void MergingSort(T myarray[], T* pResult,int left,int right,int length)//length是为了显示信息
{
	if (left >= right)
	{
		return;
	}//递归出口
	int mid = (left + right) / 2;//从中间分开
	MergingSort(myarray, pResult, left, mid, length);//对左半部分归并排序
	MergingSort(myarray, pResult, mid + 1, right, length);//对右半部分归并排序
	//上面因为左半部分归并排序完成，右半部分归并排序完成，所以下面是合并左半部分和右半部分了
	Merge(myarray, pResult, left, mid, right, length);
	return;
}
//归并排序入口
template <typename T>
void MergingSort(T myarray[], int length)
{
	T* pResult = new T[length];//新数组，用于保存结果
	MergingSort(myarray, pResult, 0, length - 1, length);//调用重载函数
	delete[]pResult;//释放内存
	return;
}
//非递归实现归并排序
template <typename T>
void MergingSort_noRecu(T myarray[], int length)
{
	if (length <= 1)
	{
		return;
	}
	T* pResult = new T[length];//新数组，用于保存数据
	//表示两个子序列位置
	int left, mid, right;
	int distence = 1;//间隔，开始时元素是紧挨着的两个进行比较，两个元素之间下表间隔1
	int subseqTotal = length;//当前子序列数量，开始是把一个元素算一个子序列
	int times = 0;//归并次数
	while (subseqTotal > 1)//只要没有最终合并成1个序列，就一直循环
	{
		times++;
		cout << "-----------这是第" << times << "次归并------------。" << endl;
		for (int i = 0; i < length; i += (distence * 2))
		{
			left = i;
			mid = left + distence - 1;
			if (mid >= length)
			{
				break;
			}
			right = 2 * mid - left + 1;
			if (right >= length)//保证right合法
			{
				right = length - 1;
			}
			//必须要保证数据都合法
			if (left <= mid && right > left && right > mid)
			{
				//肯定是两个序列，能合并
				Merge(myarray, pResult, left, mid, right, length);
				subseqTotal--;//两个序列合并成一个，序列数目减少
			}
			else
			{
				//数据出错，不能合并，直接退出
				break;
			}
		}//end for i
		distence *= 2;
	}//end while
	delete[]pResult;
	return;
}
int main()
{
	int arr[] = { 16,1,45,23,99,2,18 ,67,42,10 };
	int length = sizeof(arr) / sizeof(arr[0]);
	//MergingSort(arr, length);
	MergingSort_noRecu(arr, length);
	cout << "归并排序的结果为：";
	for (int i = 0; i < length; i++)
	{
		cout << arr[i] << " ";
	}
	return 0;
}

三、运行结果

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

【归并排序】C++数据结构实现归并排序完整代码的相关文章

Linux下phpmyadmin忘记root的登录密码，找回方法

第一步 xff1a 执行 etc init d mysql stop 结束当前正在运行的mysql进程第二步 xff1a 执行 usr bin mysqld safe skip grant tables 用mysql安全模式运行并跳过权限
matlab郭彦甫-听课笔记-02

可以分块 xff0c 分块之后可以进行分块执行run section 关系运算符 xff1a 61 不等于取余函数 xff1a mod a b rem a b switch case case case otherwise 连乘函数 xf
51单片机硬件介绍

1 单片机是啥单片机 xff0c 简称MCU xff0c 是微型计算机 xff0c 集成了一部计算机许多硬件功能 xff0c 有CPU 存储器 xff08 ROM RAM xff09 等 2 有了这样一个单片机芯片后 xff0c 怎么将程
matlab硬件支持包离线安装-（安装文件夹错误）

dSupport Software Downloader MATLAB amp Simulinkhttps ww2 mathworks cn support install support software downloader html
小结：卸载SolidWorks2018-＞重新安装系统-＞安装SolidWorks2020

因为卸载SW2018卸载不干净 xff0c 所以在安装SW20版一直在出错 xff0c 错误如下 xff1a 这个错误解决后继续安装 xff0c 又发现没有出现原本序列号的那一界面 xff0c 然后还有异型孔向导安装不了 xff0c 最后还
FreeRTOS信号量基于STM32

目录概述一信号量基本概念 1 二值信号量 2 计数信号量 3 互斥信号量 4 递归信号量二二值信号量运作机制三计数信号量运作机制四常用信号量函数接口讲解 1 创建二值信号量 xSemaphoreCreateBinary 2
FreeRTOS互斥量基于STM32

文章目录一互斥量基本概念二互斥量的优先级继承机制三互斥量应用场景四互斥量运作机制五互斥量函数接口讲解 1 互斥量创建函数 xSemaphoreCreateMutex 2 递归xSemaphoreCreateRecursi
FreeRTOS事件组基于STM32

概述文章对事件组的 xff0c 应用场景 xff0c 运作机制 xff0c 以及事件的创建 xff0c 删除 xff0c 等待 xff0c 置位 xff0c 同步等操作文章目录概述一事件标志组简介 1 事件位事件标志 2 事件组
FreeRTOS任务通知基于STM32

文章目录一任务通知简介二任务通知的运作机制三任务通知的函数接口讲解 1 xTaskGenericNotify 2 xTaskNotifyGive 3 vTaskNotifyGiveFromISR 4 xTaskNotify 5
FreeRTOS软件定时器基于STM32

文章目录一软件定时器的基本概念二软件定时器应用场景三软件定时器的精度四软件定时器的运作机制五软件定时器函数接口讲解 1 软件定时器创建函数 xTimerCreate 2 软件定时器启动函数 xTimerStart 3 软
FreeRTOS内存管理基于STM32

目录一内存管理的基本概念二内存管理的应用场景三 heap 4 c 1 内存申请函数 pvPortMalloc 2 内存释放函数 vPortFree 四内存管理的实验五内存管理的实验现象一内存管理的基本概念在计算系统中
关于ECSHOP模板架设的服务器php版本过高报错的解决方法集合

1 admin index php admin sms url php ECSHOP模板报错 xff1a Strict Standards mktime You should be using the time function inst
FreeRTOS中断管理基于STM32

文章目录一异常与中断的基本概念二中断的介绍三和中断相关的名词解释四中断管理的运作机制五中断延迟的概念六中断管理的应用场景七中断管理讲解八中断管理实验九中断管理实验现象一异常与中断的基本概念异常是导致
链表基础知识详解（非常详细简单易懂）

概述 xff1a 链表作为 C 语言中一种基础的数据结构 xff0c 在平时写程序的时候用的并不多 xff0c 但在操作系统里面使用的非常多不管是RTOS还是Linux等使用非常广泛 xff0c 所以必须要搞懂链表 xff0c 链表分为单
FreeRTOS临界段的保护

什么是临界段临界段用一句话概括就是一段在执行的时候不能被中断的代码段在 FreeRTOS 里面 xff0c 这个临界段最常出现的就是对全局变量的操作 xff0c 全局变量就好像是一个枪把子 xff0c 谁都可以对他开枪 xff0c 但
SPI通讯协议详解基于STM32

SPI 协议简介 SPI 协议是由摩托罗拉公司提出的通讯协议 Serial Peripheral Interface xff0c 即串行外围设备接口 xff0c 是一种高速全双工的通信总线它被广泛地使用在 ADC LCD 等设备与 MC
C语言编译过程

C语言的编译过程 xff1a 预处理编译汇编链接 gcc E hello c o hello i 1 预处理 gcc S hello i o hello s 2 编译 gcc c hello s o hello o 3 汇编 gcc
C语言数组详解

目录一数组的概念二数组的分类 2 1 按元素的类型分类 2 2 按维数分类三数组的定义 3 1 一维数组的定义格式 xff1a 3 2 二维数组的定义四定义并初始化 4 1 一维数组的初始化 4 2 二维数组的初始化五
C语言动态分配内存

文章目录一动态分配内存的概述二静态分配动态分配三动态分配函数 3 1 malloc 3 2 free 3 3 calloc 3 4 realloc 四内存泄漏一动态分配内存的概述在数组一章中 xff0c 介绍过数组的长
嵌入式C语言（入门必看）

目录 STM32的数据类型 const关键字 static 关键字 volatile关键字 extern关键字 struct结构体 enum typedef define 回调函数 ifdef ifndef else if 嵌入式开发中既有

随机推荐

ESP32上手指南

乐鑫的ESP32微控制器是一款集成有2 4 GHz Wi Fi和蓝牙4 0双模的物联网芯片方案 xff0c 采用台积电 TSMC 超低功耗的40纳米工艺代工片上集成有天线开关射频巴伦功率放大器接收低噪声放大器滤波器电源管理模块等
基于STM32硬币识别检测

本设计基于ARM内核的单片机STM32F4的高识别率硬币识别装置 xff0c 主要应用于各公共营业场所 xff0c 如各超市 xff0c 自动售货机 xff0c 公共交通等它应该能完成一角 xff08 分新版旧版 xff09 xff0c
PHP多维数组排序

User 61 M 39 User 39 Incomelog 61 M 39 incomelog 39 user 61 User gt select now date 61 39 2015 02 09 39 integral 61 arra
PH电极酸碱度检测

最近做了一个项目是关于PH电极测酸碱度的一个仪器简单地说 xff1a 玻璃电极是一种氢离子选择性电极 xff0c 相当于一个对玻璃膜两侧氢离子浓度差异能产生附加电势差的盐桥 xff0c 一般的盐桥是为了消除浓差电势或者液体接触电势这种附
关于调试RTC时钟出现的问题

此次做一个项目出现了一个令我很不解的问题 xff0c 就是RTC时钟 xff0c 代码是提前写好的 xff0c 当时是用的STM32F103ZET6最小系统板 xff0c 所有功能都是没有问题的但是最终我画好的PCB芯片用的是STM32F
vscode编写c/c++及自动配置c/c++环境

目录前言所需的工具链接一 vscode中文设置及c c 43 43 插件安装1 中文设置2 c c 43 43 插件安装二环境配置1 解压AutoVsCEnv WPF V1 993自动配置工具压缩包2 运行AutoVsCEnv WPF
安装最新版keil5编译报错*** target ‘target 1‘ uses arm-compiler ‘default compiler version 5‘ which i，keil5.37版

原因是 missing compiler version5 xff0c 缺少V5编译器 xff08 compiler version5 xff09 xff0c 因为打开的工程比较老 xff0c 是用v5的编译器写的 xff0c 而现在下的k
vector的理解以及模拟实现

vector的理解以及模拟实现 vector介绍vector常见函数介绍vector模拟实现及迭代器失效讲解 vector介绍 vector文档 vector是表示可变大小数组的序列容器就像数组一样 xff0c vector也采用的连续存
《数据库的嵌套查询和统计查询》

选择Study数据库 xff0c 用SQL语句进行以下查询操作 1 xff0e 嵌套查询求选修了数据结构的学生学号和成绩 span class token keyword SELECT span Sno span class token
由NP完全问题引出动态规划——状态压缩DP

所有部分都应当在非强制的情况下组合回一起要记住 xff0c 你重组的那部分原来就是你拆解的因此 xff0c 如果你不能让它们组合回来的话 xff0c 那一定是有原因的要想尽一切办法 xff0c 除了用锤头 IBM手册 1925 Par
IMU学习的一些记录（不含推导公式，仅做了解）

IMU xff08 惯性测量元件 xff09 测量三个量 xff1a 1 加速度 2 角速度3地磁 xff08 具体内容不展开 xff09 原始数据采集 IMU芯片与单片机硬件享连 xff0c 通过程序处理数据上位机 xff08 一般运行
STL简介

STL主要包含了容器迭代器算法和string四部分标准库算法对迭代器而不是容器进行操作因此 xff0c 算法不能 xff08 直接 xff09 添加或删除元素一容器容器为存储和管理数据对象的集合 xff0c 包含了三种容器 x
Linux开发工具(5)——git

文章目录 git版本控制器git是什么git的操作clone仓库到本地上传本地文件到git git版本控制器 git是什么标题也说了git就是一个版本控制器 xff0c 版本控制器是用来保存一个文件的历史版本 xff0c 如果有需要可以进
微信支付的常见问题，invalide code

这段时间在做微信支付开发 xff0c 在公司的公众号审批下来后 xff0c 我这边的测试用例也已经开发完毕 xff0c 于是拿着具体的数据来调试了 xff0c 大段大段的代码就不贴了 xff0c demo里有 xff0c 这里就说说调试过
记一次串口调试工具发指令无反应问题

最近新采购一块板子 xff0c 需要连接Android端进行USB串口通讯首先需要在Windows上用串口调试工具先调通来确认板子没问题 xff0c 调的时候发现 xff0c 咋发指令都不通 xff0c 换了几个调试工具都不行 xff0c
PyQt5 基本语法（七）：布局管理

文章目录布局管理1 布局概念2 布局方式2 1 手动布局2 1 1 绝对布局2 1 2 方法重写 2 2 布局管理器 3 布局管理器概念4 使用演示5 详细使用5 1 QLayout5 1 1 作用5 1 2 功能描述5 1 2 1 构造
Qt 实现简单的tcp网络通信

文章目录成品效果图 xff1a 代码 xff1a 工具头文件tool hUI文件代码 ui widget h 窗口头文件 widget h xff1a 窗口源文件widget cpp 相关代码说明 xff1a Qt获取本机ip Qt 打开
strrchr函数

lt string h gt 描述 C 库函数 char strrchr const char str int c 在参数 str 所指向的字符串中搜索最后一次出现字符 c xff08 一个无符号字符 xff09 的位置声明下面是 st
独轮车串级pid初了解

今晚满脑子都是如何调好独轮车 xff0c 应该用哪一套方案的时候 xff0c 我找到了一名博主 xff0c 他应该和我也一样大 xff0c 感觉他真的很值得我去学习 xff0c 所有东西几乎都是依靠自己手动制作 xff0c 也不凭借商业化的
【归并排序】C++数据结构实现归并排序完整代码

归并排序 C 43 43 数据结构实现归并排序完整代码归并排序 xff08 Merging Sort xff09 定义 xff1a 把两个或者多个有序的序列合并为一个递归调用方式实现方式实现代码 xff1a 一归并排序函数入口归并排

【归并排序】C++数据结构实现归并排序完整代码

归并排序（Merging Sort）

定义：把两个或者多个有序的序列合并为一个。

递归调用方式实现方式实现代码：

一、归并排序函数入口

二、归并排序重载函数

三、归并函数

四、算法时间复杂度

归并排序的时间复杂度是： O ( n l o g n ) O(nlogn) O(nlogn)

五、算法空间复杂度

归并排序的空间复杂度是： O ( n + l o g n ) = O ( n ) O(n+logn)=O(n) O(n+logn)=O(n)

六、递归调用实现归并排序完整代码

七、运行图片

非递归调用方式实现归并排序

一、主要代码

二、完整代码

三、运行结果

【归并排序】C++数据结构实现归并排序完整代码 的相关文章

随机推荐

热门标签

【归并排序】C++数据结构实现归并排序完整代码的相关文章