【数据结构初阶】排序算法(下)冒泡排序与归并排序

文章目录

  • 4. 交换排序
    • 4. 1 冒泡排序
  • 5. 归并排序
  • 6. 非比较排序
    • 6. 1 计数排序
  • 5. 排序性能分析
  • 6. 排序算法复杂度及稳定度分析


4. 交换排序

交换排序基本思想:
所谓交换**,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置**。
交换排序的特点是: 将值较大的数据向序列的尾部移动,值较小的数据向序列的前部移动(也可以反过来)。

常见的交换排序有两个:

  1. 冒泡排序——这是一个除了教学意义外几乎没有任何用处的排序,因为它的时间复杂度太高
  2. 快速排序——实践中最常用的排序,在快排专题中已经介绍过。

4. 1 冒泡排序

冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序,因为每一个元素都可以像小气泡一样,根据自身大小一点一点向数组的一侧移动

冒泡排序的思路就是每一趟通过两两比较逐渐将未排序的数据中的最大值(或最小值)送到它最终应该在的地方,也就是未排序数据的最右边

举例:

int a[] = {3, 5, 9, 7, 2, 1};

通过冒泡排序把它变成降序的。

第一次排序,从最左边开始拿3和5比较,3比5小,交换

int a[] = {5, 3, 9, 7, 2, 1};

接着3又和9比较,3小,再交换

int a[] = {5, 9, 3, 7, 2, 1};

接着3又和7比较,3小,再交换

int a[] = {5, 9, 7, 3, 2, 1};

接着3又和2比较,2小,不交换,但操作的元素从3变成2
2与1比较,1小,不交换,第一轮比较结束。
从原理上看,只有1被放到正确的位置,但是我们可以发现实际上被正确放置的还有2,3,这就会导致在后面几次比较时,可能整个数组都已经有序了。比如下一次遍历之后:

int a[] = {9, 7, 5, 3, 2, 1};

可以看到此时数组已经有序了,但是循环没有停止,这会大大降低冒泡排序的效率
可以在每一轮循环中增加一个变量,当发生交换时,改变它的值,如果在一轮循环后这个变量的值没有发生改变,就说明所有的数据已经有序了,就可以提前停止循环

代码:

void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int jug = 1;	//单次循环的交换检测变量for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);jug = 0;}}if (!jug)jug = 1;	else	//如果jug没被更改,就说明已经有序了break;}
}

时间复杂度:O(N2)
空间复杂度:O(1)

5. 归并排序

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

归并
归并排序的核心就是把数组拆分再一点点地合并,并在每次合并后时合并的这部分有序,直到合并成整个数组

合并时,应该怎么让合并后的部分有序呢?调用快排吗?
当然不需要,要注意合并的这两部分已经有序了,我们可以采用双指针遍历这两个数组,把较小的数放到前面,较大的数放到后面(这里以升序为例,降序则相反)。这样做的时间复杂度是O(N),而快排是O(NlogN)

但这里又出现了一个问题:把较小的数放到哪里?直接放到这个数组里面吗?这显然不行,因为这样可能会覆盖还没排序的数据。
所以我们可以创建一个新的数组,这个数组和排序的数组的大小一致,把排序好的数据放进去,在本次合并完成时,就把数据从新数组里拷贝回来就可以了。

void _MergeSort(int* a, int* tmp, int left, int right)
{//递归的停止条件if (left >= right)return;//递归的思路是反着来的,要先传递下去才能回归,把数组不断二分,最终就可以开始回归,也就是上面说的步骤int mid = (left + right) / 2;_MergeSort(a, tmp, left, mid);_MergeSort(a, tmp, mid + 1, right);//此时开始合并,合并的两个序列已经是有序的了int cur1 = left, end1 = mid;int cur2 = mid + 1, end2 = right;int cur = left;//双指针遍历两个序列,把较小的数放到tmp里,形成升序while (cur1 <= end1 && cur2 <= end2){if (a[cur1] < a[cur2])tmp[cur++] = a[cur1++];elsetmp[cur++] = a[cur2++];}//当上面的循环结束时,有且仅有一个序列还没遍历完,将剩下的放入tmp数组while (cur1 <= end1)tmp[cur++] = a[cur1++];while (cur2 <= end2)tmp[cur++] = a[cur2++];//把tmp里的数据拷贝回来,合并完成for (int i = left; i <= right; i++)a[i] = tmp[i];
}void MergeSort(int* a, int n)
{//创建新数组int* tmp = (int*)malloc(sizeof(int) * n);//开始递归_MergeSort(a, tmp, 0, n - 1);//记得释放动态申请的数组free(tmp);tmp = NULL;
}

时间复杂度:O(NlogN)
空间复杂度:O(N)

6. 非比较排序

6. 1 计数排序

计数排序又称为鸽巢原理,是对哈希直接定址法(不了解这个也没关系)的变形应用。操作步骤

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

比如

int a[]={6, 1, 2, 9, 4, 2, 4, 1, 4};

我们以这个数组为例:

  1. 首先遍历一次数组,找到数据中的最大值max和最小值min创建一个新数组,把新数组中元素都置为0,数组的大小是max
  2. 再来遍历数组,每遍历一个数据,就把新数组中对应下标的数据+1
  3. 当遍历完成后,再遍历新数组,根据新数组中数据的下标推算出对应的数据(因为放入时是根据数据对应的下标放入的,所以可以反推出数据)放入原数组个数就是新数组中存放的数据

jishu
在这个例子中,计数排序表现良好,但是如果换一个例子:
比如:

int a[]={100, 101, 109, 105, 101, 105};

这是我们再根据最大值开空间就会造成极大的浪费
2
我们可以根据范围来开空间,开一个max-min+1大小的新数组,这样每一个数据都可以在-min之后找到对应的新数组下标,还能大幅度节省空间。

void CountSort(int* a, int n)
{//找最大值和最小值int max = a[0];int min = a[0];for (int i = 0; i < n; i++){if (a[i] > max)max = a[i];if (a[i] < min)min = a[i];}//创建数组int N = max - min + 1;int* count = (int*)calloc(N, sizeof(int));if (!count){perror("calloc");exit(1);}//遍历,并在新数组中将数据标记for (int i = 0; i < n; i++){count[a[i] - min]++;}//放回原数组int index = 0;for (int i = 0; i < N; i++){while (count[i]--)a[index++] = i + min;}
}

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

5. 排序性能分析

time.h库中提供了clock()函数,可以在程序中记录运行到这里时的时间,而代码又是顺序执行的,因此只要保存一段代码前后的时间,再相减就可以得到这段代码运行的时间,由此,我们可以做出这样的测试代码:

void TestOP()
{srand((unsigned int)time(0));const int N = 100000;	//可以适当改小这个数值,提高速度int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);//制作相同的数组,避免其他变量for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}
int main()
{TestOP();return 0;
}

注:由于冒泡排序真的很慢,所以程序运行起来后一段时间的卡顿是正常的,可以修改N来减少等待时间,但N不能太小,否则时间太短看不出来差异。
结果
这样就可以很直观地看出来不同排序算法的差异了。

6. 排序算法复杂度及稳定度分析

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的,否则称为不稳定的。

排序办法平均情况最好情况最坏情况辅助空间稳定性
冒泡排序O(n2)O(n)O(n2)O(1)稳定
直接选择排序O(n2)O(n2)O(n2)O(1)不稳定
直接插入排序O(n2)O(n)O(n2)O(1)稳定
希尔排序O(nlogn)~O(n2)O(n1.3)O(n2)O(1)不稳定
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定
快速排序O(nlogn)O(nlogn)O(n2)O(nlogn)~O(n2)不稳定

关于稳定性,没必要死记硬背,需要时在脑海里拿一个比较简单的数组模拟着走一遍这个排序算法的步骤,看看有没有发生不判断两个数相等的交换就可以了,发生了就是不稳定的。
比如堆排序的第一个元素与最后一个元素交换,快排的基准值与prev或是其他变量的交换,这些都会导致这个算法不是稳定的。

谢谢你的阅读,喜欢的话来个点赞收藏评论关注吧!
我会持续更新更多优质文章

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

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

相关文章

归并排序【C语言版-笔记】

目录 一、概念二、排序流程理解三、代码实现3.1主调函数3.2 merge函数 四、性能分析 一、概念 归并是一种算法思想&#xff0c;是将两个或两个一上的有序表合并成一个长度较大的有序表。若一开始无序表中有n个元素&#xff0c;可以把n个元素看作n个有序表&#xff0c;把它们两…

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-27

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-27 目录 文章目录 计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-27目录1. VisScience: An Extensive Benchmark for Evaluating K12 Educational Multi-modal Scientific Reasoning VisScience:…

java中的强软弱虚

在java中对象的引用有强、软、弱、虚四种&#xff0c;这些引用级别的区别主要体现在对象的生命周期、回收时机的不同。 文章目录 准备工作1. 设置内存2. 内存检测 强引用软引用弱引用虚引用 准备工作 1. 设置内存 为方便调试&#xff0c;将内存设置为16MB 依次点击菜单栏的R…

初识算法 · 双指针(1)

目录 前言&#xff1a; 双指针算法 题目一&#xff1a; ​编辑 题目二: 前言&#xff1a; 本文作为算法部分的第一篇文章&#xff0c;自然是少不了简单叭叭两句&#xff0c;对于算法部分&#xff0c;多刷是少不了&#xff0c;我们刷题从暴力过度到算法解法&#xff0c;自…

【Linux】进程概念-2

文章目录 1.环境变量1.1 基本概念1.2 常见环境变量1.3 查看环境变量方法1.4 测试PATH1.5 测试HOME1.6 和环境变量相关的命令1.7 环境变量的组织方式1.8 通过代码如何获取环境变量1.9 通过系统调用获取或设置环境变量1.10 环境变量通常是具有全局属性的1.11 实验 2. 程序地址空间…

安全中心 (SOC) 与 网络运营中心 (NOC)

NOC 和 SOC 之间的区别 网络运营中心 (NOC) 负责维护公司计算机系统的技术基础设施&#xff0c;而安全运营中心 (SOC) 则负责保护组织免受网络威胁。 NOC 专注于防止自然灾害、停电和互联网中断等自然原因造成的网络干扰&#xff0c;而 SOC 则从事监控、管理和保护。 NOC 提…

微信小程序 图片的上传

错误示范 /*从相册中选择文件 微信小程序*/chooseImage(){wx.chooseMedia({count: 9,mediaType: [image],sourceType: [album],success(res) {wx.request({url:"发送的端口占位符",data:res.tempFiles[0].tempFilePath,method:POST,success(res){//请求成功后应该返…

Java在用增强for循环遍历集合时删除元素,抛出java.util.ConcurrentModificationException异常

文章目录 0. 前言1. 问题产生的背景2. Java中增强for循环的底层原理3. 为什么增强for循环不支持在遍历集合时删除元素3.1 问题排查3.2 modCount 变量的来源3.3 expectedModCount 变量的来源3.4 导致modCount变量和expectedModCount不相等的原因3.5 为什么用迭代器遍历元素时删除…

【Nacos架构 原理】内核设计之Nacos通信通道

文章目录 Nacos通信通道 &#xff08;长链接&#xff09;现状背景场景分析配置服务 长链接核心诉求功能性诉求负载均衡连接生命周期 Nacos通信通道 &#xff08;长链接&#xff09; 现状背景 Nacos 1.X 版本 Config/Naming 模块各自的推送通道都是按照自己的设计模型来实现的…

仪器数码管数字识别系统源码分享

仪器数码管数字识别检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Comput…

Glide基本用法及With方法源码解析

文章目录 引入优点 使用步骤导入依赖权限使用 其他用法占位符错误图片后备回调符圆角过渡动画大小调整gif缩略图 使用RequestOptions缓存机制设置缓存策略清理缓存 使用集成库OkHttpVolley with源码解析getRetrieverGlide.getinitializeGlide getRequestManagerRetriever Reque…

【Spine】引入PhotoshopToSpine脚本

引入 右键Photoshop图标&#xff0c;选择属性 打开文件所在位置 找到目录下的\Presets\Scripts文件夹。 找到Spine目录下的\scripts\photoshop文件夹下的PhotoshopToSpine.jsx 复制它&#xff0c;丢到Photoshop刚才找的那个目录下。 使用 打开.psd文件&#xff0c;检查不要…

ubuntu 安装harbor

#安装包 wget https://github.com/goharbor/harbor/releases/download/v2.10.3/harbor-offline-installer-v2.10.3.tgz wget https://github.com/goharbor/harbor/releases/download/v2.10.3/harbor-offline-installer-v2.10.3.tgz.asc#导入签名公钥 gpg --keyserver hkps://ke…

文心一言 VS 讯飞星火 VS chatgpt (359)-- 算法导论24.3 1题

一、在图 24-2上运行Dijkstra算法&#xff0c;第一次使用结点 s s s作为源结点&#xff0c;第二次使用结点 z z z作为源结点。以类似于图 24-6 的风格&#xff0c;给出每次while循环后的 d d d值和 π π π值&#xff0c;以及集合 S S S中的所有结点。如果要写代码&#xff0c…

计算机毕业设计Spark+PyTorch股票预测系统 股票推荐系统 股票可视化 股票数据分析 量化交易系统 股票爬虫 股票K线图 大数据毕业设计 AI

《SparkPyTorch股票预测系统》开题报告 一、研究背景与意义 随着信息技术的飞速发展和全球金融市场的日益繁荣&#xff0c;股票投资已成为广大投资者的重要选择之一。然而&#xff0c;股票市场的复杂性和不确定性使得投资者在做出投资决策时面临巨大的挑战。传统的股票分析方…

Python空间地表联动贝叶斯地震风险计算模型

&#x1f3af;要点 使用贝叶斯推断模型兼顾路径和场地效应&#xff0c;量化传统地理统计曲线拟合技术。使用破裂和场地特征等地质信息以及事件间残差和事件内残差描述数学模型模型使用欧几里得距离度量、角距离度量和土壤差异性度量确定贝叶斯先验分布和后验分布参数&#xff…

CTMO时代下的营销新力量:2+1链动模式AI智能名片商城小程序

在当今这个瞬息万变的商业世界里&#xff0c;营销领域正经历着一场深刻的变革。传统的CMO岗位似乎在时代的浪潮中逐渐失去了它的光芒&#xff0c;CTMO正在悄然取代传统CMO的岗位。 随着营销丛林现象的出现&#xff0c;企业面临着前所未有的挑战。许多企业发现&#xff0c;那些传…

【SQL】未订购的客户

目录 语法 需求 示例 分析 代码 语法 SELECT columns FROM table1 LEFT JOIN table2 ON table1.common_field table2.common_field; LEFT JOIN&#xff08;或称为左外连接&#xff09;是SQL中的一种连接类型&#xff0c;它用于从两个或多个表中基于连接条件返回左表…

动态分配内存

目录 前言 一.malloc,free函数 1.malloc,free函数原型 2.使用方法 3.具体实例 4.注意事项 二.calloc函数 1.calloc函数原型 2.主要特点 3.使用案例 三.realloc函数 1.realloc函数原型 2.使用案例 3.注意事项 前言 动态内存是指在程序运行时&#xff0c;按需分配和…

51单片机学习第六课---B站UP主江协科技

DS18B20 1、基本知识讲解 2、DS18B20读取温度值 main.c #include<regx52.h> #include"delay.h" #include"LCD1602.h" #include"key.h" #include"DS18B20.h"float T; void main () {LCD_Init();LCD_ShowString(1,1,"temp…