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

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...