当前位置: 首页 > 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…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

PLC入门【4】基本指令2(SET RST)

04 基本指令2 PLC编程第四课基本指令(2) 1、运用上接课所学的基本指令完成个简单的实例编程。 2、学习SET--置位指令 3、RST--复位指令 打开软件(FX-TRN-BEG-C)&#xff0c;从 文件 - 主画面&#xff0c;“B: 让我们学习基本的”- “B-3.控制优先程序”。 点击“梯形图编辑”…...

HTML版英语学习系统

HTML版英语学习系统 这是一个完全免费、无需安装、功能完整的英语学习工具&#xff0c;使用HTML CSS JavaScript实现。 功能 文本朗读练习 - 输入英文文章&#xff0c;系统朗读帮助练习听力和发音&#xff0c;适合跟读练习&#xff0c;模仿学习&#xff1b;实时词典查询 - 双…...

设计模式-3 行为型模式

一、观察者模式 1、定义 定义对象之间的一对多的依赖关系&#xff0c;这样当一个对象改变状态时&#xff0c;它的所有依赖项都会自动得到通知和更新。 描述复杂的流程控制 描述多个类或者对象之间怎样互相协作共同完成单个对象都无法单独度完成的任务 它涉及算法与对象间职责…...

Xcode 16.2 版本 pod init 报错

Xcode 版本升级到 16.2 后&#xff0c;项目执行 pod init 报错&#xff1b; ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchron…...