【初阶数据结构】归并排序 - 分而治之的排序魔法

文章目录

  • 前言
  • 1. 什么是归并排序?
    • 1.1 归并排序的步骤
  • 2. 归并排序的代码实现
    • 2.1 归并排序代码的关键部分讲解
      • 2.1.1 利用递归
      • 2.1.2 将拆解的数组的元素放到一个临时空间中进行重新排序
      • 2.1.3 将在临时空间中排好的数组复制到目标数组中
  • 3. 归并排序的非递归写法

前言

本文讲解的排序算法是归并排序,作为归并算法,其有着快速排序算法没有的特性,也是面试比较常考的算法之一。本文会重点讲解思路以及代码的实现。

OK,让我们来一场酣畅淋漓的排序冒险吧!!!

哈哈哈

1. 什么是归并排序?

归并排序(MergeSort)是一种基于分治法的高效排序算法,具有稳定性和较好的时间复杂度。归并排序的基本思想是将待排序数组递归地分成两个子数组,分别对这两个子数组进行排序,然后再将它们合并成一个有序数组。

我给大家看一下归并排序的动图:
归并排序的动图

1.1 归并排序的步骤

  1. 🍉分解:将数组从中间分为两部分,递归地对子数组进行相同的操作,直到子数组的长度为1(即每个子数组只有一个元素,天然有序)。
  2. 🍉合并:将两个有序的子数组合并成一个有序数组。合并的过程通过比较两个子数组的元素大小,按序依次放入目标数组。
  3. 🍉重复上述步骤,直到所有子数组都合并成一个有序数组。

也许你看到上面的步骤有点云里雾里的感觉,没有关系,下面我将给出一个具体的例子,带着大家,去理解上面的步骤。

🍇例子:假设我们要对数组 [3, 1, 4, 1, 5, 9, 2, 6] 进行归并排序:

  1. 将数组不断分成两部分,直到每个部分只有一个元素:
    [3, 1, 4, 1, 5, 9, 2, 6]
    • 分成 [3, 1, 4, 1] 和 [5, 9, 2, 6]
    • 再分成 [3, 1] 和 [4, 1],以及 [5, 9] 和 [2, 6]
    • 继续分到每个部分只有一个元素:[3], [1], [4], [1], [5], [9], [2], [6]
  1. 合并有序子数组:
    • 将 [3] 和 [1] 合并为 [1, 3],将 [4] 和 [1] 合并为 [1, 4]
    • 将 [5] 和 [9] 合并为 [5, 9],将 [2] 和 [6] 合并为 [2, 6]
    • 将 [1, 3] 和 [1, 4] 合并为 [1, 1, 3, 4],将 [5, 9] 和 [2, 6] 合并为 [2, 5, 6, 9]
    • 最后将 [1, 1, 3, 4] 和 [2, 5, 6, 9] 合并为 [1, 1, 2, 3, 4, 5, 6, 9]
    • 最终得到有序数组 [1, 1, 2, 3, 4, 5, 6, 9]。

相信来看完上面的例子,你已经了解了归并排序的玩法了,那么接下来我们就得用代码来实现了。


2. 归并排序的代码实现

大家可以对照着这幅图来理解:

归并排序图片
可以看到归并排序的思想一定可以用递归来思想,接下来,我先给大家完整的代码,之后会对代码的关键部分讲解:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int i = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}if(a[begin1] >= a[begin2]){tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + left, tmp + left, sizeof(int)*(right-left+1));}//归并排序
void MergeSort(int* a, int n)
{int left = 0, right = n - 1;int* tmp = (int*)malloc(n * sizeof(int));if (tmp == NULL) {perror("malloc fail");return;}_MergeSort(a,left,right,tmp);	
}

这里我们采用的是用_MergeSort这个函数写归并排序的核心代码,这种写法的结构也是现在比较推崇的。

2.1 归并排序代码的关键部分讲解

为了让大家更好的吸收上述代码的思想,这里我将会详细的讲解代码关键部分的逻辑。
归并排序图片

2.1.1 利用递归

递归
我们直到归并排序是采用分治思想的,其原理就是将一个数组拆解成一个一个有序的区间,最后经过比较合并之后才会称为一个有序的数组。那么,我们该如何,将数组拆成一个个区间呢?

利用递归就可以实现。有的人可能会问了,为什么会使用递归呢?

你可以这样想:我每次以数组中间位置的元素为界限,将数组拆分成两半。紧接着,又对已经拆分成两半的那两个数组再次进行这个操作。直至拆到没有元素或者是只剩一个元素为止,所以我们就可以推导出递归的条件为:左区间是否大于等于右区间。

2.1.2 将拆解的数组的元素放到一个临时空间中进行重新排序

图片
这段代码的作用:将拆解的数组的元素放到一个临时空间中进行重新排序。

有的人会问,那最后两个循环是怎么回事?

其实是这样的,你可以假设现在你有两个有序的数组,你要将这两个数组组成一个有序(升序)的数组,你会这么做:首先,你会分别拿出两个数组中的第一个元素互相比较,发现有其中一个元素的值比另一个要小,你就把那个小的元素的值放到一个你为一个有序(升序)的数组而申请的内存空间中,之后就拿下一个元素跟这个上次那个元素的值进行比较。
到后面,你会发现肯定有个数组里面的元素是没有被选中的,但是我们也不知道是哪一个,所以我们就可以都遍历一遍找到还没有被选中的元素,将它加进到你申请的空间中。

2.1.3 将在临时空间中排好的数组复制到目标数组中

这里你可以使用for循环,也可以用一个函数memcpy。这里我选择用后者。
函数
当然,里面的参数十分的讲究。

解释:

  • a+left:这里不能直接写a。原因是,每一次拷贝会目标数组的位置不都是数组的头。
  • tmp+left:这里也不能直接写为tmp。原因是,每一次让待排序数组位置的元素进行排序时,我们要求位置得一一对应。

hahaha


3. 归并排序的非递归写法

非递归归并排序的主要步骤:

  1. 🍉初始化步长(子数组长度)为 1,这意味着开始时每个元素作为一个单独的有序数组。
  2. 🍉两两合并相邻的子数组,将步长长度的相邻子数组进行合并,形成更大的有序子数组。
  3. 🍉逐步增加步长,每次将步长翻倍,然后继续合并相邻的子数组,直到整个数组完全排序。

非递归归并排序的核心思想:归并排序的递归版从上到下拆分数组,而非递归版则从下到上逐步合并,模拟递归中“合并”的过程。在这个过程中,我们通过循环控制子数组的长度,每次将相邻的子数组合并成更大的有序数组。

具体步骤:

  1. 🍇从长度为 1 的子数组开始,对整个数组进行遍历,每两个相邻的子数组合并成一个长度为 2 的有序子数组。
  2. 🍇再次遍历时,将步长翻倍至 2,对整个数组中相邻的两个长度为 2 的有序子数组进行合并,形成长度为 4 的有序子数组。
  3. 🍇重复此过程,不断将步长翻倍(4, 8, 16,直到步长大于数组长度),直到整个数组有序。

由此,我们就可以通过上述思想,写出两个版本的代码:
版本1:

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap <= n / 2){for (int i = 0; i < n; i += 2 * gap){//划分区间:[begin1,end1][begin2,end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//控制区间的边界if (end1 >= n){end1 = n - 1;begin2 = n;end2 = n - 1;}else if (begin2 >= n){begin2 = n;end2 = n - 1;}else if (end2 >= n){end2 = n - 1;}int j = i;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+i, tmp+i, sizeof(int) * (end2-i+1));}memcpy(a, tmp, sizeof(int) * n);gap *= 2;}free(tmp);tmp = NULL;
}

版本2:

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap <= n / 2){for (int i = 0; i < n; i += 2 * gap){//划分区间:[begin1,end1][begin2,end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}int j = i;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+i, tmp+i, sizeof(int) * (end2-i+1));}gap *= 2;}free(tmp);tmp = NULL;
}

好了,到这里归并排序的内容就已经全部讲完了。如果大家觉得本文写的还不错的话。麻烦给偶点个赞吧!!!

哈哈哈

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/450624.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

CTFHub | HTTP协议 - 请求方式 | 题解实操

CTFHUB 的 HTTP 请求方式题目为参与者带来了独特的挑战和学习机会。在这个题目中&#xff0c;要求参与者使用特定的方式请求来获取 flag。这不仅考验了参与者对 HTTP 请求方法的理解和掌握程度&#xff0c;还促使他们探索不同的工具和技术来解决问题。 题目背景设定在网络安全…

关于MyBatis-Plus 提供Wrappers.lambdaQuery()的方法

实例&#xff1a; private LambdaQueryWrapper<XXX> buildQueryWrapper(XXXBo bo) { Map<String, Object> params bo.getParams(); LambdaQueryWrapper<XXX> lqw Wrappers.lambdaQuery(); lqw.eq(bo.getOrgId() ! null, XXX::getOrgId, bo.getOrgId()); lq…

拼三角问题

欢迎来到杀马特的主页&#xff1a;羑悻的小杀马特.-CSDN博客 目录 一题目&#xff1a; 二思路&#xff1a; 三解答代码&#xff1a; 一题目&#xff1a; 题目链接&#xff1a; 登录—专业IT笔试面试备考平台_牛客网 二思路&#xff1a; 思路&#xff1a;首先明白能组成三角形…

新生入门季 | 学习生物信息分析,如何解决个人电脑算力不足的问题?

随着生物信息学在科研和教育中的快速普及&#xff0c;越来越多的新生开始接触基因组测序、RNA分析等复杂计算任务。然而&#xff0c;在面对这些大规模数据时&#xff0c;个人电脑的算力往往显得捉襟见肘。你是否也在为自己的笔记本性能不足而苦恼&#xff1f; 这篇文章将为你提…

JavaWeb——Maven(4/8):Maven坐标,idea集成-导入maven项目(两种方式)

目录 Maven坐标 导入Maven项目 第一种方式 第二种方式 Maven坐标 Maven 坐标 是 Maven 当中资源的唯一标识。通过这个坐标&#xff0c;我们就能够唯一定位资源的位置。 Maven 坐标主要用在两个地方。第一个地方&#xff1a;我们可以使用坐标来定义项目。第二个地方&#…

FreeRTOS - 软件定时器

在学习FreeRTOS过程中&#xff0c;结合韦东山-FreeRTOS手册和视频、野火-FreeRTOS内核实现与应用开发、及网上查找的其他资源&#xff0c;整理了该篇文章。如有内容理解不正确之处&#xff0c;欢迎大家指出&#xff0c;共同进步。 1. 软件定时器 软件定时器也可以完成两类事情…

Spring AI Alibaba 接入国产大模型通义千问

整体介绍 本文是一个详细的例子&#xff0c;讲解了如何基于spring ai 来调用通义千问国产大模型&#xff0c;有详细的代码和配置&#xff0c;并且免费。 Spring AI&#xff1a;简化Java开发者构建AI应用的统一框架 在过去&#xff0c;Java 开发者在构建 AI 应用时面临的一大…

【ios】解决xcode版本过低无法真机调式的问题

最低要求和支持的 SDK&#xff1a;Xcode - 支持 - Apple Developer 我的Xcode版本是14.2 手机系统版本是iOS15.8.3 步骤一 在终端中运行 open /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/DeviceSupport 步骤二 先去https://github.com/fi…

AI 设计工具合集

&#x1f423;个人主页 可惜已不在 &#x1f424;这篇在这个专栏AI_可惜已不在的博客-CSDN博客 &#x1f425;有用的话就留下一个三连吧&#x1f63c; ​ 前言: AI 视频&#xff0c;科技与艺术的精彩融合。它借助先进的人工智能技术&#xff0c;为影像创作带来全新可能。本书…

星海智算:【萤火遛AI-Stable-Diffusion】无需部署一键启动

部署流程 1、注册算力云平台&#xff1a;星海智算 https://gpu.spacehpc.com/ 2、创建实例&#xff0c;镜像请依次点击&#xff1a;“镜像市场”->“更换”->“AI绘画”->“萤火遛AI-Stable Diffusion”。 程序首次启动可能需要几分钟&#xff0c;待实例显示“运行…

2009年国赛高教杯数学建模A题制动器试验台的控制方法分析解题全过程文档及程序

2009年国赛高教杯数学建模 A题 制动器试验台的控制方法分析 汽车的行车制动器&#xff08;以下简称制动器&#xff09;联接在车轮上&#xff0c;它的作用是在行驶时使车辆减速或者停止。制动器的设计是车辆设计中最重要的环节之一&#xff0c;直接影响着人身和车辆的安全。为了…

MOE论文详解(4)-GLaM

2022年google在GShard之后发表另一篇跟MoE相关的paper, 论文名为GLaM (Generalist Language Model), 最大的GLaM模型有1.2 trillion参数, 比GPT-3大7倍, 但成本只有GPT-3的1/3, 同时效果也超过GPT-3. 以下是两者的对比: 跟之前模型对比如下, 跟GShard和Switch-C相比, GLaM是第一…

[WPF初学到大神] 1. 什么是WPF, MVVM框架, XAML?

什么是WPF? WPF(Windows Presentation Foundation) 包含XAML标记语言和后端代码来开发桌面应用程序的. 用VS新建项目有WPF(.Net Framework和.Net应用程序), 该怎么选? 首选 .NET 应用程序(.NET Core 或 .NET 5/6/7/8新版本)拥有更好的性能、跨平台Windows, Linux, Mac支…

电气自动化13:PLC控制硬件组成与工作扫描原理

1.PLC硬件组成&#xff1a; CPU&#xff08;中央处理器&#xff09; 存储器 系统程序存储器用户程序存储器分为&#xff1a;用户程序存储器&#xff08;程序区&#xff09;、功能存储器&#xff08;数据区&#xff09; 输入/输出&#xff08;I/O&#xff09;接口电路 电源 …

SpringBoot优雅下线

一&#xff0c;什么是优雅下线 当我们需要部署新版本代码的时候&#xff0c;需要重启服务&#xff0c;这个时候可能会出现一些问题&#xff0c;比如之前服务正在处理的请求还在处理&#xff0c;这个时候如果强制的停止服务&#xff0c;会造成数据丢失或者请求失败的情况。那么…

后端Web开发

一、Maven &#xff08;一&#xff09;、概述 视频中要用的是jdk11 &#xff08;二&#xff09;、 idea集成Maven 1.配置Maven环境 2.创建Maven项目 3.导入Maven项目 法一&#xff1a; 法二&#xff1a; &#xff08;三&#xff09;、依赖管理 1.依赖配置 2.依赖传递 3.依…

数控机械制造工厂ERP适用范围有哪些

在当今制造业高速发展的背景下&#xff0c;企业资源计划(ERP)系统已成为提升工厂管理效率、实现生产自动化与信息化的关键工具。特别是对于数控机械制造工厂而言&#xff0c;一个合适的ERP系统能够帮助其优化生产流程、提高产品质量、降低生产成本并增强市场竞争力。 1. 生产计…

06 算法基础:算法的定义、表现形式(自然语言、伪代码、流程图)、五个特性(有穷性、确定性、可行性、输入、输出)、好算法的设计目标

目录 1 算法的定义 2 算法的三种表现形式 2.1 自然语言 2.2 伪代码 2.3 流程图 3 算法的五个特性 3.1 有穷性 3.2 确定性 3.3 可行性 3.4 输入 3.5 输出 4 好算法的设计目标 4.1 正确性 4.2 可读性 4.3 健壮性 4.4 通用性 4.5 高效率与低存储量 1 算法的定义 …

Java笔记-static关键字

1.static关键字内存说明 2.访问特点 package com.test.Statics2;import com.test.statics.Student;public class Test {public static void main(String[] args) {// 静态成员中访问非静态成员// method3() // 错误-不能直接调用&#xff0c;需要new对象调用Test test01 new T…

英伟达开源超强模型Nemotron-70B;OpenAI推出Windows版ChatGPT桌面客户端

&#x1f989; AI新闻 &#x1f680; 英伟达开源超强模型Nemotron-70B 摘要&#xff1a;英伟达近日开源了新型AI模型Nemotron-70B&#xff0c;迅速超越GPT-4o和Claude 3.5 Sonnet&#xff0c;成为AI社区的新宠。该模型在多项基准测试中表现优异&#xff0c;采用混合训练方法和…