[ 数据结构 -- 手撕排序算法第七篇 ] 归并排序

news/2024/4/21 0:51:24/

文章目录

  • 前言
  • 一、常见的排序算法
  • 二、归并排序的基本思想
  • 三、归并排序
    • 3.1 归并排序的递归版本
    • 3.2 归并排序的非递归版本
  • 四、归并排序的特性总结


前言

手撕排序算法第七篇:归并排序!
从本篇文章开始,我会介绍并分析常见的几种排序,例如像插入排序,冒泡排序,希尔排序,选择排序,快速排序,堆排序,归并排序等等!
这篇文章我先来给大家手撕一下归并排序

大家可以点下面的链接去阅读其他的排序算法:
C语言手撕排序算法


正文开始!

一、常见的排序算法

在这里插入图片描述

二、归并排序的基本思想

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

核心步骤根据图来理解:
在这里插入图片描述
在这里插入图片描述

三、归并排序

3.1 归并排序的递归版本

void _MergeSort(int* a,int begin,int end,int* tmp)
{if (begin >= end)return;int mid = (begin + end) >> 1;//[begin,mid][mid+1,end]_MergeSort(a,begin,mid,tmp);_MergeSort(a,mid+1,end,tmp);//归并[begin,mid][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){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}//memcpy(a+begin,tmp+begin,(end-begin+1)*sizeof(int));for (int i = begin; i <= end; i++){a[i] = tmp[i];}
}
void MergeSort(int* a,int n)
{int* tmp = (int*)malloc(sizeof(int) * n);assert(tmp);_MergeSort(a,0,n-1,tmp);free(tmp);
}
void TestMergeSort()
{int a[] = { 10,6,7,3,9,1,4,2 };printf("排序前:");PrintArray(a, sizeof(a) / sizeof(a[0]));MergeSort(a,sizeof(a) / sizeof(a[0]));printf("排序后:");PrintArray(a, sizeof(a) / sizeof(a[0]));
}
int main()
{TestMergeSort();return 0;
}

在这里插入图片描述

3.2 归并排序的非递归版本

画图分析如下:
在这里插入图片描述
在这里插入图片描述
我们可以发现利用上述的思想就可以实现非递归排序。

但是在这里随意加一个数字,程序就崩溃了,这是为什么呢?

先来实验结果:

在这里插入图片描述
我先利用6个数给大家讲讲,数太多了,分析起来不容易理解!

在这里插入图片描述

在这里只有可能end1,begin2,end2可能会越界,所以在归并之前控制约束条件即可!

完整代码如下

//归并排序的非递归版本
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);assert(tmp);int gap = 1;while (gap<n){//间距为gap的是一组,两两归并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 index = i;//end1越界,修正即可if (end1 >= n){end1 = n - 1;}//begin2越界,证明后半区间不存在if (begin2 >= n){begin2 = n;end2 = n-1;}//begin2存在,end2越界,修正end2即可if (begin2 < n && end2 >= n){end2 = n - 1;}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 , tmp , n * sizeof(int));gap *= 2;}free(tmp);
}
void TestMergeSort()
{int a[] = { 10,6,7,3,9,1};printf("排序前:");PrintArray(a, sizeof(a) / sizeof(a[0]));MergeSortNonR(a, sizeof(a) / sizeof(a[0]));printf("排序后:");PrintArray(a, sizeof(a) / sizeof(a[0]));
}
int main()
{TestMergeSort();return 0;
}

在这里插入图片描述
此时归并排序的非递归版本就实现啦!

四、归并排序的特性总结

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多实在解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN).
  3. 空间复杂度:O(N).
  4. 稳定性:稳定.

(本章完!)


http://www.ppmy.cn/news/5264.html

相关文章

牛客竞赛每日俩题 - Day10

目录 输入输出的细节 函数find&#xff08;&#xff09;的用法 输入输出的细节 收件人列表__牛客网 细节一&#xff1a;当输入转行后又要使用getline&#xff08;&#xff09;时&#xff0c;必须先使用getchar&#xff08;&#xff09;吃掉前面的转行符\n;细节二&#xff1a…

Java——记录BigDecimal与0比较的一个坑

文章目录前言问题解决问题解决前言 在之前做的一个项目中&#xff0c;为了保证BigDecimal在除数 divide时&#xff0c;如果被除数为0&#xff0c;出现java.lang.ArithmeticException: / by zero 报错问题&#xff0c;写了一个对比。具体代码如下&#xff1a; public static B…

jdk8新特性

一、lambda表达式 Lambda表达式相当于是对接口抽象方法的重写 对比匿名内部类与lambda表达式 package com.bz.jdk8.demo01_Lambda; /*** 体验Lambda表达式*/ public class Demo01LambdaIntro {public static void main(String[] args) {// 使用匿名内部类存在的问题// public …

React Native - webview 内外通信

React Native - webview 内外通信 消息的传递需要注意是字符串. webview 向 RN 发送消息 js 发送消息: if (window.ReactNativeWebView) {ReactNativeWebView.postMessage("123321"); }RN 收消息: <WebViewref{webView}originWhitelist{[*]}javaScriptEnable…

Educational Codeforces Round 136 (Rated for Div. 2) C. Card Game

原题链接&#xff1a;Problem - 1739C - Codeforces 题意&#xff1a;n 张卡&#xff0c;Alice 和Bob 轮流出牌&#xff0c;对方应牌&#xff0c;不能应牌的一方失败&#xff0c;应牌要求是比对方出的大。 思路&#xff1a;我们考虑Alice必胜的情况&#xff1a; 1.若AIice拿…

艾美捷耗氧率检测试剂盒说明书及相关研究

细胞内稳态通过ATP的产生来维持。ATP的生成可以通过单独的糖酵解&#xff08;无氧呼吸&#xff09;或通过糖酵解与氧化磷酸化的耦合来完成。氧化磷酸化是氧&#xff08;O2&#xff09;依赖性的&#xff0c;发生在线粒体中&#xff0c;是哺乳动物细胞合成ATP的最有效和优选的方法…

【Numpy基础知识】使用genfromtxt导入数据

使用Numpy进行I/O操作 来源&#xff1a;Numpy官网&#xff1a;https://numpy.org/doc/stable/user/basics.html 文章目录使用Numpy进行I/O操作导包【1】定义输入【2】将行拆分为列【3】跳过行和选择列【4】选择数据类型【5】设置名称【6】调整转换【7】快捷键功能NumPy 提供了几…

java实验报告之Employee类的设计

一个不知名大学生&#xff0c;江湖人称菜狗 original author: jacky Li Email : 3435673055qq.com Time of completion&#xff1a;2022.12.20 Last edited: 2022.12.20 目录 一、实验目的 二、实验内容 三、总体设计&#xff08;设计原理、设计方案及流程等&#xff09; 四…

jmeter简单压力测试

测试目的&#xff1a;10个用户并发访问一个接口&#xff08;http://127.0.0.1:8080/dfm/login.action&#xff09;&#xff0c;能否正常响应。 一、打开JMeter 二、右击“测试计划”&#xff0c;添加线程组 三、设置线程组的线程数 JMeter中的线程组&#xff0c;类似于LoadRunn…

web--拉灯泡切换黑天与白夜的精美动画

功能&#xff1a; 进入界面会出现一个灯泡&#xff08;下面有可以自由飘动也可以自由拉动的绳子&#xff09;&#xff0c;鼠标左键按住不松开可以拉动绳子&#xff0c;松开变化亮起&#xff0c;同时有拉响的清脆声响&#xff0c;把它放在web作业的设计里面绝对是非常非常不错的…

安卓架构-内核

本文是从安卓官网总结的内核相关知识。 1. 概览 安卓内核用的也是linux&#xff08;LTS&#xff09;&#xff0c;google把LTS内核和Android的一些补丁、模块结合形成自己的Android通用内核&#xff08;Android common kernel&#xff0c;ACK&#xff09;。也就是GKI, Generic…

服务攻防-中间件安全CVE 复现K8sDockerJettyWebsphere

目录 (一)中间件-kubernetes 1、认识k8s 2、判定k8s 3、安全问题 (二)中间件-Docker

RCTFweb复现

文章目录filechecker_minieasy_uploadfilechecker_plusfilechecker_pro_maxezbypassezruoyifilechecker_mini 给了附件&#xff0c;代码比较短&#xff0c;先审计一下。 在这里发现了file –b命令&#xff0c;且filepath部分可控&#xff0c;明显的ssti漏洞&#xff0c;没过…

Java中的StringBuilder类

目录 一、StringBuilder类介绍 二、StringBuilder类的体系图 三、StringBuilder类的常用方法 四、String类、StringBuffer类和StringBuilder类比较 1、效率比较 2、如何选择&#xff1f; 一、StringBuilder类介绍 StringBuilder也是lang包中的类&#xff0c;即java.lang.S…

MySQL 服务端口大全

介绍 MySQL默认服务端口3306/TCP都不会陌生&#xff0c;但MySQL提供服务只有单纯的这个端口吗。在8.0版本默认启动的时候会发现&#xff0c;出现新的端口。 可以说MySQL使用的端口数量取决于所启用的特性、所使用的组件、应用程序连接的方式以及环境的其他方面。 按照官方说…

如何使用FastReport .NET 从 JetBrains Rider 中创建PDF报告?

Fastreport是目前世界上主流的图表控件&#xff0c;具有超高性价比&#xff0c;以更具成本优势的价格&#xff0c;便能提供功能齐全的报表解决方案&#xff0c;连续三年蝉联全球文档创建组件和库的“ Top 50 Publishers”奖。 FastReport.NET官方版下载&#xff08;qun&#x…

状态观测控制器设计与仿真验证

【无限嚣张&#xff08;菜菜&#xff09;】&#xff1a;hello您好&#xff0c;我是菜菜&#xff0c;很高兴您能来访我的博客&#xff0c;我是一名爱好编程学习研究的菜菜&#xff0c;每天分享自己的学习&#xff0c;想法&#xff0c;博客来源与自己的学习项目以及编程中遇到问题…

嵌入式分享合集124

一、19个常用的5V转3.3V技巧 01 使用LDO稳压器 标准三端线性稳压器的压差通常是 2.0-3.0V。要把 5V 可靠地转换为 3.3V&#xff0c;就不能使用它们。压差为几百个毫伏的低压降 &#xff08;Low Dropout&#xff0c; LDO&#xff09;稳压器&#xff0c;是此类应用的理想选择。图…

聊聊设计模式-备忘录模式?

简介 备忘录模式是一种行为设计模式&#xff0c;允许在不暴露对象实现细节的情况下保存和恢复对象之前的状态&#xff0c;也就是在不破坏封装性的前提下&#xff0c;捕获一下对象的内部状态&#xff0c;并在该对象之外保存这个状态&#xff0c;以便以后当需要时能将该对象之外…