排序算法：归并排序（递归和非递归）

朋友们、伙计们，我们又见面了，本期来给大家解读一下有关排序算法的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

C 语 言 专 栏：C语言：从入门到精通

数据结构专栏：数据结构

个  人  主  页 ：stackY、

​

目录

1.归并排序

1.1递归版本

代码演示：

1.2非递归版本 

代码演示：

测试排序：

改正代码1：

测试排序：

改正代码2：

1.3递归版本的优化

代码演示：

2.归并排序特性

1.归并排序

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

 

归并排序也分为递归和非递归版本，下面我们就来逐步学习： 

1.1递归版本

从上面的图中我们可以看出归并排序是分为两个阶段分解和合并，那么转化为代码的思想就是先划分小区间，然后将区间中最小的单独拿出来在另外的一个数组中进行尾插，等到最后一组数据排完之后，再将尾插排序完的整个数组再拷贝至原数组，这样子就完成了整个数组的排序。

那么通过这个过程可以发现：归并排序是需要单独开一个数组的，所以它的

空间复杂度是O（N），另外归并排序是先划分小区间再进行排序，那么就和二叉树中的后序遍历逻辑类似，先将整个数据一分为二，使得左区间和右区间有序，然后再将左右两个区间进行排序，那么整个数据就有序了，所以需要让左右区间再有序，也需要将做右区间各划分为两个区间，并且让它们的左右区间再有序，以此类推，直到区间内只剩一个数据就不需要再划分了，然后取两个区间小的值尾插到单独的一个数组，最后再次整体拷贝至原数组。

在递归时要注意几个问题：

1. 在递归的时候需要保存两个区间的起始和终止位置，以便访问。

2. 当一个区间已经尾插完毕，那么直接将另外一个区间的数据依次尾插。

3. 两个区间的数据都尾插完毕至tmp数组时，需要将tmp数组的数据再次拷贝至原数组。

4. 在拷贝到原数组时需要注意尾插的哪一个区间就拷贝哪一个区间。 

代码演示：

void _MergerSort(int* a, int begin, int end, int* tmp)
{//递归截止条件if (begin == end)return;//划分区间int mid = (begin + end) / 2;//[begin,mid] [mid+1,end]//递归左右区间_MergerSort(a, begin, mid, tmp);_MergerSort(a, mid + 1, end, tmp);//将区间保存int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;//取两个区间小的值尾插//一个区间尾插完毕另一个区间直接尾插即可while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//再将剩余数据依次尾插//哪个区间还没有尾插就尾插哪一个while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//再重新拷贝至原数组//尾插的哪个区间就将哪个区间拷贝memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}//归并排序
void MergerSort(int* a, int n)
{//先创建一个数组int* tmp = (int*)malloc(sizeof(int) * n);_MergerSort(a, 0, n - 1, tmp);//释放free(tmp);
}
归并排序的特性总结：
1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(N)
4. 稳定性：稳定

1.2非递归版本 

由于递归代码在数据太多时可能会因为递归太深出现问题，所以我们也需要写出它们所对应的非递归版本的排序代码：非递归版本的归并排序直接可以使用循环来完成，但是坑点非常多，接下来我们就来慢慢排查。

我们可以先一个数据为一组，然后两两进行排序，然后将排序完的整体结果再重新拷贝至原数组，这样子就完成了一次排序，然后再将排序完的结果两个数据为一组，然后两两排序，然后将排序完的数据再拷贝至原数组，这样子就完成了第二次的排序，然后将数据四个分为一组，两两进行排序，再将排序完的数据拷贝至原数组，直到每组的数据超过或者等于数据的总长度即不需要在进行排序。

首先我们先创建一个开辟一个数组，然后设置一个gap用来分组，然后记录两个区间，对两个区间的数进行比较，小的尾插，再将剩余数据继续尾插，然后完成了一趟排序，再将排完序的数据再拷贝至原数组，再将gap * 2，继续完成剩余的排序，直到划分组的gap大于等于数据总长度即可完成全部的排序：

代码演示：

//归并排序
//非递归
void MergerSortNonR(int* a, int n)
{//创建数组int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("tmp");exit(-1);}//划分组数int gap = 1;while (gap < n){int j = 0;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;//取两个区间小的值尾插//一个区间尾插完毕另一个区间直接尾插即可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, tmp, sizeof(int) * n);//更新gapgap *= 2;}//释放free(tmp);
}
测试排序：
void PrintArry(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestMergerSortNonR()
{int a[] = { 10,6,7,1,3,9,4,2 };PrintArry(a, sizeof(a) / sizeof(int));MergerSortNonR(a, sizeof(a) / sizeof(int));PrintArry(a, sizeof(a) / sizeof(int));
}int main()
{TestMergerSortNonR();return 0;
}

可以看到排序完成，而且还完成的不错，那么我们再来几组数据进行测试：

在这里我们使用的是8个数据，那如果我们使用9个或者10个数据呢？

void PrintArry(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestMergerSortNonR()
{int a[] = { 10,6,7,1,3,9,4,2,8,5 };PrintArry(a, sizeof(a) / sizeof(int));MergerSortNonR(a, sizeof(a) / sizeof(int));PrintArry(a, sizeof(a) / sizeof(int));
}int main()
{TestMergerSortNonR();return 0;
}

可以看到数据发生错误，那么到底是为什么呢？我们可以来一起观察一下：

随着gap的2倍递增，那么会发生数据区间越界的问题，因为当数据是10个的时候，gap会递增到8，因此在访问数据的时候会发生越界，我们也可以观察一下这个越界的现象：

可以将数据访问的区间打印出来：

那么该怎么解决这个问题呢？

1. 首先不能排完一次序然后将数据整体拷贝，需要排完一组，拷贝一组。

2. 其次当发生越界中的第一、二种时可以直接break。

3. 当发生越界中的第三种时可以将边界进行修正。

改正代码1：

//归并排序
//非递归
void MergerSortNonR(int* a, int n)
{//创建数组int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("tmp");exit(-1);}//划分组数int gap = 1;while (gap < n){int j = 0;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;//end1和begin2越界直接跳出if (end1 >= n || begin2 >= n){break;}//end2越界可以进行修正if (end2 >= n){end2 = n - 1;}//取两个区间小的值尾插//一个区间尾插完毕另一个区间直接尾插即可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);
}
测试排序：
void PrintArry(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestMergerSortNonR()
{int a[] = { 10,6,7,1,3,9,4,2,8,5 };PrintArry(a, sizeof(a) / sizeof(int));MergerSortNonR(a, sizeof(a) / sizeof(int));PrintArry(a, sizeof(a) / sizeof(int));printf("\n");int a2[] = { 10,6,7,1,3,9,4,2 };PrintArry(a2, sizeof(a2) / sizeof(int));MergerSortNonR(a2, sizeof(a2) / sizeof(int));PrintArry(a2, sizeof(a2) / sizeof(int));printf("\n");int a3[] = { 10,6,7,1,3,9,4,2,8 };PrintArry(a3, sizeof(a3) / sizeof(int));MergerSortNonR(a3, sizeof(a3) / sizeof(int));PrintArry(a3, sizeof(a3) / sizeof(int));printf("\n");}int main()
{TestMergerSortNonR();return 0;
}

改正过后就完全的解决了越界的问题，那么这种改进方法是归并一组，拷贝一组。

我们也可以将全部越界的区间进行修正，然后排序完一次将整个数据拷贝。

改正代码2：

将越界区间全部修正也是可以达到改进的目的，我们就以归并数据的逻辑为基础，然后修改区间，因此需要将越界的区间改为不存在的区间即可：

//归并排序
//非递归
//改进代码2：
void MergerSortNonR(int* a, int n)
{//创建数组int* tmp = (int*)malloc(sizeof(int) * n);//划分组数int gap = 1;while (gap < n){int j = 0;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 (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;}//取两个区间小的值尾插//一个区间尾插完毕另一个区间直接尾插即可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, tmp, sizeof(int) * n);gap *= 2;}//释放free(tmp);
}

 

1.3递归版本的优化

 当数据量非常多的时候使用递归版本可以进行一个优化，当递归到小区间的时候，我们可以采用插入排序来进行优化，这个优化只限于递归版本，在进行小区间中的插入排序时需要注意在前面的步骤递归到了哪个区间就使用插入排序排序哪个区间，所以在进行插入排序的时候需要注意排序的区间。

代码演示：

void _MergerSort(int* a, int begin, int end, int* tmp)
{//递归截止条件if (begin == end)return;小区间优化//区间过小时直接使用插入排序，减少递归损耗if (end - begin + 1 < 10){//         注意排序的区间InsertSort(a + begin, end - begin + 1); return;}//划分区间int mid = (begin + end) / 2;//[begin,mid] [mid+1,end]//递归左右区间_MergerSort(a, begin, mid, tmp);_MergerSort(a, mid + 1, end, tmp);//将区间保存int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;//取两个区间小的值尾插//一个区间尾插完毕另一个区间直接尾插即可while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//再将剩余数据依次尾插//哪个区间还没有尾插就尾插哪一个while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//再重新拷贝至原数组//尾插的哪个区间就将哪个区间拷贝memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}//归并排序
void MergerSort(int* a, int n)
{//先创建一个数组int* tmp = (int*)malloc(sizeof(int) * n);_MergerSort(a, 0, n - 1, tmp);//释放free(tmp);
}

2.归并排序特性

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

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！ 

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

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

相关文章

什么是ELK

什么是ELK

什么是ELK ELK 并不是一个技术框架的名称&#xff0c;它其实是一个三位一体的技术名词&#xff0c;ELK 的每个字母都来自一个技术组件&#xff0c;分别是 Elasticsearch&#xff08;简称 ES&#xff09;、Logstash 和 Kibana。 三个技术组件是独立的&#xff0c;后两个被elast…
阅读更多...
table 写表格

table 写表格

<!-- colspan"3" 合并3列 --> <!-- rowspan"4" 合并4行 --> <!-- 7行4列 --><table><tr><th>企业名称</th><td>2020.11.11</td><th>法定代表人</th><td>2020.11.11</td>&l…
阅读更多...
Nginx替代产品-Tengine健康检测

Nginx替代产品-Tengine健康检测

1、官网地址 官网地址&#xff1a;The Tengine Web Server 文档地址&#xff1a;文档 - The Tengine Web Server 健康检测模块&#xff1a;ngx_http_upstream_check_module - The Tengine Web Server 2、安装 下载 wget https://tengine.taobao.org/download/tengine-3.…
阅读更多...
如何使用ArcGIS Pro提取河网水系

如何使用ArcGIS Pro提取河网水系

DEM数据除了可以看三维地图和生成等高线之外&#xff0c;还可以用于水文分析&#xff0c;这里给大家介绍一下如何使用ArcGIS Pro通过水文分析提取河网水系&#xff0c;希望能对你有所帮助。 数据来源 本教程所使用的数据是从水经微图中下载的DEM数据&#xff0c;除了DEM数据&a…
阅读更多...
PASCAL VOC2012数据集详细介绍

PASCAL VOC2012数据集详细介绍

PASCAL VOC2012数据集详细介绍 0、数据集介绍2、Pascal VOC数据集目标类别3、 数据集下载与目录结构4、目标检测任务5、语义分割任务6、实例分割任务7、类别索引与名称对应关系 0、数据集介绍 2、Pascal VOC数据集目标类别 在Pascal VOC数据集中主要包含20个目标类别&#xff…
阅读更多...
初见QT，控件的基本应用，实现简单登录窗口

初见QT，控件的基本应用，实现简单登录窗口

窗口实现代码 #include "widget.h"Widget::Widget(QWidget *parent): QWidget(parent) {//窗口设置this->setFixedSize(538, 373); //固定窗口大小this->setWindowIcon(QIcon("G:\\QT_Icon\\windos_icon2.png"))…
阅读更多...
线性代数基础-行列式

线性代数基础-行列式

一、行列式之前的概念 1.全排列&#xff1a; 把n个不同的元素排成一列&#xff0c;称为n个元素的全排列&#xff0c;简称排列 &#xff08;实际上就是我们所说的排列组合&#xff0c;符号是A&#xff0c;arrange&#xff09; 2.标准序列&#xff1a; 前一项均小于后一项的序列…
阅读更多...
微博情绪分类

微博情绪分类

引自&#xff1a;https://blog.csdn.net/no1xiaoqianqian/article/details/130593783 友好借鉴&#xff0c;总体抄袭。 所需要的文件如下&#xff1a;https://download.csdn.net/download/m0_37567738/88340795 import os import torch import torch.nn as nn import numpy a…
阅读更多...
32:TX Text Control ActiveX/ASP.NET/WinForms/WPF Crack

32:TX Text Control ActiveX/ASP.NET/WinForms/WPF Crack

TX Text Control ActiveX 32.0 添加操作“普通”样式表的能力。 2023 年 9 月 14 日 - 15:38新版本 特征 脚注- 在文档中插入与 Microsoft Word 兼容的脚注。脚注是一种文字处理功能&#xff0c;允许用户在页面底部插入附加信息。 可编辑的[普通]样式表- 添加了操作[普通]样式的…
阅读更多...
9.20号作业实现钟表

9.20号作业实现钟表

1.widget.h #include <QPainter> //画家 #include <QTimerEvent> #include <QTime> #include<QTimer> //定时器类QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Wid…
阅读更多...
物联网网络安全：保护物理世界和数字世界的融合

物联网网络安全：保护物理世界和数字世界的融合

我们正在见证数字技术如何成为我们日常生活和经济系统的一部分&#xff0c;从而提高福利并增强竞争力。尽管如此&#xff0c;新的尖端互联技术的迅速出现和采用也对政府、企业和整个社会构成了重大威胁。 长期以来&#xff0c;网络安全威胁一直是电影行业的一个现成的灵感来源&…
阅读更多...
el-table表格中加入输入框

el-table表格中加入输入框

<template><div class"box"><div class"btn"><el-button type"primary">发送评委</el-button><el-button type"primary" click"flag true" v-if"!flag">编辑</el-button…
阅读更多...
RFID技术在仓储物流供应链管理中的应用

RFID技术在仓储物流供应链管理中的应用

仓储物流供应链管理的透明度和库存周转率成为管控的重点&#xff0c;为了提高仓储物流的效率和减少库存损失&#xff0c;RFID技术被广泛应用于仓储、分发、零售管理等各个环节&#xff0c;为供应链管理带来了巨大的改变和提升。 首先&#xff0c;采用RFID技术进行仓库物流智能化…
阅读更多...
Jenkins “Trigger/call builds on other project“用法及携带参数

Jenkins “Trigger/call builds on other project“用法及携带参数

1.功能 “Trigger/call builds on other project” 功能是 Jenkins 中的一个特性&#xff0c;允许您在某个项目的构建过程中触发或调用另一个项目的构建。 当您在 Jenkins 中启用了 “Trigger/call builds on other project” 功能并配置了相应的触发条件后&#xff0c;当主项…
阅读更多...
（三十二）大数据实战——Maxwell安装部署及其应用案例实战

（三十二）大数据实战——Maxwell安装部署及其应用案例实战

前言 Maxwell是一个开源的MySQL数据库binlog解析工具&#xff0c;用于将MySQL数据库的binlog转换成易于消费的JSON格式&#xff0c;并通过Kafka、RabbitMQ、Kinesis 等消息队列或直接写入文件等方式将其输出。本节内容主要介绍如何安装部署Maxwell以及如何使用Maxwell完成数据…
阅读更多...
从淘宝数据分析产品需求（商品销量总销量精准月销）

从淘宝数据分析产品需求（商品销量总销量精准月销）

淘宝数据分析总体来说可以分为商品分析、客户分析、地区分析、时间分析四大维度(参考数据雷达的分析思路)。在这里我重点说商品分析。 在淘宝上开店的竞争还是非常激烈的&#xff0c;随便拿出一个单品就有很多竞品存在&#xff0c;所以做起来还是很难的&#xff0c;而想要在众…
阅读更多...
嵌入式学习 - 用电控制电

嵌入式学习 - 用电控制电

目录 前言&#xff1a; 1、继电器 2、二极管 3、三极管 3.1 特殊的三极管-mos管 3.2 npn类型三极管 3.3 pnp类型三极管 3.4 三极管的放大特性 3.5 mos管和三极管的区别 前言&#xff1a; 计算机的工作的核心原理&#xff1a;用电去控制电。 所有的电子元件都有数据手册…
阅读更多...
MySQL的高级SQL语句

MySQL的高级SQL语句

目录 一、高级SQL语句 1、select 查询表中一个或多个字段的数据 2、distinct 不显示重复的数据记录 3、where 有条件查询 4、and与or 且与或 5、in 显示在某个范围值内 的字段的信息 6、between 显示两个值范围内的数据记录 7、order by 对字…
阅读更多...
ChatGLM 实现一个BERT

ChatGLM 实现一个BERT

前言 本文包含大量源码和讲解，通过段落和横线分割了各个模块，同时网站配备了侧边栏，帮助大家在各个小节中快速跳转，希望大家阅读完能对BERT有深刻的了解。同时建议通过pycharm、vscode等工具对bert源码进行单步调试，调试到对应的模块再对比看本章节的讲解。 涉及到的jupyt…
阅读更多...
网络安全：保护你的系统

网络安全：保护你的系统

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023