惊叹数据结构之美,品味排序算法之妙:对四大排序的详细介绍
大家好,这里是小编的博客频道
小编的博客:就爱学编程
很高兴在
CSDN
这个大家庭与大家相识,希望能在这里与大家共同进步,共同收获更好的自己!!!
本文目录
- 正文
- 一、冒泡排序(Bubble Sort)
- 二、选择排序(Selection Sort)
- 三、插入排序(Insertion Sort)
- 四、希尔排序(Shell Sort)
- 快乐的时光总是短暂,咱们下篇博文再见啦!!!不要忘了,给小编点点赞和收藏支持一下,在此非常感谢!!!
那接下来就让我们开始遨游在知识的海洋!
正文
一、冒泡排序(Bubble Sort)
- 原理:通过重复遍历要排序的序列,每次比较相邻的两个元素并交换它们的位置,如果它们的顺序错误(即前一个元素大于后一个元素)。这样,每一轮遍历都会将当前未排序部分中的最大元素移动到末尾。这个过程就像气泡一样逐渐把较大的元素“冒”到数组的顶端,因此得名冒泡排序。
- 过程:
- 第一次遍历时,比较第一个和第二个元素,如果前者大于后者则交换;然后比较第二个和第三个元素,依此类推。这样一轮下来,最大的元素就被移动到了数组的最后一个位置。
- 接着进行第二轮遍历,这次不再考虑已经排好序的最大元素,继续对剩余的元素进行比较和交换。
- 重复上述步骤,直到整个数组有序为止。
代码实现:
void Swap(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//冒泡排序
void BubbleSort(int* a, int n) {for (int i = 0; i < n; i++) {int change = 0;for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {change = 1;Swap(&a[j], &a[j + 1]);}}if (change == 0) break;}
}
- 时间复杂度:平均和最坏情况下为O(n^2),最好情况为O(n)(当序列已经有序时)。
- 稳定性:稳定排序算法,即相等元素的相对位置在排序前后不会改变。
- 适用场景:适用于数据量较小且对效率要求不高的场景,如小型程序中对学生成绩的快速排序。
二、选择排序(Selection Sort)
- 原理:从未排序的部分找到最小(或最大)的元素,将其放到已排序部分的末尾(或开头)。
- 过程:
- 从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置。
- 在剩余的集合中重复上述步骤,直到所有元素都排列完毕。
代码实现:
void Swap(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//选择排序
void SelectSort(int* a, int n) {int left = 0, right = n - 1;while (left < right) {int mini = left, maxi = right;for (int i = left; i <= right; i++) {if (a[i] <= a[mini]) {mini = i;}if (a[i] > a[maxi]) {maxi = i;}}Swap(&a[mini], &a[left]);Swap(&a[maxi], &a[right]);++left;--right;}
- 时间复杂度:无论数据规模如何,其时间复杂度都是O(n^2)。
- 稳定性:不稳定排序算法,因为相同关键字的记录可能会因为最后一步的赋值而更改相对次序。
- 适用场景:适用于数据量较小且对稳定性无要求的场景,如小型库存管理系统中对库存物品价格的排序。
三、插入排序(Insertion Sort)
- 原理:构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
- 过程:
- 将第一个元素视为已排序部分。
- 取下一个元素,与已排序部分的元素从后往前逐一比较,找到合适的位置插入。
- 重复上述步骤,直到所有元素都插入到已排序部分中。
代码实现:
//插入排序-------O(N ^ 2)
void InsertSort(int* a, int n) {for (int i = 1; i < n; i++) {int end = i - 1; //对应有序数字最后一个元素的下标int temp = a[end + 1]; //end的后一个,也就是要插入的元素while (end >= 0) {if (temp < a[end]){a[end + 1] = a[end];--end;}else {break;}}a[end + 1] = temp;}
}
- 时间复杂度:平均和最坏情况下均为O(n^2),但在数据基本有序的情况下,其性能可以接近O(n)。
- 空间复杂度:O(1),因为它是一种原地排序算法,不需要额外的存储空间。
- 稳定性:稳定排序算法。
- 适用场景:适用于数据量较小且基本有序的数据排序场景,如实时数据处理系统中对新数据的快速排序。
四、希尔排序(Shell Sort)
- 原理:是插入排序的一种改进版,也称为缩小增量排序。它先选定一个整数gap作为增量,将待排序文件中的所有记录分成若干组,每组内的记录相距gap个位置。然后对每组内的记录进行直接插入排序。随着排序的进行,逐步减小gap的值,直到gap为1时,对整个序列进行一次最后的插入排序。
- 过程:
- 选择初始增量gap,通常取数组长度的一半。
- 根据当前的gap值,将数组分成若干子序列,对每个子序列进行插入排序。
- 逐步减小gap的值,并重复上述步骤,直到gap为1时进行一次完整的插入排序。
代码实现:
//希尔排序-------O(N ^ 1.3)
void ShellSort(int* a, int n) {int gap = n;while (gap > 1) {gap /= 2;/*for (int i = 0; i < gap; i++) {for (int j = i; j < n - gap; j += gap) {int end = j;int tmp = a[end + gap];while (end >= 0) {if (tmp < a[end]) {a[end + gap] = a[end];end -= gap;}else {break;}}a[end + gap] = tmp;}}*/for (int i = 0; i < n - gap; i++) {int end = i;int tmp = a[end + gap];while (end >= 0) {if (tmp < a[end]) {a[end + gap] = a[end];end -= gap;}else {break;}}a[end + gap] = tmp;}PrintArray(a, n);printf("\n");}
}
- 时间复杂度:平均时间复杂度约为O(n1.3)至O(n2)之间,具体取决于增量的选择和数据的分布情况。但通过优化增量序列,可以显著提高排序效率。
- 空间复杂度:O(1),同样是一种原地排序算法。
- 稳定性:不稳定排序算法。
- 适用场景:适用于中等规模的数据排序,当希望获得比简单排序算法更好的效率时。
综上所述:
- 这四种排序算法各有优缺点和适用场景。在实际应用中,应根据具体需求和数据特点选择合适的排序算法以提高程序执行效率和用户体验。
快乐的时光总是短暂,咱们下篇博文再见啦!!!不要忘了,给小编点点赞和收藏支持一下,在此非常感谢!!!
相关文章:
惊叹数据结构之美,品味排序算法之妙:对四大排序的详细介绍
大家好,这里是小编的博客频道 小编的博客:就爱学编程 很高兴在CSDN这个大家庭与大家相识,希望能在这里与大家共同进步,共同收获更好的自己!!! 本文目录 正文一、冒泡排序(Bubble Sor…...
机器学习——什么是代价函数? 下
“上次课讲了机器学习的模型表示,讲了一个线性模型的例子,那怎样在可能的拟合直线里选择一条最合适的呢?有没有数学的方法让这个直线合适还是不合适变得可以量化呢?这就要说代价函数了。” 本次课前半段内容非常简单,带领我们一起复习初中平面几何的知识,后半段给出了代价…...
Ubuntu本地部署网站
目录 1.介绍 2.安装apache 3.网页升级 1.介绍 网站其实就相当于一个文件夹,用域名访问一个网页,就相当于访问了一台电脑的某一个文件夹,在网页中看见的视频,视频和音乐其实就是文件夹里面的文件。为什么网页看起来不像电脑文件夹…...
hydra破解密码
hydra九头蛇是常用的密码破解工具 1、破解centos ssh密码 hydra -l root -P password.txt ssh://192.168.1.107:2222 hydra -l root -P password.txt -s 2222 192.168.1.107 ssh2、破解ftp hydra -l allen -P e:\aa.txt ftp://127.0.0.1 hydra -l allen -P e:\aa.txt ftp:…...
华为OD机试E卷 --字符串变换最小字符串 --24年OD统一考试(Java JS Python C C++)
文章目录 题目描述输入描述输出描述用例题目解析JS算法源码java算法源码python算法源码c算法源码c算法源码 题目描述 给定一个字符串s,最多只能进行一次变换,返回变换后能得到的最小字符串(按照字典序进行比较)。 变换规则&#…...
用户中心项目教程(二)---umi3的使用出现的错误
目录 1.情况的说明 2.遇到的问题 1)第一个问题-关于npx的使用 2)第二个问题--unsupport问题 3)第三个收获--nodejs安装问题 4)第四个收获---nvm下载问题 5)第五个问题--尚未解决的问题 3.个人总结 1.情况的说明…...
具身智能新突破!Physical Intelligence推出机器人动作tokenizer,训练提速5倍
具身智能,是人工智能(AI)行业的下一个浪潮。如何有效训练 Transformers 模型来控制具身机器人,是当前亟需要解决的难题,尤其是对于更复杂、需要精确和高频控制的精巧技能,现有的视觉-语言-动作(…...
Unity 学习指南与资料分享
Unity学习资料 Unity学习资料 Unity学习资料 Unity 作为一款强大的跨平台游戏开发引擎,在游戏开发及实时 3D 内容创作领域占据着重要地位。它功能丰富、易于上手,支持多平台发布,为开发者提供了广阔的创作空间。下面为你带来全面的 Unity 学…...
react什么时候用箭头函数,什么时候不需要
最近从vue项目转到react,太久没写了。遇到了一些卡住的问题,记录一下。 在 JavaScript 和 React 开发中,箭头函数(Arrow Functions)的使用主要取决于上下文、代码简洁性和特定需求。以下是关于何时使用箭头函数以及何时…...
软考中级复习篇章:数据结构部分的复习
软考中级快速通过篇章:数据结构部分的复习 一、引言 在软考中级的备考过程中,数据结构是极为重要的一个部分。它不仅是计算机科学的基础,也是软考中考查的重点知识领域。扎实掌握数据结构相关内容,对于顺利通过软考中级考试起着…...
【Vim Masterclass 笔记22】S09L40 + L41:同步练习11:Vim 的配置与 vimrc 文件的相关操作(含点评课内容)
文章目录 S09L40 Exercise 11 - Vim Settings and the Vimrc File1 训练目标2 操作指令2.1. 打开 vimrc-sample 文件2.2. 尝试各种选项与设置2.3. 将更改内容保存到 vimrc-sample 文件2.4. 将文件 vimrc-sample 的内容复制到寄存器2.5. 创建专属 vimrc 文件2.6. 对于 Mac、Linu…...
Spring Boot 整合 PageHelper 实现分页功能
在开发 Web 应用时,分页功能几乎是必不可少的。Spring Boot 提供了强大的功能来简化开发,而 PageHelper 则是一个优秀的 MyBatis 分页插件,可以极大地简化分页查询的代码。本文将介绍如何在 Spring Boot 项目中整合 PageHelper,并…...
Redis和MongoDB的区别
前言 在项目选型阶段,MongoDB被选中主要是基于其处理大规模数据集的能力,而当时并未深入探讨其他替代方案。此前,Redis被用于管理少量但访问频繁的热数据。目前,项目采用MongoDB存储百万级数据,预计未来数据量将增长至…...
Java基础(2)
博客:深入理解浮点型数据、计算机视觉信息存储与类型转换 四、浮点型数据 在编程语言中,浮点型数据主要包括float(单精度)和double(双精度)。计算机默认使用double类型存储小数,这会引发一些特…...
D3.js及实例应用
文章目录 D3.jsd3.js 应用实例图标展示点击选择拖拉拽应用 D3.js D3.js是一个功能强大的JavaScript库,除了图标展示,还能实现多种类型的交互效果: 数据可视化交互 动态更新图表:根据用户操作(如点击按钮、选择下拉菜…...
管理权限特权
管理权限 Oracle 用户权限分为两种类型: 系统权限:允许用户在数据库中执行特定的操作。 对象权限:允许用户访问和操作特定的对象。 系统权限 Oracle 数据库中有超过100种不同的系统权限。权限中的 “ANY” 关键字表示用户在任何模式&#x…...
基于海思soc的智能产品开发(视频的后续开发)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 前面我们讨论了camera,也讨论了屏幕驱动,这些都是基础的部分。关键是,我们拿到了这些视频数据之后,…...
为什么相关性不是因果关系?人工智能中的因果推理探秘
目录 一、背景 (一)聚焦当下人工智能 (二)基于关联框架的人工智能 (三)基于因果框架的人工智能 二、因果推理的基本理论 (一)因果推理基本范式:因果模型࿰…...
【QT】已解决:Qt4.11.0无法使用MSVC编译器问题
目录 一、背景 1.本机环境 2.问题描述 3.问题解决前后对比图 二、详细操作 1.下载项目二所需qt环境 2.解决思路 3.安装VS2017 4.安装MSVC调试器 5.打开qtCreator查看编译器 5.编译运行项目二 三、参考 一、背景 1.本机环境 windows11 qtCreator4.11.0 minGW 64位…...
python如何解析word文件格式(.docx)
python如何解析word文件格式(.docx) .docx文件遵从开源的“Office Open XML标准”,这意味着我们能用python的文本操作对它进行操作(实际上PPT和Excel也是)。而且这并不是重复造轮子,因为市面上操作.docx的…...
点云目标检测训练数据预处理---平面拟合与坐标转换(python实现)
在做centerpoint训练之前,需要先对点云数据进行标注,然后制作kittti数据集。不用nuScenes或者waymo数据集的理由也很简单,因为麻烦,没有kitti数据集直观。 kitti数据集的格式如下,可以看到数据集中只有航向角ÿ…...
Debezium日常分享系列之:对于从Oracle数据库进行快照的性能优化
Debezium日常分享系列之:对于从Oracle数据库进行快照的性能优化 源数据库Kafka Connect监控测试结果 源数据库 Oracle 19c,本地,CDB数据库主机的I/O带宽为6 GB/s,由此主机上运行的所有数据库共享临时表空间由42个文件组成&#x…...
logback日志自定义占位符
前言 在大型系统运维中,很大程度上是需要依赖日志的。在java大型web工程中,一般都会使用slf4jlogback这一个组合来实现日志的管理。 logback中很多现成的占位符可以可以直接使用,比如线程号【%t】、时间【%d】、日志等级【%p】,…...
【Red Hat8】:搭建FTP服务器
目录 一、匿名FTP访问 1、新建挂载文件 2、挂载 3、关闭防火墙 4、搭建yum源 5、安装VSFTPD 6、 打开配置文件 7、设置配置文件如下几个参数 8、重启vsftpd服务 9、进入图形化界面配置网络 10、查看IP地址 11、安装ftp服务 12、遇到拒绝连接 13、测试 二、本地…...
华为AI培训-NLP实验
中文分词、命名实体识别、语义词性标注、语句逻辑推理、文本摘要、机器翻译、文本情感分析、内容创作 1 实验介绍 1.1 实验背景 中文分词、命名实体识别、语义词性标注、语句逻辑推理是自然语言处理领域中的重要任务。中文分词是将连续的汉字序列切分成有意义的词语序列…...
goodreads书籍评论爬取NRC Emotion Lexicon分析
文章目录 目标网站数据获取评论情感分析对爬虫、逆向感兴趣的同学可以查看文章,一对一小班教学:https://blog.csdn.net/weixin_35770067/article/details/142514698 目标网站 https://www.goodreads.com/book/show/3656.The_Sea 就是针对一本书进行3000+评论抓取和情感分析…...
【vitePress】基于github快速添加评论功能(giscus)
一.添加评论插件 使用giscus来做vitepress 的评论模块,使用也非常的简单,具体可以参考:giscus 文档,首先安装giscus npm i giscus/vue 二.giscus操作 打开giscus 文档,如下图所示,填入你的 github 用户…...
论文笔记(六十二)Diffusion Reward Learning Rewards via Conditional Video Diffusion
Diffusion Reward Learning Rewards via Conditional Video Diffusion 文章概括摘要1 引言2 相关工作3 前言4 方法4.1 基于扩散模型的专家视频建模4.2 条件熵作为奖励4.3 训练细节 5 实验5.1 实验设置5.2 主要结果5.3 零样本奖励泛化5.4 真实机器人评估5.5 消融研究 6 结论 文章…...
电梯系统的UML文档07
从这个类中得到的类图,构划出了软件的大部分设计。 系统结构视图提供软件和整个系统结构最复杂的也是最优雅的描述。和通常的软件系统相比,在分布式嵌入系统中了解系统组件如何协同工作是非常重要的。毕竟,每个类图仅仅是一个系统的静态设计…...
【Python】综合案例--人生重开模拟器
1. 设置初始属性 在游戏中我们设定四个属性.: 颜值 (face) 体质 (strong) 智力 (iq) 家境 (home)我们约定每个属性的范围为 [1, 10], 并且总和不能超过 20. 如果玩家输入的初始属性不合理, 就提示输入有误, 重新输入. print("-----------------------------------------…...
vue+高德API搭建前端3D交通页面
1. 模板部分 (<template>) <template><div class"content"><div><div id"container"></div></div></div> </template> 功能:定义了组件的HTML结构。分析: div.content 是最…...
2024年博客之星主题创作|猫头虎分享AI技术洞察:2025年AI发展趋势前瞻与展望
2025年AI发展趋势前瞻:猫头虎深度解析未来科技与商业机遇 摘要 2024年,AI技术迎来爆发式增长,AIGC、智能体、AIRPA、AI搜索、推理模型等技术不断突破,AI应用场景持续扩展。2025年,AI将进入全新发展阶段,W…...
算法刷题笔记——图论篇
这里写目录标题 理论基础图的基本概念图的种类度 连通性连通图强连通图连通分量强连通分量 图的构造邻接矩阵邻接表 图的遍历方式 深度优先搜索理论基础dfs 与 bfs 区别dfs 搜索过程深搜三部曲所有可达路径广度优先搜索理论基础广搜的使用场景广搜的过程 岛屿数量孤岛的总面积沉…...
虚幻基础-1:cpu挑选(14600kf)
能帮到你的话,就给个赞吧 😘 文章目录 ue非常吃cpu拉满主频打开项目编写蓝图运行原因 时间长 关于压力测试 本文以14600kf为例,双12购入,7月份产。 ue非常吃cpu 经本人测试,ue是非常吃cpu的。 拉满主频 无论任何时间…...
IP地址:127.0.0.1
概述 首先,我们需要明确 127.0.0.1 地址的含义。在网络中,127.0.0.1 地址称为本地回环地址,是一种特殊的网络地址,用于让单独的计算机进行自我回路测试和通信。这个地址在 IP 协议中被定义为环回地址。 在网络设备中,…...
深度学习 | pytorch + torchvision + python 版本对应及环境安装
Hi,大家好,我是半亩花海。要让一个基于 torch 框架开发的深度学习模型正确运行起来,配置环境是个重要的问题,本文介绍了 pytorch、torchvision、torchaudio 及 python 的对应版本以及环境安装的相关流程。 目录 一、版本对应 二…...
学习ASP.NET Core的身份认证(基于JwtBearer的身份认证6)
重新创建WebApi项目,安装Microsoft.AspNetCore.Authentication.JwtBearer包,将之前JwtBearer测试项目中的初始化函数,jwt配置类、token生成类全部挪到项目中。 重新编写login函数,之前测试Cookie和Session认证时用的函数适合m…...
企业级流程架构设计思路-基于价值链的流程架构
获取更多企业流程资料 纸上得来终觉浅,绝知此事要躬行 一.企业流程分级规则定义 1.流程分类分级的总体原则 2.完整的流程体系需要体现出流程的分类分级 03.通用的流程分级方法 04.流程分级的标准 二.企业流程架构设计原则 1.流程架构设计原则 流程框架是流程体…...
深度学习 DAY2:Transformer(一部分)
前言 Transformer是一种用于自然语言处理(NLP)和其他序列到序列(sequence-to-sequence)任务的深度学习模型架构,它在2017年由Vaswani等人首次提出。Transformer架构引入了自注意力机制(self-attention mech…...
【2025】拥抱未来 砥砺前行
2024是怎样的一年 2024在历史画卷上是波澜壮阔的一年,人工智能的浪潮来临,涌现出无数国产大模型。 22年11月ChatGPT发布,它的出现如同在平静湖面上投下一颗巨石,激起了层层波澜,短短五天用户数就达到了100万࿰…...
精选100+套HTML可视化大屏模板源码素材
大屏数据可视化以大屏为主要展示载体的数据可视化设计。 “大面积、炫酷动效、丰富色彩”,大屏易在观感上给人留下震撼印象,便于营造某些独特氛围、打造仪式感。 原本看不见的数据可视化后,便能调动人的情绪、引发人的共鸣。 使用方法&…...
欧拉(Euler 22.03)安装ProxySQL
下载离线安装包 proxysql-2.0.8-1-centos7.x86_64.rpm 链接: https://pan.baidu.com/s/1R-SJiVUEu24oNnPFlm9wRw 提取码: sa2w离线安装proxysql yum localinstall -y proxysql-2.0.8-1-centos7.x86_64.rpm 启动proxysql并检查状态 systemctl start proxysql 启动proxysql syste…...
Electron实践继续
文章目录 前言一、知识储备前提二、开发工具集(一)代码编辑器之选(二)命令行工具运用(三)Git 与 GitHub 协作利器(四)Node.js 与 npm 核心环境 你的第一个Electron应用程序 前言 上…...
【STM32-学习笔记-11-】RTC实时时钟
文章目录 RTC实时时钟一、RTC简介二、RTC框图三、RTC基本结构四、RTC操作注意事项五、RTC函数六、配置RTCMyRTC.c 七、示例:实时时钟①、main.c②、MyRTC.c③、MyRTC.h RTC实时时钟 一、RTC简介 RTC(Real Time Clock)实时时钟 RTC是一个独立…...
使用ffmpeg提高mp4压缩比,减小文件体积【windows+ffmpeg+batch脚本】
文章目录 关于前情提要FFmpeg是什么使用脚本运行FFmpeg首先,下载ffmpeg.exe然后在视频相同位置写一个bat脚本运行压缩脚本 关于 个人博客,里面偶尔更新,最近比较忙。发一些总结的帖子和思考。 江湖有缘相见🤝。如果读者想和我交…...
PostgreSQL-01-入门篇-简介
文章目录 1. PostgreSQL是什么?2. PostgreSQL 历史 2.1. 伯克利 POSTGRES 项目2.2. Postgres952.3. PostgreSQL来了 3. PostgreSQL vs MySQL4. 安装 4.1 Windows 安装4.2 linux 安装4.3 docker安装 1. PostgreSQL是什么 PostgreSQL 是一个基于加州大学伯克利分校计算机系开…...
虚拟专用网VPN的概念及实现VPN的关键技术
虚拟专用网VPN通过建立在公共网络上的重要通道(1分),实现远程用户、分支机构、业务伙伴等与机构总部网络的安全连接,从而构建针对特定组织机构的专用网络,实现与专用网络类似的功能,可以达到PN安全性的目的,同时成本相对要低很多(…...
电脑风扇声音大怎么办? 原因及解决方法
电脑风扇是电脑的重要组件之一,它的作用是为电脑的各个部件提供冷却,防止电脑过热。然而,有时候我们会发现电脑风扇的声音特别大,不仅影响我们的使用体验,也可能是电脑出现了一些问题。那么,电脑风扇声音大…...
【Pytorch】unsqueeze与expand结合使用
示例代码 mask mask.unsqueeze(1).expand(-1, N, -1, -1)unsqueeze(1) 操作 unsqueeze是一个在指定位置增加维度的方法。在这行代码中,mask.unsqueeze(1)的作用是在mask张量的第二个维度(索引为1的位置)上插入一个新的维度。 例如…...
基于 Spring Boot 和 Vue.js 的全栈购物平台开发实践
在现代 Web 开发中,前后端分离的架构已经成为主流。本文将分享如何使用 Spring Boot 和 Vue.js构建一个全栈购物平台,涵盖从后端 API 开发到前端页面实现的完整流程。 1. 技术栈介绍 后端技术栈 JDK 1.8:稳定且广泛使用的 Java 版本。 Spring…...