【排序】归并排序(C语言实现)
文章目录
- 1. 递归版的归并排序
- 1.1 归并排序的思想
- 2. 递归版的归并排序的实现
- 2. 非递归版的归并排序
1. 递归版的归并排序
1.1 归并排序的思想
归并排序(MERGE - SORT)是建立在归并操作上的一种有效的排序算法, 该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:


这里我们先介绍一下递归版本的归并排序的思想:
- 我们需要先创建一个临时数组,用来将需要排序的数组归并到这个临时数组里面去,然后再将这个数组拷贝到原数组中去,这样就完成了排序的过程。
2. 递归版的归并排序的实现
具体实现方式如下:
void Sub_MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end - 1) // 我控制的是左闭右开区间return;int key = (begin + end) / 2;// [left,key + 1) [key,end) 左闭右开的空间一定要控制好int begin1 = begin, end1 = key;int begin2 = key, end2 = end;Sub_MergeSort(a, tmp, begin1, end1);Sub_MergeSort(a, tmp, begin2, end2);// 归并过程int indix = begin;while (begin1 < end1 && begin2 < end2){if (a[begin1] <= a[begin2]){tmp[indix++] = a[begin1++];}else{tmp[indix++] = a[begin2++];}}while (begin1 < end1){tmp[indix++] = a[begin1++];}while (begin2 < end2){tmp[indix++] = a[begin2++];}// 将tmp数组中的元素拷贝到元素中memmove(a + begin, tmp + begin, (end - begin)*sizeof(int));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}// 因为这里开一次空间就够用了,所以递归过程我们还是要写成一个子函数来完成Sub_MergeSort(a, tmp, 0, n);free(tmp);tmp = NULL;
}
2. 非递归版的归并排序
所以在平时我们要使用归并排序时,使用递归版的完全够用了。但由于现在还在学习阶段,所以掌握一下非递归版的归并排序还是有必要的。
把递归改成非递归,这个怎么处理呢?可以像我们之前讲的快速排序的非递归一样使用栈吗?
这里实现非递归的归并排序使用栈其实不是很好的方式,反而会使问题变复杂。

所以我们就得想其他办法:
可以这样:

但是这里需要注意两种情况:

这里不控制好边界的话,很容易就造成越界了,这里我分享两种控制边界的方式,细节我写在注释里了:
方式一:
// 归并排序 -- 非递归
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}int gap = 1;while (gap < n){for (int i = 0;i < n;i = 2 * gap + i){int begin1 = i, end1 = i + gap - 1; // 定义每次归并时的第一组数据int begin2 = i + gap, end2 = i + 2 * gap - 1; // 定义每次归并时的第二组数据if (begin2 >= n) // 如果第二组不存在了,这一趟就不用归并了{break;}if (end2 >= n) // 如果存在第二组,但第二组的末尾越界了,应该调整一下{end2 = n - 1;}// 归并过程int indix = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[indix++] = a[begin1++];}else{tmp[indix++] = a[begin2++];}}while (begin1 <= end1){tmp[indix++] = a[begin1++];}while (begin2 <= end2){tmp[indix++] = a[begin2++];}// 将tmp数组拷贝回原数组memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}gap *= 2;}free(tmp);tmp = NULL;
}
方式二:
void MergeSortNonR2(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}int gap = 1;while (gap < n){int j = 0;for (int i = 0;i < n;i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// end1 >= n - 1 和begin2 >= n 都代表没有第二组,所以第二组就不用参与归并过程if (end1 >= n){end1 = n - 1;// 此时begin2和end2一定是越界的// 我们手动让这段空间不存在begin2 = n;end2 = n - 1;}else if (begin2 >= n){// 我们手动让这段空间不存在begin2 = n;end2 = n - 1;}else if (end2 >= n) // 此时end1 和 begin2都没有越界{end2 = n - 1;}// 归并过程while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}}memcpy(a, tmp, sizeof(int) * n);gap *= 2;}free(tmp);tmp = NULL;
}
相关文章:
【排序】归并排序(C语言实现)
文章目录 1. 递归版的归并排序1.1 归并排序的思想2. 递归版的归并排序的实现 2. 非递归版的归并排序 1. 递归版的归并排序 1.1 归并排序的思想 归并排序(MERGE - SORT)是建立在归并操作上的一种有效的排序算法, 该算法是采用分治法(Divide a…...
127. 单词接龙
和433.最小基因变化这道题一样的解法。 https://blog.csdn.net/qq_43606119/article/details/135538247 class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Set<String> cnt new HashSet<>();for (int …...
计算机算法贪心算法
贪心算法(Greedy Algorithm)是一种常见的算法思想,它在每一步选择当前状态下最优的解决方案,从而希望最终能够达到全局最优解。 贪心算法的基本思路是每一步都选择当前状态下的局部最优解,而忽略了当前选择所带来的影…...
基于css实现动画效果
介绍 本文将会基于css,实现各种动画效果,接下来会从简单几个例子入手。 案例 三颗球 <!DOCTYPE html> <html lang"en"><head><meta charset"utf-8" /><title>React App</title><style>…...
18.将文件上传至云服务器 + 优化网站的性能
目录 1.将文件上传至云服务器 1.1 处理上传头像逻辑 1.1.1 客户端上传 1.1.2 服务器直传 2.优化网站的性能 2.1 本地缓存优化查询方法 2.2 压力测试 1.将文件上传至云服务器 客户端上传:客户端将数据提交给云服务器,并等待其响应;用户…...
Linux: module: kheaders;CONFIG_IKHEADERS
文章目录 参考错误开一个玩笑。configcommit参考 https://github.com/iovisor/bcc/pull/2312 https://github.com/iovisor/bcc/pull/3588 https://bugs.gentoo.org/809347 https://lore.kernel.org/lkml/20190408212855.233198-1-joel@joelfernandes.org/ 错误 <built-in…...
Page 251~254 Win32 GUI项目
win32_gui 源代码: #if defined(UNICODE) && !defined(_UNICODE)#define _UNICODE #elif defined(_UNICODE) && !defined(UNICODE)#define UNICODE #endif#include <tchar.h> #include <windows.h>/* Declare Windows procedure */…...
Kafka(七)可靠性
目录 1 可靠的数据传递1.1 Kafka的可靠性保证1.2 复制1.3 Broker配置1.3.1 复制系数1.3.2 broker的位置分布1.3.3 不彻底的首领选举1.3.4 最少同步副本1.3.5 保持副本同步1.3.6 持久化到磁盘flush.messages9223372036854775807flush.ms9223372036854775807 1.2 在可靠的系统中使…...
Spring Data JPA入门到放弃
参考文档:SpringData JPA:一文带你搞懂 - 知乎 (zhihu.com) 一、 前言 1.1 概述 Java持久化技术是Java开发中的重要组成部分,它主要用于将对象数据持久化到数据库中,以及从数据库中查询和恢复对象数据。在Java持久化技术领域&a…...
MES系统数据采集的几种方式
生产制造执行MES系统具有能够帮助企业实现生产数据收集与分析、生产计划管理、生产过程监控等的功能板块,在这里小编就不一一介绍了,主要讲讲它的数据采集功能板块,可以说,数据采集是该系统进行数据统计与生产管理等后续工作的基础…...
铭文 LaunchPad 平台 Solmash 推出早鸟激励计划
为感谢用户对Solmash的支持,Solmash 特别推出“Solmash早鸟激励计划”,以回馈社区的早期参与者,这是专为已经参与Staking Pool或Honest Pool的用户推出的激励。 Solmash NFT激励 被列入早鸟计划的用户,可通过点击:sol…...
【前端规范】
1 前言 HTML 作为描述网页结构的超文本标记语言,一直有着广泛的应用。本文档的目标是使 HTML 代码风格保持一致,容易被理解和被维护。 2 代码风格 2.1 缩进与换行 [强制] 使用 4 个空格做为一个缩进层级,不允许使用 2 个空格 或 tab 字符…...
12、JVM高频面试题
1、JVM的主要组成部分有哪些 JVM主要分为下面几部分 类加载器:负责将字节码文件加载到内存中 运行时数据区:用于保存java程序运行过程中需要用到的数据和相关信息 执行引擎:字节码文件并不能直接交给底层操作系统去执行,因此需要…...
【Docker】Docker安装入门教程及基本使用
🎉🎉欢迎来到我的CSDN主页!🎉🎉 🏅我是Java方文山,一个在CSDN分享笔记的博主。📚📚 🌟推荐给大家我的专栏《Docker实战》。🎯🎯 &…...
语义解析:如何基于SQL去实现自然语言与机器智能连接的桥梁
🌈个人主页: Aileen_0v0 🔥热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 💫个人格言:"没有罗马,那就自己创造罗马~" 目录 语义解析 定义 作用 语义解析的应用场景 场景一: 场景二: 总结语…...
Java项目:117SpringBoot动漫论坛网站
博主主页:Java旅途 简介:分享计算机知识、学习路线、系统源码及教程 文末获取源码 117SpringBoot动漫论坛网站 一、项目介绍 动漫论坛网站是由SpringBootMybatis开发的,旅游网站分为前台和后台,前台为用户浏览,后台进…...
Jenkins基础篇--添加节点
节点介绍 Jenkins 拥有分布式构建(在 Jenkins 的配置中叫做节点),分布式构建能够让同一套代码在不同的环境(如:Windows 和 Linux 系统)中编译、测试等。 Jenkins 运行的主机在逻辑上是 master 节点,下图是主节点和从节点的关系。 添加节点 …...
【C++】手撕 list类(包含迭代器)
目录 1,list的介绍及使用 2,list_node 3,list_node() 3,list 4,list() 5,push_back(const T& x) 6,print() 7,_list_iterator 8,operator*() 9,…...
@Autowired 和 @Resource 的区别是什么?
Java面试题目录 Autowired 和 Resource 的区别是什么? Autowired 是 Spring 提供的注解。默认的注入方式为byType(根据类型进行匹配)。 Resource 是 JDK 提供的注解。默认注入方式为 byName(根据名称进行匹配)。 当一…...
栈和排序.
给你一个1->n的排列和一个栈,入栈顺序给定 你要在不打乱入栈顺序的情况下,对数组进行从大到小排序 当无法完全排序时,请输出字典序最大的出栈序列 输入 第一行一个数n 第二行n个数,表示入栈的顺序,用空格隔开&…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
