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

数据结构—归并排序-C语言实现

引言:归并排序跟快速排序一样,都运用到了分治的算法,但是归并排序是一种稳定的算法,同时也具备高效,其时间复杂度为O(N*logN)

算法图解: 

 

 然后开始归并:

 

 就是这个思想,拆成最小子问题后再进行归并(两个有序数组的排序问题)

下面是代码:

 

void merge_sort(int* arry, int size) {//保证接口一致性,再调子函数assert(arry);int* tmp = (int*)malloc(sizeof(int) * size);_merge(arry, 0, size - 1,tmp);//_merge2(arry, 0, size - 1, tmp);free(tmp);
}
void _merge(int* arry, int left, int right, int* tmp) {if (right - left <= 0)return;int mid = left + (right - left >> 1);//找到中间值//递归,拆分子问题_merge(arry, left, mid, tmp);_merge(arry, mid + 1, right, tmp);merge_arry(arry, left, mid, mid + 1, right, tmp);
}
void merge_arry(int* arry, int begin1, int end1, int begin2, int end2, int* tmp) {int index = begin1;int left = begin1;int right = end2;while (begin1 <= end1 && begin2 <= end2) {if (arry[begin1] < arry[begin2]) {tmp[index++] = arry[begin1++];}else {tmp[index++] = arry[begin2++];}}if (begin1 <= end1) {for (int i = begin1; i <= end1; i++) {tmp[index++] = arry[i];}}else {for (int i = begin2; i <= end2; i++) {tmp[index++] = arry[i];}}//再拷贝回原数组for (int i = left; i <= right; i++) {arry[i] = tmp[i];}
}

上面是它的递归实现,那么思考如何使用非递归实现呢?

 

 同时要控制grap的循环次数,grap小于等于数组大小即可

下面是代码:

void _merge2(int* arry, int left, int right, int* tmp) {int grap = 1;while (grap<=right+1) {for (int i = left; i <= right; i += 2 * grap) {int begin1 = i, end1 = i + grap - 1;int begin2 = i + grap, end2 = i + 2 * grap - 1;if (end1 > right)end1 = right;if (end2 > right)end2 = right;merge_arry(arry, begin1, end1, begin2, end2, tmp);}grap = grap * 2;}}
void merge_sort(int* arry, int size) {assert(arry);int* tmp = (int*)malloc(sizeof(int) * size);//_merge(arry, 0, size - 1,tmp);_merge2(arry, 0, size - 1, tmp);free(tmp);
}

相关文章:

数据结构—归并排序-C语言实现

引言&#xff1a;归并排序跟快速排序一样&#xff0c;都运用到了分治的算法&#xff0c;但是归并排序是一种稳定的算法&#xff0c;同时也具备高效&#xff0c;其时间复杂度为O(N*logN) 算法图解&#xff1a; 然后开始归并&#xff1a; 就是这个思想&#xff0c;拆成最小子问题…...

Multiple CORS header ‘Access-Control-Allow-Origin‘ not allowed

今天在修改天天生鲜超市项目的时候&#xff0c;因为使用了前后端分离模式&#xff0c;前端通过网关统一转发请求到后端服务&#xff0c;但是第一次使用就遇到了问题&#xff0c;比如跨域问题&#xff1a; 但是&#xff0c;其实网关里是有配置跨域的&#xff0c;只是忘了把前端项…...

msvcp100.dll丢失怎样修复,msvcp100.dll丢失问题全面解析

msvcp100.dll是一个动态链接库文件&#xff0c;属于 Microsoft Visual C Redistributable 的一个组件。它包含了 C 运行时库&#xff0c;这些库在运行程序时会被加载到内存中。msvcp100.dll文件的主要作用是为基于 Visual C 编写的程序提供必要的运行时支持。 当您运行一个基于…...

最新AI智能问答系统源码/AI绘画系统源码/支持GPT联网提问/Prompt应用+支持国内AI提问模型

一、AI创作系统 SparkAi创作系统是基于国外很火的ChatGPT进行开发的AI智能问答系统和AI绘画系统。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图…...

全连接网络实现回归【房价预测的数据】

也是分为data&#xff0c;model&#xff0c;train&#xff0c;test import torch import torch.nn as nn import torch.nn.functional as F import torch.optim as optimclass FCNet(nn.Module):def __init__(self):super(FCNet,self).__init__()self.fc1 nn.Linear(331,200)s…...

mysql八股

1、请你说说mysql索引&#xff0c;以及它们的好处和坏处 检索效率、存储资源、索引 索引就像指向表行的指针&#xff0c;是一个允许查询操作快速确定哪些行符合WHERE子句中的条件&#xff0c;并检索到这些行的其他列值的数据结构索引主要有普通索引、唯一索引、主键索引、外键…...

MATLAB算法实战应用案例精讲-【优化算法】狐猴优化器(LO)(附MATLAB代码实现)

代码实现 MATLAB LO.m %======================================================================= % Lemurs Optimizer: A New Metaheuristic Algorithm % for Global Optimization (LO)% This work is published in Journal of "Applied …...

C#WPF动态资源和静态资源应用实例

本文实例演示C#WPF动态资源和静态资源应用 一、资源概述 静态资源(StaticResource)指的是在程序载入内存时对资源的一次性使用,之后就不再访问这个资源了。 动态资源(DynamicResource)指的是在程序运行过程中然会去访问资源。 WPF中,每个界面元素都含有一个名为Resources…...

游戏逆向中的 NoClip 手段和安全应对方式

文章目录 墙壁边界寻找碰撞 NoClip 是一种典型的黑客行为&#xff0c;允许你穿过墙壁&#xff0c;所以 NoClip 又可以认为是避免碰撞体积的行为 墙壁边界 游戏中设置了碰撞体作为墙壁边界&#xff0c;是 玩家对象 和墙壁发生了碰撞&#xff0c;而不是 相机 玩家对象有他的 X…...

nodejs+vue流浪猫狗救助领养elementui

第三章 系统分析 10 3.1需求分析 10 3.2可行性分析 10 3.2.1技术可行性&#xff1a;技术背景 10 3.2.2经济可行性 11 3.2.3操作可行性&#xff1a; 11 3.3性能分析 11 3.4系统操作流程 12 3.4.1管理员登录流程 12 3.4.2信息添加流程 12 3.4.3信息删除流程 13 第四章 系统设计与…...

Css Flex 弹性布局中的换行与溢出处理方法

Css Flex 弹性布局中的换行与溢出处理方法 CSS弹性布局&#xff08;Flex&#xff09;是CSS3中的一种新的布局方式&#xff0c;它能够帮助我们更加灵活地布局元素。在Flex弹性布局中&#xff0c;元素的布局仅依赖于父容器的设置&#xff0c;而不再需要复杂的相对或绝对定位。本…...

linux系统与应用

Windows中的硬盘和盘符的关系&#xff1b; 硬盘通常为一块到两块&#xff1b;数量与盘符没有直接关系&#xff1b;一块硬盘可以分为多个盘符&#xff0c;如c,d,e,f,g等&#xff1b;当然理论上也可以一块硬盘只有一个盘符&#xff1b;学习linux时&#xff0c;最好使用固态硬盘&a…...

MySQL的结构化语言 DDL DML DQL DCL

一、SQL结构化语言介绍 数据查询语言DQL&#xff1a;其语句称为“数据检索语言”&#xff0c;用以从库中获取数据&#xff0c;确定数据怎样在应用程序给出&#xff0c;保留select是dql&#xff08;也是所有sql&#xff09;用的最多的动词 数据操作语言DML:其语句包括动词insert…...

P5488 差分与前缀和

传送门:洛谷 前题提要:包含了简单的生成函数思想以及多项式乘法,是一道不可多得的多项式好题.故记录一下. 题意:给定一个长为 n 的序列 a&#xff0c;求出其 k 阶差分或前缀和。结果的每一项都需要对 1004535809取模。 对于差分和前缀和我们分开来讨论. 先讨论前缀和部分: …...

uboot启动流程-uboot内存分配

一. uboot启动流程 _main 函数中会调用 board_init_f 函数&#xff0c;本文继续简单分析一下 board_init_f 函数。 具体分析 board_init_f函数的第二部分&#xff1a;内存分配代码。 本文继上一篇文章的学习&#xff0c;地址如下&#xff1a; uboot启动流程-涉及board_init…...

LeetCode 面试题 08.02. 迷路的机器人

文章目录 一、题目二、C# 题解 一、题目 设想有个机器人坐在一个网格的左上角&#xff0c;网格 r 行 c 列。机器人只能向下或向右移动&#xff0c;但不能走到一些被禁止的网格&#xff08;有障碍物&#xff09;。设计一种算法&#xff0c;寻找机器人从左上角移动到右下角的路径…...

画CMB天图使用Planck配色方案

使用Planck的配色方案&#xff1a; 全天图&#xff1a; 或者方形图&#xff1a; 使用下面设置即可&#xff1a; import pspy, pixell from pspy.so_config import DEFAULT_DATA_DIR pixell.colorize.mpl_setdefault("planck")此方法不会改变matplotlib默认配色方案…...

成都瀚网科技有限公司:抖店精选联盟怎么用?

抖音精选联盟是抖音电商平台提供的一项服务&#xff0c;旨在为商家提供更多的推广机会和销售渠道。然而&#xff0c;很多人对于如何使用抖店精选联盟以及如何开通这项服务不太了解。本文将为您详细介绍抖店精选联盟的使用和激活流程。 第一节&#xff1a;如何使用抖店精选联盟 …...

第二章:最新版零基础学习 PYTHON 教程(第五节 - Python 输入/输出–如何在Python中打印而不换行?)

一般来说,从 C/C++ 切换到 Python 的人想知道如何在 python 中打印两个或多个变量或语句而不进入新行。由于Python print() 函数默认以换行符结尾。Python 有一个预定义的格式,如果你使用 print(a_variable) 那么它会自动转到下一行。 例子: # 输入:[csdn, csdnforcsdn] …...

C++实现集群聊天服务器

C实现集群聊天服务器 JSON Json是一种轻量级的数据交换模式&#xff08;也叫做数据序列化方式&#xff09;。Json采用完全独立于编程语言的文本格式来存储和表示数据。见解和清晰的层次结构使得Json称为理想的数据交换语言。易于阅读和编写。同时也易于支持机器解析和生成&am…...

MedGemma 1。5在Linux环境下的部署与优化

MedGemma 1.5在Linux环境下的部署与优化 1. 引言 MedGemma 1.5是谷歌最新发布的开源医疗AI模型&#xff0c;专门针对医学影像和文本数据处理进行了深度优化。这个40亿参数的轻量级模型不仅能处理CT、MRI等三维医学影像&#xff0c;还能分析病理切片和电子健康记录&#xff0c…...

语音合成延迟优化:IndexTTS-2-LLM网络IO调优实战

语音合成延迟优化&#xff1a;IndexTTS-2-LLM网络IO调优实战 1. 为什么语音合成总在“等”&#xff1f;从用户卡顿说起 你有没有试过在语音合成页面点下“开始合成”&#xff0c;然后盯着进度条数秒——明明只是一句话&#xff0c;却要等3秒、5秒&#xff0c;甚至更久&#x…...

BootstrapBlazor通知组件:如何实现声音提示功能

BootstrapBlazor通知组件&#xff1a;如何实现声音提示功能 【免费下载链接】BootstrapBlazor 项目地址: https://gitcode.com/gh_mirrors/bo/BootstrapBlazor BootstrapBlazor是一个功能丰富的Blazor组件库&#xff0c;提供了各种UI组件来增强Web应用的用户体验。其中…...

HP-Socket技术演讲视频描述撰写指南:关键词与吸引力

HP-Socket技术演讲视频描述撰写指南&#xff1a;关键词与吸引力 【免费下载链接】HP-Socket High Performance TCP/UDP/HTTP Communication Component 项目地址: https://gitcode.com/gh_mirrors/hp/HP-Socket HP-Socket是一款高性能跨平台网络通信框架&#xff0c;专为…...

AudioLDM-S效果惊艳:科幻飞船、城市夜晚,AI生成的音效有多真实?

AudioLDM-S效果惊艳&#xff1a;科幻飞船、城市夜晚&#xff0c;AI生成的音效有多真实&#xff1f; 想象一下&#xff0c;你正在制作一个科幻短片&#xff0c;需要一个飞船引擎启动时低沉、充满能量的嗡鸣声。或者&#xff0c;你想为一段城市夜景视频配上背景音&#xff0c;需…...

6种压缩黑科技如何彻底解决文件处理的效率难题

6种压缩黑科技如何彻底解决文件处理的效率难题 【免费下载链接】7-Zip-zstd 7-Zip with support for Brotli, Fast-LZMA2, Lizard, LZ4, LZ5 and Zstandard 项目地址: https://gitcode.com/gh_mirrors/7z/7-Zip-zstd 为何压缩工具总是陷入"速度与压缩率"的两难…...

OpenClaw+GLM-4.7-Flash学习助手:自动整理课程笔记与生成复习题

OpenClawGLM-4.7-Flash学习助手&#xff1a;自动整理课程笔记与生成复习题 1. 为什么需要自动化学习助手&#xff1f; 去年备考研究生时&#xff0c;我每天要处理3-4小时的课程视频。最痛苦的不是听课本身&#xff0c;而是课后整理&#xff1a;手动截取关键片段、转录字幕、标…...

三步解锁QQ空间历史说说备份:数据留存与管理实用指南

三步解锁QQ空间历史说说备份&#xff1a;数据留存与管理实用指南 【免费下载链接】GetQzonehistory 获取QQ空间发布的历史说说 项目地址: https://gitcode.com/GitHub_Trending/ge/GetQzonehistory QQ空间数据备份是许多用户保存青春记忆和重要记录的需求。GetQzonehist…...

3步告别微信单向好友:WechatRealFriends帮你轻松识别谁删了你

3步告别微信单向好友&#xff1a;WechatRealFriends帮你轻松识别谁删了你 【免费下载链接】WechatRealFriends 微信好友关系一键检测&#xff0c;基于微信ipad协议&#xff0c;看看有没有朋友偷偷删掉或者拉黑你 项目地址: https://gitcode.com/gh_mirrors/we/WechatRealFrie…...

OpenClaw多模型管理:同时接入百川2-13B-4bits与其他开源大模型

OpenClaw多模型管理&#xff1a;同时接入百川2-13B-4bits与其他开源大模型 1. 为什么需要多模型管理&#xff1f; 去年冬天&#xff0c;我尝试用OpenClaw自动化处理一批技术文档的翻译和摘要任务时&#xff0c;遇到了一个典型问题&#xff1a;当处理简单段落翻译时&#xff0…...