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

【数据结构】排序--归并排序

目录

一 基本思想

二 代码实现 

三 非递归归并排序 


一 基本思想

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

二 代码实现 

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);//归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int index = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1)//如果[begin1, end1] 区间没有排完 接着排{tmp[index++] = a[begin1++];}while (begin2 <= end2)//如果[begin2, end2] 区间没有排完 接着排{tmp[index++] = a[begin2++];}memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));//拷贝回原数组
}void MergeSort(int* a, int n)
{int tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, tmp, 0, n-1);free(tmp);
}int main()
{int arr[] = { 10, 6, 7, 1, 3, 9, 4, 2 };MergeSort(arr, sizeof(arr) / sizeof(arr[0]));for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){printf("%d ", arr[i]);}return 0;
}

三 非递归归并排序 

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}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;if (begin2 >= n)//如果第二个区间 的begin2 已经超过了 就break 不用排这个区间了{break;}if (end2 >= n)//如果end2>= n 了 那就修正一下 最后一个数的下标就是n-1{end2 = n - 1;}int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}gap *= 2;}free(tmp);
}
int main()
{int arr[] = { 10, 6, 7, 1, 3, 9, 4, 2 };MergeSortNonR(arr, sizeof(arr) / sizeof(arr[0]));for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){printf("%d ", arr[i]);}return 0;
}

本节主要讲解了归并排序, 并且对递归和非递归版本进行了讲解,大家可以根据代码和图解进行理解, 归并排序并不难, 但是大家的二叉树的递归思想和基础必须要扎实(之前博客讲的有)

继续加油!

相关文章:

【数据结构】排序--归并排序

目录 一 基本思想 二 代码实现 三 非递归归并排序 一 基本思想 归并排序&#xff08;MERGE-SORT&#xff09;是建立在归并操作上的一种有效的排序算法,该算法是采用分治法&#xff08;Divide and Conquer&#xff09;的一个非常典型的应用。将已有序的子序列合并&#xff…...

批量修改视频尺寸:简单易用的视频剪辑软件教程

如果你需要批量修改视频尺寸&#xff0c;同时保持高质量的画质&#xff0c;那么“固乔剪辑助手”这款软件是你的不二之选。下面就是如何使用这款软件进行批量修改视频尺寸的详细步骤。 1. 首先&#xff0c;你需要在浏览器中进入“固乔科技”的官网&#xff0c;然后下载并安装“…...

四川云汇优想:短视频矩阵运营方案

短视频矩阵运营方案是为了提高短视频平台的用户黏性和活跃度&#xff0c;从而增强用户粘性和平台的商业价值而制定的。下面四川百幕晟小编将对短视频矩阵运营方案进行详细的介绍和分析。 首先&#xff0c;短视频矩阵运营方案要注重用户精细化运营。通过用户画像和兴趣标签&…...

vue中如何获取到当前位置的天气

要在Vue中获取当前位置的天气&#xff0c;您需要使用浏览器的Geolocation API来获取设备的地理位置&#xff0c;并使用第三方的天气API来获取天气数据。 下面是一般的步骤&#xff1a; 在Vue项目中安装axios库&#xff0c;用于发送HTTP请求。 npm install axios 创建一个新的…...

C++三角函数和反三角函数

当涉及到三角函数和反三角函数时&#xff0c;C提供了一组函数来执行这些计算。以下是C中常用的三角函数和反三角函数的详细解释和示例说明&#xff1a; sin函数&#xff08;正弦函数&#xff09;&#xff1a; 函数原型&#xff1a;double sin(double x);功能&#xff1a;计算给…...

Linux篇 五、Ubuntu与Linux板卡建立NFS服务

Linux系列文章目录 一、香橙派Zero2设置开机连接wifi 二、香橙派Zero2获取Linux SDK源码 三、香橙派Zero2搭建Qt环境 四、Linux修改用户名 文章目录 Linux系列文章目录前言一、连接到局域网互ping测试 二、安装NFS服务配置NFS更新exports配置三、板卡安装NFS客户端四、板卡临时…...

通讯协议学习之路:IrDA协议协议理论

通讯协议之路主要分为两部分&#xff0c;第一部分从理论上面讲解各类协议的通讯原理以及通讯格式&#xff0c;第二部分从具体运用上讲解各类通讯协议的具体应用方法。 后续文章会同时发表在个人博客(jason1016.club)、CSDN&#xff1b;视频会发布在bilibili(UID:399951374) 序、…...

互联网摸鱼日报(2023-10-20)

互联网摸鱼日报(2023-10-20) 博客园新闻 OPPO让折叠机超越直板旗舰成为可能 特斯拉的“大空头”&#xff0c;是马斯克那张嘴 逃避内卷的年轻人&#xff0c;盯上了老年大学的音乐课 理想市值超蔚来1倍&#xff0c;一场属于增程式的胜利 补足折叠屏影像短板&#xff0c;OPPO…...

C/C++ 快速入门

参考&#xff1a;https://blog.csdn.net/gao_zhennan/article/details/128769439 1 下载Visual Studio Code并安装中文插件&#xff0c;此处不再叙述 2 插件安装C/C插件 3 使用快捷键【Ctr ~】打打开终端 验证并未安装编译器 4 我们即将使用【MinGW-64】做为编译器 https:…...

【Git】升级MacOS系统,git命令无法使用

终端执行git命令报错 xcrun: error: invalid active developer path (/Library/Developer/CommandLineTools), missing xcrun at: /Library/Developer/CommandLineTools/usr/bin/xcrun安装这个东东&#xff0c;&#xff1f;需要42小时 最终解决&#xff1a; 下载安装 https…...

单点登录是什么?

单点登录&#xff08;Single Sign On, SSO&#xff09;是指在同一帐号平台下的多个应用系统中&#xff0c;用户只需登录一次&#xff0c;即可访问所有相互信任的应用系统。 单点登录的本质就是在多个应用系统中共享登录状态。如果用户的登录状态是记录在 Session 中的&#xff…...

面向对象设计原则之依赖倒置原则

目录 定义原始定义进一步的理解 作用实现方法代码示例 面向对象设计原则之开-闭原则 面向对象设计原则之里式替换原则 面向对象设计原则之依赖倒置原则 面向对象设计原则之单一职责原则 定义 依赖倒置原则&#xff08;Dependence Inversion Principle&#xff09;&#xff0c…...

MATLAB——概率神经网络分类问题程序

欢迎关注“电击小子程高兴的MATLAB小屋” %% 概率神经网络 %% 解决分类问题 clear all; close all; P[1:8]; Tc[2 3 1 2 3 2 1 1]; Tind2vec(Tc) %数据类型的转换 netnewpnn(P,T); Ysim(net,P); Ycvec2ind(Y) %转换回来...

微信小程序的OA会议之首页搭建

目录 一.小程序的布局 1.1. flex是什么 1.2. flex布局 1.3.总体布局 二.轮播图 2.1. 组件 2.2. 数据请求 2.3. 页面 三.首页 2.1. 视图 2.2.数据 2.3. 样式 好啦今天就到这里了&#xff0c;希望能帮到你哦&#xff01;&#xff01;&#xff01; 一.小程序的布局 …...

JS初步了解环境对象this

什么是环境对象&#xff1f; 环境对象&#xff1a;指的是函数内部特殊的变量this&#xff0c;它代表着当前函数运行时所处的环境 作用&#xff1a;弄清楚this的指向&#xff0c;可以让我们代码更简洁 在普通函数中&#xff1a; // 每个函数里面都有this 普通函数的this指向wind…...

Unbuntu-18-network-issue

第六步&#xff1a;容器管理 查看zfs储存卷的占用情况zpool list 为容器修改参数配置 我们不想每个人使用全部的硬件资源&#xff0c;所以还需要限制每个人的参数容器参数配置说明配置容器参数lxc config edit YourContainerName 配置默认容器参数&#xff08;新容器的参数会…...

Vue、React和小程序中的组件通信:父传子和子传父的应用

序言&#xff1a; 组件化开发是将一个大型应用程序拆分成独立的、可重用的、可组合的模块&#xff0c;使得开发人员可以快速构建和开发应用程序。组件化开发提倡将应用程序的各个功能模块分离开发&#xff0c;每个模块完成自己的功能并且可以在不同的应用程序中被复用。这可以…...

leetcode_171Excel表列序号

1. 题意 把excel中列序号字符串转换为10进制数。 Excel表列序号 2. 题解 26进制转10进制 class Solution { public:int titleToNumber(string columnTitle) {int sz columnTitle.size();int ans 0;int base 1;for ( int i sz - 1; ~i; --i){int v columnTitle[i] - A …...

北斗GPS卫星时钟同步服务器在银行数据机房应用

北斗GPS卫星时钟同步服务器在银行数据机房应用 北斗GPS卫星时钟同步服务器在银行数据机房应用 有些银行、政务、公安等重要业务单位&#xff0c;机房是采用屏蔽保密机房&#xff0c;这种情况下的时钟同步装置方案和普通机房的时钟同步方案又是不一样的。下面我们重点介绍保密机…...

Mysql数据库 1. SQL基础语法和操作

一、Mysql逻辑结构 一个数据库软件可以包含许多数据库 一个数据库包含许多表 一个表中包含许多字段&#xff08;列&#xff09; 数据库软件——>数据库——>数据表——>字段&#xff08;列&#xff09;、元组&#xff08;行&#xff09; 二、SQL语言基础语法 1.SQL…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...