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

排序算法8----归并排序(非递归)(C)

       1、介绍

        归并排序既可以是内排序(在内存上的数据排序),也可以是外排序(磁盘上)(硬盘)(在文件中的数据排序)。

        其他排序一般都是内排序。

        区别于快速排序的非递归,归并排序非递归不适合使用栈。

        因为快速排序的本质是一种前序递归,而归并排序的本质是一种后序递归,并没有“根”来区分左右。

        那么归并排序的非递归应该怎么样实现呢?

        2、思想

        我们先想想归并的思想和目的:递归的分治是将数组分割成两边有序的子序列,然后再合并这两个。那么我们是否可以直接将数组中两两元素归并呢?答案是:对的!因为我们将数组中所有元素看作两两一组(每组数据中都各有一个元素),那么这一组中的两个元素单个来看就是有序的子序列,然后合并这两个元素。再往上就是四四一组(每组数据中都各有两个有序的元素),八八一组........37d6c6e9443a437cb6846fbf4345fcf2.png

        听起来好像很简单,其实坑很多,下面慢慢实现。

        3、代码

void MergeSortNonR_incline(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");exit(-1);}int gap = 1;//1-1归//gap代表归并每组数组个数,即gap个和gap个归并while (gap < n){for (int i = 0; i < n; i += 2 * gap)//[0,n){int begin1 = i, end1 = i + gap - 1;//第一组int begin2 = i + gap, end2 = i + 2 * gap - 1;//第二组//[begin1,end1],[begin2,end2] 归并//[0,0]-[1,1]归,[2,2]-[3,3],[4,4]-[5,5]....//[0,1]-[2,3]归, [4,5]-[6,7]....//[0,3]-[4,7]归, [8,11]-[11,15]......// ......//注意:begin1不会越界,end1,begin2,end2都可能越界,所以要修正if (end1 >= n || begin2>=n)break;if (end2 >= n)end2 = n - 1;//合并,将arr中对应位置,放入tmp的对应位置int j = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])tmp[j++] = arr[begin1++];elsetmp[j++] = arr[begin2++];}while (begin1 <= end1){tmp[j++] = arr[begin1++];}while (begin2 <= end2){tmp[j++] = arr[begin2++];}//[begin1,end1],[begin2,end2]memcpy(arr + i, tmp + i, sizeof(int) * (end2-i+1));//每次归并完拷贝回去}gap *= 2;}free(tmp);tmp = NULL;
}

        4、实现效果

	int arr[] = { 1,6,41,32,5,12,7,11 };int size = sizeof(arr) / sizeof(int);printf("原数组\n");for (int i = 0; i < size; i++){printf("%d ", arr[i]);}printf("\n");printf("排序后\n");MergeSortNonR_incline(arr, size);for (int i = 0; i < size; i++){printf("%d ", arr[i]);}printf("\n");

原数组:1 6 41 32 5 12 7 11

排序后:1 5 6 7 11 12 32 41

相关文章:

排序算法8----归并排序(非递归)(C)

1、介绍 归并排序既可以是内排序&#xff08;在内存上的数据排序&#xff09;&#xff0c;也可以是外排序&#xff08;磁盘上&#xff09;&#xff08;硬盘&#xff09;&#xff08;在文件中的数据排序&#xff09;。 其他排序一般都是内排序。 区别于快速排序的非递归&#xf…...

Golang 里的 context

context 的作用 go 的编程中&#xff0c;常常会在一个 goroutine 中启动多个 goroutine&#xff0c;然后有可能在这些 goroutine 中又启动多个 goroutine。 如上图&#xff0c;在 main 函数中&#xff0c;启动了一个 goroutine A 和 goroutine B&#xff0c;然后 goroutine A …...

PHP短链接url还原成长链接

在开发过程中&#xff0c;碰到了需要校验用户回填的短链接是不是系统所需要的&#xff0c;于是就需要还原找出短链接所对应的长链接。 长链接转短链接 在百度上搜索程序员&#xff0c;跳转页面后的url就是一个长链接。当然你可以从任何地方复制一个长链接过来。 长链接 http…...

redis原理(三)redis命令

一、字符串命令&#xff1a; 1、字符串基本操作&#xff1a; 2、自增自减 &#xff1a;如果一个值可以被解释为十进制整数或者浮点数&#xff0c;redis允许用户对这个字符串进行INCR*、DECR*操作。 &#xff08;1&#xff09;INCR key&#xff1a;将键存储的值的值加1。 &a…...

教程:在Django中实现微信授权登录

教程&#xff1a;在Django中实现微信授权登录 本教程将引导您如何在Django项目中实现微信授权登录。在本教程中&#xff0c;我们将使用自定义的用户模型User&#xff0c;并通过微信提供的API来进行用户认证。 在进行以下教程之前&#xff0c;请确保你已经在微信开放平台添加了…...

YOLOv5改进 | 主干篇 | 12月份最新成果TransNeXt特征提取网络(全网首发)

一、本文介绍 本文给大家带来的改进机制是TransNeXt特征提取网络,其发表于2023年的12月份是一个最新最前沿的网络模型&#xff0c;将其应用在我们的特征提取网络来提取特征&#xff0c;同时本文给大家解决其自带的一个报错&#xff0c;通过结合聚合的像素聚焦注意力和卷积GLU&…...

【java八股文】之计算机网络系列篇

1、TCP/IP和UDP模型 TCP/IP分层&#xff08;4层&#xff09;&#xff1a;应用层&#xff0c;传输层&#xff0c;网络层&#xff0c;数据链路层 网络的七层架构 &#xff08;7层&#xff09;&#xff1a;应用层&#xff0c;表示层&#xff0c;会话层&#xff0c;传输层&#xff…...

SpringAMQP的使用

1. 简介&#xff1a; SpringAMQP是基于RabbitMQ封装的一套模板&#xff0c;并且还利用SpringBoot对其实现了自动装配&#xff0c;使用起来非常方便。 SpringAmqp的官方地址&#xff1a;https://spring.io/projects/spring-amqp SpringAMQP提供了三个功能&#xff1a; 自动声…...

MATLAB - 使用运动学 DH 参数构建机械臂

系列文章目录 前言 一、 使用 Puma560 机械手机器人的 Denavit-Hartenberg (DH) 参数&#xff0c;逐步建立刚体树形机器人模型。在连接每个关节时&#xff0c;指定其相对 DH 参数。可视化机器人坐标系&#xff0c;并与最终模型进行交互。 DH 参数定义了每个刚体通过关节与其父…...

2024年腾讯云新用户优惠云服务器价格多少?

腾讯云服务器租用价格表&#xff1a;轻量应用服务器2核2G3M价格62元一年、2核2G4M价格118元一年&#xff0c;540元三年、2核4G5M带宽218元一年&#xff0c;2核4G5M带宽756元三年、轻量4核8G12M服务器446元一年、646元15个月&#xff0c;云服务器CVM S5实例2核2G配置280.8元一年…...

如何在原型中实现继承和多态

在JavaScript中&#xff0c;我们可以通过原型链来实现继承。以下是如何在原型中实现继承的例子&#xff1a; // 定义一个动物原型 var Animal function() {}; Animal.prototype.move function() { console.log(‘This animal can move.’); }; // 定义一个狗的原型&#xf…...

MySQL/Oracle 的 字符串拼接

目录 MySQL、Oracle 的 字符串拼接1、MySQL 的字符串拼接1.1 CONCAT(str1,str2,...) : 可以拼接多个字符串1.2 CONCAT_WS(separator,str1,str2,...) : 指定分隔符拼接多个字符串1.3 GROUP_CONCAT(expr) : 聚合函数&#xff0c;用于将多行的值连接成一个字符串。 2、Oracle 的字…...

【Java SE语法篇】10.String类

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更新的动力❤️ 文章目录 前言1. String类1.1 字符串的构造1.2 String对象的比…...

【Python】数据可视化--基于TMDB_5000_Movie数据集

一、数据准备 tmdb_5000_movie数据集下载 二、数据预处理 观察数据集合情况 import pandas as pd import ast import warnings warnings.filterwarnings(ignore) # 加载数据集 df pd.read_csv(tmdb_5000_movies.csv) # 查看数据集信息 print(df.info()) 由于原数据集包含的…...

学习Vue的插槽总结

今天学习了Vue的插槽&#xff0c;在这之前学习使用组件的使用还没有试过在父组件中给子组件插入html结构&#xff0c;今天学习的插槽正是拿来实现这一功能的&#xff0c;这也是一种组件中通信的方式&#xff0c;首先插槽分为三类&#xff1a;默认插槽、具名插槽、作用域插槽。接…...

第九篇 API设计原则与最佳实践

深入浅出HTTP请求前后端交互系列专题 第一章 引言-HTTP协议基础概念和前后端分离架构请求交互概述 第二章 HTTP请求方法、状态码详解与缓存机制解析 第三章 前端发起HTTP请求 第四章 前后端数据交换格式详解 第五章 跨域资源共享&#xff08;CORS&#xff09;&#xff1a;现代W…...

新版AndroidStudio配置maven阿里云镜像

project下的build.gradle&#xff1a; // Top-level build file where you can add configuration options common to all sub-projects/modules. // 注意jdk版本需要17以上&#xff0c;因为8.1.3的gradle需要jdk17以上 //plugins { // id com.android.application version…...

【OSG案例详细分析与讲解】之十一:【多效果的3D动画】

目录 ​​​​​​​一、【多效果的3D动画】前言 二、【多效果的3D动画】实现效果...

一道使用LinkedList和Stack解决的算法题

一、无法吃午餐的学生数量 学校的自助午餐提供圆形和方形的三明治&#xff0c;分别用数字 0 和 1 表示。所有学生站在一个队列里&#xff0c;每个学生要么喜欢圆形的要么喜欢方形的。 餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里&#xff0c;每一轮&#…...

通用外设-W25Q64

前言 一、SPI通信 二、W25Q64基初时序 1.各种命令代码 2.代码 1.写使能指令 2.读取芯片是否忙碌状态并等待 3.写入数据 4.擦除函数操作 5.读取代码 三.验证 四.擦除说明 总结 前言 在单片机中一般32K FLASH就够用了&#xff0c;但是当我们使用图片或其他大量数据时…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...