归并排序----C语言数据结构
目录
- 引言
- 1.归并排序的实现----c
- 2.归并排序的复杂度分析
- 时间复杂度
- 空间复杂度
引言
归并排序(Merge Sort) 是一种基于分治法的排序算法,它的基本思想是将原始数组划分成较小的数组,然后递归地对这些小数组进行排序,最后将排好序的小数组合并成一个整体有序的数组。
归并排序是一种稳定的排序算法,其时间复杂度为 O(n log n),这使得它在大规模数据集上具有较好的性能。
基本应用:
- 排序: 归并排序是一种高效的排序算法,其时间复杂度为 O(n log n)。它对于各种数据分布情况都有较好的性能,特别适用于链表结构。
- 外部排序: 归并排序在外部排序中也很有用,因为它的排序过程不依赖于数据的分布。外部排序是处理大规模数据集无法一次加载到内存的情况下的一种排序方式。
- 合并有序序列: 归并排序的合并过程可以轻松地用于合并两个有序序列。这在数据库操作中常被用来合并两个已排序的结果集。
- 逆序数计算: 归并排序在计算逆序数(数组中的逆序对)时具有优势,因为在归并的过程中可以统计逆序对的数量。
1.归并排序的实现----c
归并排序的思路是:本质是递归
将一个数组分成许多个小数组(直到最后单个数组有序,也就是只有一个元素),再将这些有序的小数组递归,由下往上返回
步骤:
- 开辟动态数组,来复制之后有序的原数组
- 将原数组划分成较小的数组,也就是单元素的数组
- 将有序的数组拷贝,
- 通过动态数组拷贝,返回的有序小数组集成为有序原始数组


//归并排序
void _MergeSort(int* a, int begin, int end, int* tmp)
{//若一个区间只有一个元素,返回if (begin >= end)return;//若区间为不有序//记录中间坐标int mid = (begin + end) / 2;_MergeSort(a, 0, mid, tmp);_MergeSort(a, mid+1, end, tmp);//将有序的小区间集成为有序大区间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++];elsetmp[i++] = a[begin2++];}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//注意拷贝的时候,数组的起始位置与拷贝空间大小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 ");return;}//递归拷贝,分组_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
2.归并排序的复杂度分析
时间复杂度
时间复杂度是O(n log n)
分为俩部分:
合并
每一层的合并操作的总时间复杂度是 O(n)
递归
递归的算法类似于二叉树后序遍历的时间复杂度,也就是递归深度,log n
空间复杂度
空间复杂度是 O(log n)
归并排序的空间复杂度相对较高,主要取决于递归调用的栈空间和临时数组的存储空间。
在最坏情况下,递归树的深度达到 log n ,因此空间复杂度是 O(log n)。此外,合并过程需要额外的 O(n) 空间来存储临时数组。
相关文章:
归并排序----C语言数据结构
目录 引言 1.归并排序的实现----c2.归并排序的复杂度分析时间复杂度空间复杂度 引言 归并排序(Merge Sort) 是一种基于分治法的排序算法,它的基本思想是将原始数组划分成较小的数组,然后递归地对这些小数组进行排序,最后将排好序…...
【网站项目】065健康综合咨询问诊平台
🙊作者简介:拥有多年开发工作经验,分享技术代码帮助学生学习,独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。🌹赠送计算机毕业设计600个选题excel文件,帮助大学选题。赠送开题报告模板ÿ…...
Adobe Camera Raw forMac/win:掌控原始之美的秘密武器
Adobe Camera Raw,这款由Adobe开发的插件,已经成为摄影师和设计师们的必备工具。对于那些追求完美、渴望探索更多创意可能性的专业人士来说,它不仅仅是一个插件,更是一个能够释放无尽创造力的平台。 在数字摄影时代,R…...
OpenHarmony—开发及引用静态共享包(API 9)
HAR(Harmony Archive)是静态共享包,可以包含代码、C库、资源和配置文件。通过HAR可以实现多个模块或多个工程共享ArkUI组件、资源等相关代码。HAR不同于HAP,不能独立安装运行在设备上,只能作为应用模块的依赖项被引用。 接下来&a…...
测试面试题常见题
文章目录 功能测试一个完整的测试计划应该包含哪些内容一个完整的测试用例包含哪些内容?什么时候需要发测试报告?一份测试报告应该包含哪些内容?一个完整的缺陷报告应该包含哪些内容?简述等价类划分法并举例针对具体场景的测试用例…...
代码随想录算法训练营第六天 - 哈希表part02
454.四数之和II 核心思想:利用字典的key,value 4个数组两两分组,nums1nums2 的两两元素之和 及 计数 先存入字典中,然后对nums3和nums4的进行元素相加 然后对比字典中是否有对应的key,有就countvalue class Solution…...
【Javaweb程序设计】【C00165】基于SSM的高考志愿辅助填报系统(论文+PPT)
基于SSM的高考志愿辅助填报系统(论文PPT) 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于ssm的高考志愿辅助填报系统 本系统分为前台系统模块、后台管理员模块以及后台学生模块 前台系统模块:当游客打开系统的网址后&…...
海外云手机为什么吸引用户?
近年来,随着全球化的飞速发展,海外云手机逐渐成为各行各业关注的焦点。那么,究竟是什么让海外云手机如此吸引用户呢?本文将深入探讨海外云手机的三大吸引力,揭示海外云手机的优势所在。 1. 高效的社交媒体运营 海外云…...
将`List<String>`转换为`List<Long>`
将List<String>转换为List<Long> 大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!在Java中,将List<String>转换为List<Long>可以…...
【Unity3D小功能】Unity3D中Text使用超链接并绑定点击事件
推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客 大家好,我是佛系工程师☆恬静的小魔龙☆,不定时更新Unity开发技巧,觉得有用记得一键三连哦。 一、前言 在开发中遇到了要给Text加超链接的需求,研究了实现…...
MyBatis-Plus CRUD 接口
Service CRUD 接口 public String services() {Boolean re false;/**Service CRUD 接口**//**Save 返回boolean **///1、插入一条数据Person person1 new Person();person1.setEmail("123qq.com");person1.setSex("男");//person1.setUser_id(0);//影响…...
在JVM中,Java对象是如何创建、存储和访问的?
在Java虚拟机(JVM)中,Java对象的创建、存储和访问是Java程序运行的核心部分。这个过程涉及到内存管理、对象模型以及运行时数据区域的概念。 1. Java对象的创建: a. 类加载: 在Java程序运行时,类加载器负…...
C++类和对象之进击篇
目录 1.类的6个默认成员函数2.构造函数2.1概念2.2特性 3.析构函数3.1概念3.2特性 4.拷贝构造函数4.1 概念4.2特征 5.赋值运算符重载5.1运算符重载5.2赋值运算符重载5.3前置和后置重载 6.日期类的实现7.const成员8.取地址及const取地址操作符重载 1.类的6个默认成员函数 如果一…...
ElementUI 组件:Container 布局容器
ElementUI安装与使用指南 Container 布局容器 点击下载learnelementuispringboot项目源码 效果图 el-container.vue(Container 布局容器)页面效果图 项目里el-container.vue代码 <script> import PagePath from "/components/PagePat…...
小米商城服务治理之客户端熔断器(Google SRE客户端熔断器)
目录 前言 一、什么是Google SRE熔断器 二、Google SRE 熔断器的工作流程: 三、客户端熔断器 (google SRE 熔断器) golang GRPC 实现 四、客户端熔断器 (google SRE 熔断器) golang GRPC单元测试 大家可以关注个人博客:xingxing – Web Developer …...
Springboot 校验工具类
校验工具类 这个实现逻辑很简单,就是调用string的正则表达式 我这里的代码要导入糊涂工具包 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.7.17</version> </dependency>import…...
编程笔记 html5cssjs 069 JavaScrip Undefined数据类型
编程笔记 html5&css&js 069 JavaScrip Undefined数据类型 一、undefined数据类型二、类型运算小结 在JavaScript中,undefined 是一种基本数据类型,它表示一个变量已经声明但未定义(即没有赋值)或者一个对象属性不存在。 一…...
MySQL 处理JSON字符串
目录 前言 JSON值的部分更新 创建JSON值 JSON 值的规范化、合并和自动包装 合并JSON值 搜索和修改JSON值 JSON路径 JSON值的比较和排序 JSON值的聚合 前言 现在很多数据会以json格式存储,如果你还在用like查询json字符串,那你就OUT了࿰…...
python爬虫-多线程-数据库——WB用户
数据库database的包: Python操作Mysql数据库-CSDN博客 效果: 控制台输出: 数据库记录: 全部代码: import json import os import threading import tracebackimport requests import urllib.request from utils im…...
有向图查询所有环,非递归
图: 有向图查询所有环,非递归: import java.util.*;public class CycleTest {private final int V; // 顶点数private final List<List<Integer>> adjList; // 邻接表public CycleTest(int vertices) {this.V vertices;this.…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
