归并排序----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.…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
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…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
