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

【数据结构】 归并排序超详解

1.基本思想

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。(有点像二叉树递归,大家可以联想二叉树理解)

在这里插入图片描述
下面是动图展示:
在这里插入图片描述

2.代码展示及讲解

讲解部分在注释中,配合上述两张图食用更佳

#include <stdio.h>void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end){return;}//递归返回的判断条件int mid = (begin + end) / 2;//作为数组递归的左边(类似于左子树)和右边(右子树)_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);//对数组递归,利用mid将数组分成左右两个数组,并分别不断递归,并将递归排列好的元素储存到辅助数组tmp中,然后用内存函数将tmp中的元素复制到原数组中int left1 = begin;int right1 = mid;int left2 = mid + 1;int right2 = end;//递归的左右边界int t = begin;while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){tmp[t++] = a[left1++];}else{tmp[t++] = a[left2++];}}while (left1 <= right1){tmp[t++] = a[left1++];}while (left2 <= right2){tmp[t++] = a[left2++];}// 在递归的过程中对左右两边进行排序,如果上述排序方法一下子看不懂的话,//可以在纸上模拟一下,绝对简单,就是将两个数组中的元素按照从小到大依次放到辅助数组tmp中memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));//转移排好的元素
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);**//创建一个新数组作为辅助数组,储存递归的元素,并将其进行排序,//然后使用内存函数将辅助数组中的排列好的元素转移到原数组中**if (tmp == NULL){perror("malloc fail");return;}//判断空间是否开辟成功_MergeSort(a, 0, n - 1, tmp);//借助子函数开始递归
}int main()
{int a[10] = { 1,3,5,7,9,2,4,6,8,10 };MergeSort(a, 10);for (int i = 0; i < 10; i++){printf("%d ", a[i]);}return 0;
}

3.归并排序的特性总结

归并排序的特性总结:

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

以上就是关于C++中的类的6个默认成员函数详解的全部内容,希望我的文章能对你有所帮助 感谢你的观看!
在这里插入图片描述

相关文章:

【数据结构】 归并排序超详解

1.基本思想 归并排序&#xff08;MERGE-SORT&#xff09;是建立在归并操作上的一种有效的排序算法,该算法是采用分治法&#xff08;Divide andConquer&#xff09;的一个非常典型的应用。 将已有序的子序列合并&#xff0c;得到完全有序的序列&#xff0c;即先使每个子序列有序…...

Debezium系列之:深入理解GTID全局事务标识,并记录一次数据库重启造成数据丢失的原因和解决方案

Debezium系列之:深入理解GTID,并记录一次数据库重启造成数据丢失的原因和解决方案 一、背景二、深入理解什么是GTID三、深入理解gtid的uuid部分四、判断GTID之间的顺序大小五、解决方案一、背景 hive数据库的表与源头业务数据库的数据不一致,经过检查发现源头数据库发生了重…...

格式化内存卡后,如何找回丢失的监控视频?

随着摄像头的应用越来越广泛&#xff0c;很多监控摄像头采用了内存卡作为存储介质&#xff0c;方便用户存储和查看摄像头拍摄的视频文件。然而&#xff0c;由于各种原因&#xff0c;监控摄像头的内存卡有时会被意外格式化导致重要数据的丢失&#xff0c;给用户带来诸多困扰。 那…...

《动手学深度学习(PyTorch版)》笔记4.8

注&#xff1a;书中对代码的讲解并不详细&#xff0c;本文对很多细节做了详细注释。另外&#xff0c;书上的源代码是在Jupyter Notebook上运行的&#xff0c;较为分散&#xff0c;本文将代码集中起来&#xff0c;并加以完善&#xff0c;全部用vscode在python 3.9.18下测试通过。…...

助力水下潜行:浮力调节系统仿真

01.建设海洋强国 海洋蕴藏着丰富的资源&#xff0c;二十大报告强调&#xff0c;要“发展海洋经济&#xff0c;保护海洋生态环境&#xff0c;加快建设海洋强国”。建设海洋强国旨在通过科技创新驱动、合理开发利用海洋资源、强化海洋环境保护与生态修复、提升海洋经济质量等多个…...

Mysql常用sql语句

1、建表语句 --建表语句 CREATE TABLE students (id INT PRIMARY KEY AUTO_INCREMENT,name VARCHAR(50),age INT ); 2、插入语句 --插入测试数据 insert into test_2 values(1,zhangsan); 3、查询语句 --查询语句 MySQL [test_drds_2]> select * from test_2; -------…...

dubbo rpc序列化

序列化配置 provider <dubbo:service interface"com.example.DemoService" serialization"hessian2" ref"demoService"/>consumer <dubbo:reference id"demoService" interface"com.example.DemoService" seria…...

【C语言】va_list(可变参数处理)

C 语言中的 va_list 类型允许函数接受可变数量的参数&#xff0c;这在编写需要处理不定数量参数的函数时非常有用。va_list 类型是在 stdarg.h 头文件中定义的&#xff0c;它允许函数处理可变数量的参数。下面我们将详细介绍 va_list 的用法以及实际应用示例。 一、va_list的用…...

负载均衡下的webshell连接

一、环境配置 1.在Ubuntu上配置docker环境 我们选择用Xshell来将环境资源上传到Ubuntu虚拟机上&#xff08;比较简单&#xff09; 我们选择在root模式下进行环境配置&#xff0c;先将资源文件复制到root下&#xff08;如果你一开始就传输到root下就不用理会这个&#xff09; …...

5-4 D. DS串应用—最长重复子串

题目描述 求串的最长重复子串长度&#xff08;子串不重叠&#xff09;。例如&#xff1a;abcaefabcabc的最长重复子串是串abca&#xff0c;长度为4。 输入 测试次数t t个测试串 输入样例&#xff1a; 3 abcaefabcabc szu0123szu szuabcefg 输出 对每个测试串&#xff0c;输出最…...

C语言实现12种排序算法

1.冒泡排序 思路&#xff1a;比较相邻的两个数字&#xff0c;如果前一个数字大&#xff0c;那么就交换两个数字&#xff0c;直到有序。 时间复杂度&#xff1a;O(n^2)&#xff0c;稳定性&#xff1a;这是一种稳定的算法。 代码实现&#xff1a; void bubble_sort(int arr[],…...

C语言应用实例——贪吃蛇

&#xff08;图片由AI生成&#xff09; 0.贪吃蛇游戏背景 贪吃蛇游戏&#xff0c;最早可以追溯到1976年的“Blockade”游戏&#xff0c;是电子游戏历史上的一个经典。在这款游戏中&#xff0c;玩家操作一个不断增长的蛇&#xff0c;目标是吃掉出现在屏幕上的食物&#xff0c…...

Mac如何设置一位数密码?

一、问题 Mac如何设置一位数密码&#xff1f; 二、解答 1、打开终端 2、清除全局账户策略 sudo pwpolicy -clearaccountpolicies 输入开机密码&#xff0c;这里是看不见的&#xff0c;输入完回车即可 3、重新设置密码 &#xff08;1&#xff09;打开设置-->用户和群组…...

运动编辑学习笔记

目录 跳舞重建&#xff1a; 深度运动重定向 Motion Preprocessing Tool anim_utils MotionBuilder 跳舞重建&#xff1a; https://github.com/Shimingyi/MotioNet 深度运动重定向 https://github.com/DeepMotionEditing/deep-motion-editin 游锋生/deep-motion-editin…...

C#小结:ScottPlot 5.0在VS2022桌面开发的应用(以winform为例)

目录 一、官网文档地址 二、在VS2022中安装Scottplot 三、拖动Scottplot 四、使用Scottplot 五、效果图 一、官网文档地址 官网地址&#xff1a;ScottPlot 5.0 食谱 本文内容来自于官网&#xff0c;选取了官网的一些比较好用的功能展示&#xff0c;如需学习更多功能&a…...

Jmeter性能测试: Jmeter 5.6.3 分布式部署

目录 一、实验 1.环境 2.jmeter 配置 slave 代理压测机 3.jmeter配置master控制器压测机 4.启动slave从节点检查 5.启动master主节点检查 6.运行jmeter 7.观察jmeter-server主从节点变化 二、问题 1.jmeter 中间请求和响应乱码 一、实验 1.环境 &#xff08;1&#…...

跟着cherno手搓游戏引擎【15】DrawCall的封装

目标&#xff1a; Application.cpp:把渲染循环里的glad代码封装成自己的类&#xff1a; #include"ytpch.h" #include "Application.h"#include"Log.h" #include "YOTO/Renderer/Renderer.h" #include"Input.h"namespace YO…...

Qt实现窗口吸附屏幕边缘 自动收缩

先看效果&#xff1a; N年前的QQ就可以吸附到屏幕边缘&#xff0c;聊天时候非常方便&#xff0c;不用点击状态栏图标即可呼出QQ界面 自己尝试做了一个糙版的屏幕吸附效果。 关键代码&#xff1a; void Widget::mouseMoveEvent(QMouseEvent *e) {int dx e->globalX() - l…...

shell脚本之免交互

目录 一、Here Document 免交互 1、交互与免交互的概念 2、 Here Document 概述 二、Here Document 应用 1、使用cat命令多行重定向 2、使用tee命令多行重定向 3、使用read命令多行重定向 4、使用wc -l统计行数 5、使用passwd命令用户修改密码 6、Here Document 变量…...

Ajax入门与使用

目录 ◆ AJAX 概念和 axios 使用 什么是 AJAX&#xff1f; 怎么发送 AJAX 请求&#xff1f; 如何使用axios axios 函数的基本结构 axios 函数的使用场景 1 没有参数的情况 2 使用params参数传参的情况 3 使用data参数来处理请求体的数据 4 上传图片等二进制的情况…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...