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

[数据结构]排序之归并排序（有详细的递归图解）

news 来源：原创 2025/8/7 9:06:43

一、非递归

基本思想：

归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤：

归并：如果左区间和右区间都有序，那么一次比较，小的尾插到新空间，链表可以摘下来插入，数组不行，得借助新空间

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
void _MergeSort(int* a, int begin, int end, int* temp)
{if (begin>=end)return;int mid = (begin + end) / 2;//[begin,mid] [mid+1,end]如果这两个区间有序，那么可以归并了_MergeSort(a, begin, mid, temp);_MergeSort(a, mid+1, end, temp);//[begin, mid] [mid + 1, end]归并int begin1 = begin, end1 = mid;int begin2 = mid+1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){temp[i] = a[begin1];i++;begin1++;}else{temp[i] = a[begin2];i++;begin2++;}}//谁没结束谁++来拷贝，由于不知道是哪个区间没有结束，所有都写一遍while (begin1 <= end1){temp[i] = a[begin1];i++;begin1++;}while (begin2 <= end2){temp[i] = a[begin2];i++;begin2++;}//等把所有数都放到temp数组上时，再拷贝回去memcpy(a+begin, temp+begin,sizeof(int)*(end-begin+1));
}
void MergeSort(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail\n");return;}_MergeSort(a, 0, n - 1, temp);free(temp);
}
int main()
{int a[] = {10,6,7,1,3,9,4,2 };MergeSort(a,8);for (int i = 0; i < 8; i++){printf("%d ", a[i]);}return 0;
}

注：以下图片看不清楚可以点进去放大看

二、递归

不能用栈，栈是前序，而归并是后序

方法：

能不能依次依次往后算？算完第一个和第二个后算第三个和第四个，再算第五个和第六个.......

第一次归完后再拷贝回去后四个四个一归.....

必须得注意细节：如果是奇数个数那么得注意边界

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
void _MergeSort(int* a, int begin, int end, int* temp)
{if (begin >= end)return;int mid = (begin + end) / 2;//[begin,mid] [mid+1,end]如果这两个区间有序，那么可以归并了_MergeSort(a, begin, mid, temp);_MergeSort(a, mid + 1, end, temp);//[begin, mid] [mid + 1, end]归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){temp[i] = a[begin1];i++;begin1++;}else{temp[i] = a[begin2];i++;begin2++;}}//谁没结束谁++来拷贝，由于不知道是哪个区间没有结束，所有都写一遍while (begin1 <= end1){temp[i] = a[begin1];i++;begin1++;}while (begin2 <= end2){temp[i] = a[begin2];i++;begin2++;}//等把所有数都放到temp数组上时，再拷贝回去memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail\n");return;}int gap = 1;while (gap < n){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;int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){temp[j] = a[begin1];j++;begin1++;}else{temp[j] = a[begin2];j++;begin2++;}}//谁没结束谁++来拷贝，由于不知道是哪个区间没有结束，所有都写一遍while (begin1 <= end1){temp[j] = a[begin1];j++;begin1++;}while (begin2 <= end2){temp[j] = a[begin2];j++;begin2++;}//等把所有数都放到temp数组上时，再拷贝回去memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));}gap *= 2;}free(temp);
}
int main()
{int a[] = {10,6,7,1,3,9,4,2 };MergeSort(a,8);for (int i = 0; i < 8; i++){printf("%d ", a[i]);}return 0;
}

[数据结构]排序之归并排序（有详细的递归图解）

一、非递归基本思想： 归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列&#x…...

编程日记 2025/8/7 9:06:43

pdf文件分页按需查看

pdf预览本来打算粗暴点，一次性查看全部，但是一个pdf四五百页导致手机端查看超出内存直接崩掉，崩掉会导致页面疯狂刷新，所以不得不进行优化解决思路大致如下： canvas转为blob格式以图片的形式加载在页面（B…...

编程日记 2025/8/7 9:02:47

栈/堆/static/虚表

在 C 里，栈空间主要用来存放局部变量、函数调用信息等。下面为你介绍栈空间在 C 里的运用方式。 1. 局部变量的使用在函数内部定义的变量会被存于栈空间，当函数执行结束，这些变量会自动被销毁。 #include <iostream>void exampleFu…...

编程日记 2025/8/7 8:58:44

计算机网络技术服务管理基于Spring Boot-SSM

目录一、引言二、用户需求分析三、功能介绍 ‌‌3.1.资源管理‌： ‌3.2.故障管理‌： ‌3.3.性能管理‌： ‌3.4.安全管理‌： ‌3.5.配置管理‌： ‌3.6.日志管理‌： ‌3.7.用户管理‌&#xff1…...

编程日记 2025/8/7 9:00:50

Redisson 分布式锁原理

加锁原理 # 如果锁不存在 if (redis.call(exists, KEYS[1]) 0) then# hash结构,锁名称为key,线程唯一标识为itemKey，itemValue为一个计数器。支持相同客户端线程可重入,每次加锁计数器1.redis.call(hincrby, KEYS[1], ARGV[2], 1);# 设置过期时间redis.call(pexpi…...

编程日记 2025/8/7 9:04:47

LLM(5)：了解 GPT 架构

1.6 对 GPT 架构的更深入了解 GPT 最初由 OpenAI 的 Radford 等人在论文《通过生成式预训练提高语言理解能力》中提出。GPT-3 是该模型的扩展版本，具有更多的参数，并且使用了更大的数据集进行训练。此外，ChatGPT 中提供的原始模型是通过在大…...

编程日记 2025/8/6 9:12:40

Android Zygote 启动流程梳理

和你一起终身学习，这里是程序员Android 本篇文章主要介绍 Android Zygote 启动分析知识点，通过阅读本篇文章，您将收获以下内容: 一、Android 系统基本服务二、虚拟机创建和第一个Java 程序引导三、Dalvik 虚拟机基本配置四、Zygote 启动流程…...

编程日记 2025/7/27 1:47:49

华为OD机试-绘图机器-双指针（Java 2025 A卷 100分）

题目描述绘图机器的绘图笔初始位置在原点 (0, 0)。机器启动后按照以下规则绘制直线：尝试沿着横坐标正向绘制直线，直到给定的终点 E。期间可以通过指令在纵坐标轴方向进行偏移，offsetY 为正数表示正向偏移，为负数表示负向偏移。给定的横坐标终点值 E 以及若干条绘制指令，…...

编程日记 2025/8/5 7:08:02

ESP32（1）基于ESP32的lwIP了解

ESP32-S3 是一款集成了 Wi-Fi 和蓝牙功能的微控制器，而 lwIP（轻量级 IP）是一个为嵌入式系统设计的开源 TCP/IP 协议栈。通过使用 lwIP 库， ESP32-S3 可以实现与外部网络的通信，包括发送和接收数据包、处理网络连接等。…...

编程日记 2025/8/7 9:03:45

C语言预处理详解

目录 （一）预处理符号 （二）define定义常量和宏 （三）#符号和##符号 （四）undef符号的条件编译 （五）头文件的包括 （一）预处理符号在…...

编程日记 2025/7/31 7:59:00

python实现接口自动化

代码实现自动化相关理论代码编写脚本和工具实现脚本区别是啥? 代码： 优点：代码灵活方便缺点：学习成本高工具： 优点：易上手缺点：灵活度低，有局限性。总结： 功能脚本：工…...

编程日记 2025/8/7 9:06:02

当Anaconda的安装路径与我想创建的conda虚拟环境路径不一致时，应该怎么操作？

我的anaconda安装在该路径：D:\Program\anaconda3 , 如果我想在F盘创建一个虚拟环境应该怎么做呢？ 若你想在 F 盘创建 Anaconda 虚拟环境，可使用 conda create 命令，并通过 --prefix 参数指定环境路径。以下是详细步骤&#xff1…...

编程日记 2025/8/5 5:09:55

MongoDB慢日志查询及索引创建

MongoDB 的慢日志（Slow Query Log）对于运维和程序员来说都非常重要，因为它直接关系到数据库的性能和应用程序的稳定性。以下分享介绍下MongoDB慢日志查询及索引创建相关的一些笔记。一，准备 1. 使用 db.currentOp() 实时监控 …...

编程日记 2025/7/31 4:24:24

C语言指针（详细总结）

目录 1.初始C指针几个重要的概念： 指针的加减 &与* 二级指针 2.指针与数组指针数组数组指针变量一维数组与二维数组传参的本质编辑编辑编辑 3.指针与函数函数指针数组 4.指针与结构体 5.野指针以及常见的内存管理错误常见的内存错…...

编程日记 2025/8/7 9:02:11

服务器部署Kong和Konga过程

前言最近在想怎么将一个接口给外部提供服务，并且可以根据和对放的关系，设置不同的期限或者服务大小？并且有友好的可视化页面！这让我了解到了 API 网关，所以我开始研究 Kong 和 Konga 的使用。实际上我最开始研究的apisix，但是部署了好久因为etcd不支持 http 无法连接…...

编程日记 2025/8/7 9:04:48

stm32第五天按键的基础知识

一：按键连接示意图按键控制LED灯软件设计流程初始化系统 o 初始化GPIO外设时钟 o 初始化按键和LED的引脚 • 检测按键输入电平来控制LED灯 o SW2控制灯开。 SW3控制灯关 1：key.c工程 #include"key.h" #include"stm32f10x.h"v…...

编程日记 2025/8/7 9:00:48

高主频CPU+RTX4090：AI生图性能优化超150%

概述：消费级高主频CPU搭配 RTX 4090显卡可以显著提高AI生图的性能，相比于企业级CPU具有更大的吞吐量和更优的成本效益。引言：在AI图像生成过程中，CPU与GPU的协同效应对系统的整体性能至关重要。测试表明，与RTX 4090显…...

编程日记 2025/8/4 22:55:53

自学Python创建强大AI：从入门到实现DeepSeek级别的AI

人工智能（AI）是当今科技领域最热门的方向之一，而Python是AI开发的首选语言。无论是机器学习、深度学习还是自然语言处理，Python都提供了丰富的库和工具。如果你梦想创建一个像DeepSeek这样强大的AI系统，本文将为你提供…...

编程日记 2025/7/30 8:19:47

主流区块链

文章目录主流链1. Solana特点：适用场景：工具链： 2. Binance Smart Chain (BSC)特点：适用场景：工具链： 3. Avalanche特点：适用场景：工具链： 4. Polkadot特点：…...

编程日记 2025/8/4 8:05:47

DevEco Studio的使用

目录 1.创建ArkTS工程 2.ArkTS工程目录结构（Stage模型） 构建第一个页面构建第二个页面实现页面间的跳转 1.创建ArkTS工程若首次打开DevEco Studio，请点击Create Project创建工程。如果已经打开了一个工程，请在菜单栏选择…...

编程日记 2025/7/31 21:37:00

Oracle 公布 Java 的五大新功能

Java 增强提案包括语言增强和性能优化，从 JDK 25 中的稳定值 API 开始。随着JDK（Java 开发工具包）24刚刚全面上市，Oracle 提前透露了不久的将来即将推出的 Java 功能，包括增强原始装箱到空限制值类类型。 3 月 18 日…...

编程日记 2025/8/6 9:15:18

checkpoint机制

1、什么是checkpoint 将缓冲池中的脏页刷新到磁盘，并更新redo log的checkpoint位点，确保数据库在发生故障时可以快速恢复到一致的状态。 2、checkpoint执行过程确保需要刷新的脏页：从缓冲池中选取一部分需要刷新的页数据页刷新&#xff1…...

编程日记 2025/8/6 8:27:50

MySQL函数大全（持续更新）

MySQL常用函数一、字符串函数函数功能 CONCAT(s1, s2, ...) 拼接字符串 CONCAT_WS(sep, s1, s2, ...) 指定分隔符拼接字符串 SUBSTRING(str, start, length) 截取字符串 LEFT(str, length) 从左边截取指定长度字符串 RIGHT(str, length) 从右边截取指定长度字符串 LENGTH(s…...

编程日记 2025/8/7 6:30:14

商业智能BI分析中，汽车4S销售行业的返厂频次有什么分析价值？

买过车的朋友会发现，同一款车不管在哪个4S店去买，基本上价格都相差不大。即使有些差别，也是带着附加条件的，比如要做些加装需要额外再付一下费用。为什么汽车4S销售行业需要商业智能BI？就是因为在汽车4S销售行业&#…...

编程日记 2025/8/5 17:35:29

51单片机程序变量作用域问题

问题： //为什么下面这个程序可以运行 #include <REGX52.H> #include "LCD1602.h" #include "Delay.h" unsigned int result 0; void main(){LCD_Init();while(1){LCD_ShowNum(1,1,result,3);Delay(200);result;}; } //但是这样会报错&a…...

编程日记 2025/8/3 17:16:56

力扣算法ing(33 / 100)

3.20 146.LRU缓存请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类： LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值&…...

编程日记 2025/8/2 16:08:05

基于springboot的母婴商城系统（018）

摘要现代经济快节奏发展以及不断完善升级的信息化技术，让传统数据信息的管理升级为软件存储，归纳，集中处理数据信息的管理方式。本母婴商城系统就是在这样的大环境下诞生，其可以帮助管理者在短时间内处理完毕庞大的数据信息&am…...

编程日记 2025/8/5 19:39:02

【数学建模】模糊综合评价模型详解、模糊集合论简介

模糊综合评价模型详解文章目录模糊综合评价模型详解1. 模糊综合评价模型概述2. 模糊综合评价的基本原理2.1 基本概念2.2 评价步骤 3. 模糊综合评价的数学模型3.1 数学表达3.2 模糊合成运算 4. 模糊综合评价的应用领域5. 模糊综合评价的优缺点5.1 优点5.2 缺点 6. 模糊综合评价…...

编程日记 2025/8/4 19:52:42

BSCAN2-1：load design

1. DFT Flow Using Tessent Shell Tessent BoundaryScan 具有一个基本的高层次流程顺序。下图展示了将 Tessent BoundaryScan 插入设计所需的高层次步骤顺序。图中的每个步骤都链接到有关可测试性设计（DFT）流程的更详细信息，包括示例。 Desi…...

编程日记 2025/8/2 16:17:58

Pytorch中layernorm实现详解

平时我们在编写神经网络时，经常会用到layernorm这个函数来加快网络的收敛速度。那layernorm到底在哪个维度上进行归一化的呢？ 一、问题描述首先借用知乎上的一张图，原文写的也非常好，大家有空可以去阅读一下，链接放…...

编程日记 2025/8/6 6:05:56

Redis HyperLogLog

Redis HyperLogLog HyperLogLog 是 Redis 提供的一种基数估算（Cardinality Estimation）数据结构，专门用于统计去重元素的数量（近似值）。 1. HyperLogLog 特点 ✅ 节省内存：无论存储的元素有 10 个还是 …...

编程日记 2025/8/4 16:48:11

【微服务日志收集①】使用FileBeat+Logstash+ES搭建ELK日志系统

使用FileBeatLogstashES搭建ELK日志系统，架构图如下： 1、使用docker快速创建ES服务和Kibana服务前置条件：需要在linux上提前安装好docker和docker-compose 1.1、在linux创建好一个用于存放docker-compose配置文件的文件夹我的目录是/app/…...

编程日记 2025/8/5 1:37:25

【FAQ】HarmonyOS SDK 闭源开放能力 —Push Kit（10）

1.问题描述： 离线推送，锁屏的时候没有弹出消息，只有下拉在通知中心里面显示。请问是否是正常的？ 解决方案： 检查一下是否存在图片风控：https://developer.huawei.com/consumer/cn/doc/harmonyos-referen…...

编程日记 2025/8/4 22:07:19

1、确保app已配置完(settings.py文件里面配置） INSTALLED_APPS [django.contrib.admin,django.contrib.auth,django.contrib.contenttypes,django.contrib.sessions,django.contrib.messages,django.contrib.staticfiles,app.apps.AppConfig #配置已经注册好的app…...

编程日记 2025/8/3 5:23:16

Redis Sentinel（哨兵模式）高可用性解决方案

一、概述 Redis Sentinel（哨兵模式）是Redis的高可用性（High Availability, HA）解决方案，它通过哨兵系统和Redis实例的协同工作，确保了Redis服务的高可用性和数据的持久性。哨兵系统由一个或多个哨兵进程组…...

编程日记 2025/8/6 20:44:52

Redis缓存与数据库数据一致性保障

为什么要保证数据一致性只要使用redis做缓存，就必然存在缓存和DB数据一致性问题。若数据不一致，则业务应用从缓存读取的数据就不是最新数据，可能导致严重错误。比如将商品的库存缓存在Redis，若库存数量不对，则下单时…...

编程日记 2025/8/6 23:36:15

Grid 布局实现三栏布局

使用 CSS Grid 布局实现三栏布局（左右固定 100px，中间自适应）的核心原理是通过网格模板精确控制列宽分配。以下是具体实现方法及优化技巧：一、基础实现父容器设置为外层容器添加 display: grid 使其成为网格容器，并通过 grid-template-columns 定义列宽 css .contain…...

编程日记 2025/8/4 10:36:17

如何在 HTML 中创建一个有序列表和无序列表，它们的语义有何不同？

大白话如何在 HTML 中创建一个有序列表和无序列表，它们的语义有何不同？ 1. HTML 中有序列表和无序列表的基本概念在 HTML 里，列表是一种用来组织信息的方式。有序列表就是带有编号的列表，它可以让内容按照一定的顺序呈现&#…...

编程日记 2025/6/28 2:31:13

springboot第三站（1） web开发引入

目录 1.简介 2.SpringBoot对静态资源的映射规则 3.模版引擎 1.简介使用SpringBoot； 1）、创建SpringBoot应用，选中我们需要的模块； 2）、SpringBoot已经默认将这些场景配置好了，只需要在配置文件中指定…...

编程日记 2025/8/5 4:42:09

nginx 简单实践：负载均衡【nginx 实践系列之四】

〇、前言本文为 nginx 简单实践系列文章之三，主要简单实践了负载均衡，仅供参考。注意：可以使用测试域名，但前提是要修改 hosts 文件路径和重启：Linux（/etc/hosts）（重启命令&#…...

编程日记 2025/8/3 23:41:05

CentOS 7.9 安装 Python 3.10 详细步骤及常见问题解决

一、环境准备与依赖安装更新系统与开发工具 sudo yum update -y sudo yum groupinstall "Development Tools" -y sudo yum install -y zlib-devel bzip2-devel openssl-devel ncurses-devel sqlite-devel \ readline-devel tk-devel libffi-devel gdbm-devel db4-de…...

编程日记 2025/8/6 7:55:47

计算机网络-1-1计算机网络体系结构

第一章计算机网络体系结构绪论《计算机网络》学什么？——数据如何通过网络正确、可靠地从A传送到B 【考纲内容】 (一)计算机网络概述计算机网络的概念、组成与功能；计算机网络的分类； 计算机网络的性能指标 (二)计算机网…...

编程日记 2025/8/3 0:01:35

集装箱箱号OCR识别技术，在铁路物流场站集装箱装卸机械数字化系统中的应用

集装箱装卸机械数字化是针对铁路物流场站的门式起重机、集装箱正面吊运起重机、重型叉车、堆高机等作业设备，在不影响原设备作业性能情况下，通过增加或集成集装箱箱号OCR识别或者车号识别装置、北斗定位装置、PLC采集装置等，利用多种通信协议…...

编程日记 2025/8/4 23:30:36

数仓工具—Hive语法之不同纬度聚合

不同纬度聚合提到不同纬度聚合，大家想到的肯定是grouping sets，或者是cube和rollup 其实这些我们之前都讲过，可以看看之前的文章数仓工具—Hive语法之cube和rollup 数仓工具—Hive语法之grouping sets 但是我们今天遇到的问题是，使用的工具不支持grouping sets，既然…...

编程日记 2025/8/4 22:29:46

GitHub在push推送到远程仓库的时候显示Logon failed登录失败

具体问题描述 git.exe push --progress "origin" master:master Logon failed, use ctrlc to cancel basic credential prompt. remote: Support for password authentication was removed on August 13, 2021. 这是因为Git 推送失败的原因是 GitHub 已经不支持密码认…...

编程日记 2025/8/5 19:44:43

【Dive Into Stable Diffusion v3.5】1：开源项目正式发布——深入探索SDv3.5模型全参/LoRA/RLHF训练

目录 1 引言2 项目简介3 快速上手3.1 下载代码3.2 环境配置3.3 项目结构3.4 下载模型与数据集3.5 运行指令3.6 核心参数说明3.6.1 通用参数3.6.2 优化器/学习率3.6.3 数据相关 4 结语 1 引言在人工智能和机器学习领域，生成模型的应用越来越广泛。Stable Diffusion…...

编程日记 2025/8/5 23:01:27

2025-03-19 Unity 网络基础2——网络通信基础

文章目录 1 数据通信模型1.1 C/S 模型1.2 B/S 模型1.3 P2P 模型1.4 小结 2 网络协议2.1 OSI 模型2.1.1 下层2.1.2 上层 2.2 TCP/IP 协议2.2.1 TCP 协议2.2.2 UDP 协议 3 网络游戏通信方案3.1 强/弱弱联网游戏3.2 长/短连接游戏3.3 相关术语 1 数据通信模型在早期的计算机网…...

编程日记 2025/8/5 4:52:11

路由器安全研究：D-Link DIR-823G v1.02 B05 复现与利用思路

前言 D-Link DIR-823G v1.02 B05存在命令注入漏洞，攻击者可以通过POST的方式往 /HNAP1发送精心构造的请求，执行任意的操作系统命令。漏洞分析 binwalk提取固件，成功获取到固件。现在我们已经进入到应用里了，那么我们在进行分析…...

编程日记 2025/8/1 1:37:55

【蓝桥杯python研究生组备赛】005 数学与简单DP

题目1 01背包有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数&a…...

编程日记 2025/8/6 8:23:11

数据仓库是什么，跟数据集成有什么关系

在当今数字化时代，数据已成为企业决策的重要依据。数据仓库作为企业数据管理的核心组件，其重要性不言而喻。那么，数据仓库到底是什么？它与数据集成又有着怎样的关系呢？本文将深入探讨这些问题。一、数据仓库&#xf…...

编程日记 2025/8/4 17:36:30

一、非递归

二、递归

相关文章：