归并排序与非比较排序详解

W...Y的主页 😊

代码仓库分享 💕


🍔前言:
上篇博客我们讲解了非常重要的快速排序,相信大家已经学会了。最后我们再学习一种特殊的排序手法——归并排序。话不多说我们直接上菜。

目录

归并排序

基本思想

递归思路 

 算法思路

代码思路以及实现

非递归思路

算法思路​编辑

代码思路以及实现

归并排序的特性总结

非比较排序 

计数排序

算法思路以及代码实现

计数排序总结

八大排序总结 


归并排序

基本思想

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

递归思路 

 算法思路

归并排序的思路就是先分再合。

1.我们将一个数组进行平分,然后继续递归进行更细小的划分秒,直到每个数组如同一个数组时,然后再进行返回。

2.返回时每个小数组中的数必须排列为有序的数。

3.然后合并每个小数组,然后继续进行排序直到数组有序即可。

我们可以展示一下归并排序的动图,让大家更好的理解:

 

代码思路以及实现

不难看出递归的过程非常像二叉树的后序遍历数组,如果左右区间都无序,我们进行向下递归,直到有序再返回合并。(只有一个数时,我们可以看作其有序)

所以我们的代码思路也与二叉树后序代码有点相似。

具体思路:

 1.创建一个与原数组相同空间大小的数组用来拷贝已经排序好的子数组。

2.创建一个函数来进行递归调用,如果使用有malloc的函数,递归时会重复开辟空间导致空间浪费,函数的参数传入原数组,新建数组与排序的起始位置与终止位置。

3.进行数组的递归调用。

4.创建临时遍历begin1、end1、begin2、end2,控制子数组的区间,然后进行比较排序成为有序子数组。

5.将有序的数组先放入新数组中,然后拷贝到原数组中进行覆盖,变为有序数组即可。

代码实现:

void _MergeSort(int* a, int* tmp, int begin, int end)
{if (end <= begin)return;int mid = (end + begin) / 2;//[begin, min][min + 1, end]_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){tmp[index++] = a[begin1++];}while (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");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}

易错点:

在拷贝时,我们不一定是从头进行拷贝,拷贝的都是与数组头的相对位置,所以在参数中我们要添加begin。 

非递归思路

为什么要进行非递归,与快速排序的原因相同,就是因为递归占用的是栈空间,而栈空间的内存非常小,所以我们要进行非递归的算法学习。而非递归与斐波那契切数的思路相当,就是已知前两个然后去推后面的数,而归并的非递归也是如此,将思路进行正向整理,从最小的开始进行即可。

算法思路

 我们先创建一个gap数进行子数组大小记录,gap为1则进行一一比较排序,gap = 2则进行两个两个比较以此类推。后面与递归思路基本相同。

代码思路以及实现

实现思路:

1.模拟递归最后一层进行比较排序。

2.每次gap *= 2.

3.当gap>=n时停止递归。

4.将有序数组进行拷贝

代码实现:

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){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;if (begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}printf("[%d][%d][%d][%d] ", begin1, end1, begin2, end2);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));}printf("\n");gap *= 2;}free(tmp);
}

 注意:当我们进行排序时,我们就会进行分组。但是有些数组中的元素个数不一定够组成一组。当我们一个一个进行分组时,我们可以将所以元素分为一组,但是当个数为奇数时,我们进行归并后进行两个一组时,就会有一个剩余。四个进行分组时也会有其中一组或两组没有分满的情况,所以我们如果不进行控制,就会出现数组越界的情况,程序就会报错。

我们将每一次的递归区间进行打印即可看出区间越界的问题:

 但是我们进行修改后就不会出现越界情况:

其中越界的有end2、begin2、end1。begin1是不会越界的。那我们将其进行边界的修正,这样即不会影响正常的归并,也不会将出错的情况算入其中。 

处理方法:

如果end2越界,则将其修改为n-1。
如果begin2和end1越界,则将其修正为不存在的区间,不存在则直接跳出了归并的过程。
共用三种出界情况.
但是如果begin2越界或end1越界程序直接break即可,其实直接写begin2就可以涵盖所有情况,所以我们可以将begin1>n省略。

归并排序的特性总结


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


非比较排序 

非比较排序的思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。 操作步骤:
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

计数排序

计数排序是一种比较新奇的排序思路,它没有两两数之间的比较,而是统计每个数出现的次数,然后进行排序。

这种方法适合于数目比较集中的情况,且整型数据。

时间复杂度:O(N + range) 空间复杂度:O(range)

算法思路以及代码实现

思路:

1.先寻找数组中出现的最大数与最小数。

2.开辟最大数-最小数差值的数组空间大小

3.遍历数组,统计数组中每个数出现的次数放入开辟好的数组中去。

4.遍历新建数组中的内容,每个数出现几次,就在旧数组中打印几次,覆盖掉原数组的内容。

代码实现:

void CountSort(int* a, int n)
{int min = a[0], max = a[0];for (size_t i = 0; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);printf("range:%d\n", range);if (count == NULL){perror("malloc fail");return;}memset(count, 0, sizeof(int) * range);// 统计数据出现次数for (int i = 0; i < n; i++){count[a[i] - min]++;}// 排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

 注意:我们统计的数组不一定从0开始,所以我们在统计出数组中的最小值时一定要在默认在每个下标后加最小值才可以得到原数组中的内容。

计数排序总结

计数排序的特性总结:
1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
2. 时间复杂度:O(MAX(N,范围))
3. 空间复杂度:O(范围)


八大排序总结 

总结:几种常见易错且重要的排序在这里就讲述完了,我们要合理引用,发挥出排序的优点,舍弃其缺点。最后我将这些排序的复杂度以及稳定性进行了总结,我们可以适度观看。 

 


以上就是本次博客全部内容,感谢大家观看!!!

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

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

相关文章

[NewStarCTF 2023 公开赛道] week1

最近没什么正式比赛&#xff0c;都是入门赛&#xff0c;有moectf,newstar,SHCTF,0xGame都是漫长的比赛。一周一堆制。 这周newstar第1周结束了&#xff0c;据说py得很厉害&#xff0c;第2周延期了&#xff0c;什么时候开始还不一定&#xff0c;不过第一周已经结束提交了&#…

林沛满-TCP之在途字节数

本文整理自&#xff1a;《Wireshark网络分析的艺术 第1版》 作者&#xff1a;林沛满 著 出版时间&#xff1a;2016-02 我一直谨记斯蒂芬霍金的金玉良言—每写一道数学公式就会失去一半读者。不过为了深度分析网络包&#xff0c;有时候是不得不计算的&#xff0c;好在小学一年级…

socket简介

套接字&#xff08;Socket&#xff09;实质上就是对网络中不同主机上的应用进程之间进行双向通信的端点的抽象。一个套接字就是网络上进程通信的一端&#xff0c;为应用层进程利网络协议交换数据提供了相应机制。套接字出于承上启下的作用&#xff0c;向上连接应用进程&#xf…

【QT5-程序控制电源-[GPIB-USB-HS]-SCPI协议-上位机-基础样例【2】】

【QT5-程序控制电源-[GPIB-USB-HS]-SCPI协议-上位机-基础样例【2】】 1、前言2、实验环境3、自我总结1、基础了解仪器控制-熟悉仪器2、连接SCPI协议3、了解GPIB-USB-HS4、软件调试-代码编写 4、熟悉协议-SCPI协议5、实验过程-熟悉软件&#xff08;1&#xff09;去官网NI&#x…

【Java项目推荐之黑马头条】自媒体文章实现异步上下架(使用Kafka中间件实现)

自媒体文章上下架功能完成 需求分析 流程说明 接口定义 说明接口路径/api/v1/news/down_or_up请求方式POST参数DTO响应结果ResponseResult DTO Data public class WmNewsDto {private Integer id;/*** 是否上架 0 下架 1 上架*/private Short enable;}ResponseResult 自媒…

使用华为eNSP组网试验⑷-OSPF多区域组网

今天进行了OSPF的多区域组网试验&#xff0c;本来这是个很简单的操作&#xff0c;折腾了好长时间&#xff0c;根本原因只是看了别人写的配置代码&#xff0c;没有真正弄明白里面对应的规则。 一般情况下&#xff0c;很多单位都使用OSPF进行多区域的组网&#xff0c;大体分为1个…

2023-IDEA插件推荐

CamelCase 链接 https://plugins.jetbrains.com/plugin/7160-camelcase https://github.com/netnexus/camelcaseplugin 介绍 提供下划线、驼峰等代码风格的切换。快捷键是⇧ ⌥ U / Shift Alt U GsonFormatPlus 链接 https://plugins.jetbrains.com/plugin/14949-gs…

11.2 基本电路和基本分析方法

一、基本电路 电路类型电路名称特点和典型功能指标参数或功能描述方法基本放大电路共射放大 ∣ A ˙ ∣ |\dot A| ∣A˙∣大&#xff1b;适用于小信号电压放大 A ˙ u \dot A_u A˙u​、 R i R_i Ri​、 R o R_o Ro​、 f L f_L fL​、 f H f_H fH​、 f b w f_{bw} fbw​共集…

Docker 安装 MongoDB

一、什么是MongoDB MongoDB 是一个基于分布式文件存储的数据库。是一个介于关系数据库和非关系数据库之间的产品&#xff0c;是非关系数据库当中功能最丰富&#xff0c;最像关系数据库的。 二、MongoDB的安装 这里使用docker来安装MongoD 1.docker 拉取mysql镜像 docker pu…

unity脚本_生命周期函数 c#

帧&#xff1a;fps 即每秒钟跑的游戏帧数 游戏的本质 是一个死循环 每一次循环处理游戏逻辑就会更新一次画面 之所以能看到画面在动 是因为切换画面的速度达到一定时人眼就认为画面时流畅的 一帧就是执行一次循环 人眼舒适放松时可视帧数 24帧/s 游戏卡顿的原因&#xff1a; …

x64内核实验7-线程

x64内核实验7-线程 TOC 线程是比较重要的内核结构&#xff0c;思考一下其实可以想到线程结构体在64位下的变化应该不会很大最多只是扩充了一些内容&#xff0c;因为从我们之前分析段页时候会发现cpu更新的这些内容大部分不影响xp时候的线程切换机制&#xff0c;下面我们来验证…

初识链表(7.25)

前面我们学习了顺序表&#xff0c;但顺序表其实存在一些问题 1. 中间/头部的插入删除&#xff0c;时间复杂度为O(N) 2. 增容需要申请新空间&#xff0c;拷贝数据&#xff0c;释放旧空间。会有不小的消耗&#xff08;尤其是异地扩容&#xff09;。 3. 增容一般是呈2倍的增长&am…

【Java 进阶篇】深入了解JDBCTemplate:简化Java数据库操作

数据库操作是几乎所有现代应用程序的一部分。从存储和检索数据到管理业务逻辑&#xff0c;数据库操作是不可或缺的。在Java应用程序中&#xff0c;JDBCTemplate是一种强大的工具&#xff0c;可帮助开发人员轻松进行数据库操作。本文将深入探讨JDBCTemplate&#xff0c;了解它的…

【gcc】RtpTransportControllerSend学习笔记 1

本文是大神 https://www.cnblogs.com/ishen 的文章的学习笔记。主要是大神文章: webrtc源码分析(8)-拥塞控制(上)-码率预估 的学习笔记。大神的webrtc源码分析(8)-拥塞控制(上)-码率预估 详尽而具体,堪称神作。因为直接看大神的文章,自己啥也没记住,所以同时跟着看代码。跟…

二蛋赠书四期:《Go编程进阶实战:开发命令行应用、HTTP应用和gRPC应用》

前言 大家好&#xff01;我是二蛋&#xff0c;一个热爱技术、乐于分享的工程师。在过去的几年里&#xff0c;我一直通过各种渠道与大家分享技术知识和经验。我深知&#xff0c;每一位技术人员都对自己的技能提升和职业发展有着热切的期待。因此&#xff0c;我非常感激大家一直…

Java类加载机制

一、java类加载机制 类加载分为三个步骤&#xff1a;加载&#xff0c;连接&#xff0c;初始化&#xff1a; 1. JVM中类的装载是由类加载器&#xff08;ClassLoader&#xff09;和它的子类来实现的&#xff0c;Java中的类加载器是一个重要的Java运行时系统组件&#xff0c;它负…

设备上架与调试步骤项目篇

1.设备又哪些常见的调试方法&#xff1f; 2.设备开箱 -> 使用的步骤是什么&#xff1f; 3.开局新设备都要设置哪些功能&#xff1f; -- 工程师&#xff1a;架构设计 项目实施 故障排查 -- 调试设备&#xff1a; -- 1.WEB界面 - 界面调试 - 内容比较少的 主要项目 …

Zygote Secondary:加速应用启动的未来之路

Zygote Secondary&#xff1a;加速应用启动的未来之路 1. 引言 在现代的移动应用开发中&#xff0c;启动速度和响应性能是用户体验的重要方面。然而&#xff0c;传统的 Android 进程管理方式在启动应用时会出现性能瓶颈&#xff0c;导致启动时间过长和资源占用过多。为了解决…

2023/9/28 -- ARM

【内存读写指令】 int *p0X12345678 *p100;//向内存中写入数据 int a *p;//从内存读取 1.单寄存器内存读写指令 1.1 指令码以及功能 向内存中写&#xff1a; str:向内存中写一个字(4字节)的数据 strh:向内存写半个字&#xff08;2字节&#xff09;的数据 strb:向内存写一个字…

连接虚拟机工具推荐

连接虚拟机工具推荐 连接虚拟机的工具有很多种&#xff0c;以下是一些常用的推荐&#xff1a; PuTTY&#xff1a;这是一个非常常用的SSH和telnet客户端&#xff0c;适用于Windows系统。它允许你在本地机器上通过命令行接口远程登录到虚拟机。 SecureCRT&#xff1a;这是一个支…