当前位置: 首页 > news >正文

【算法】常用排序算法(插入排序、希尔排序、堆排序、选择排序、冒泡排序、快速排序、归并排序、计数排序)超详细

        排序算法是数据结构相关知识中非常重要的一节,相信很多小伙伴对这部分知识一知半解。那么接下来,小编就要带领大家一起来进行对排序算法的深入剖析学习,希望本篇文章能够使你有所收获!

一.常见的排序算法

        排序算法有很多种,为了使同学们有一个比较系统的了解,小编找了一张图片,用以加深同学们的理解:

        

那么接下来,我们就对上图所提到的排序算法进行一一细致的学习吧!

二..插入排序

        插入排序,就是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为 止,得到一个新的有序序列 。

        我们平时玩扑克牌,就是运用到了插入排序的思想。

代码展示:

时间复杂度问题:

插入排序最好的时间复杂度是O(N)  (当数组元素顺序时)

最坏时间复杂度是是O(N^2)  (当数组元素逆序时)

三.希尔排序

        只有掌握好插入排序,才会有可能掌握希尔排序。希尔排序是建立在插入排序的基础之上。

希尔排序分为两步:1.预排序(让数组接近有序 注意预排序是多次)

                                 2.插入排序

其中,预排序是将数组分为gap组,每一组中的数是原数组间隔了gap个数而划分的,间隔为gap,亦将数组划分为gap组。

希尔排序的特性总结:

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就 会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

代码展示:

为了方便同学们理解代码,老师做了详细的批注:

时间复杂度问题分析:

希尔排序的复杂度问题分析非常复杂,我们不做过多研究,我们只告诉大家希尔排序的平均时间复杂度:

                                        O(N^1.3)          

四.堆排序

        堆排序相信大家都不陌生,早在堆的实现中,我们就已经涉及到了堆的相关知识,那么我们就一起来温习一下吧!

        堆排序包括两步:

                1.向下调整建堆

                 2.堆排序

代码展示:

堆排序示意图:

(注意:升序建大堆 降序建小堆 本代码建的是大堆  堆排序具有实践意义,堆排序使用堆来选数,效率就高了很多。)

堆排序时间复杂度:

                        O(N*logN)

五.选择排序

每一次从待排序的数据元素中选出最小(或/和 最大)的一个元素,存放在序列的起始位置,直到全部待排序的 数据元素排完 。

代码展示:

时间复杂度:
                O(N^2)

本代码是优化后的选择排序的代码,我们直接同时寻找最小和最大的两个元素,分别放在序列的最左边和最右边。

六.冒泡排序

        冒泡排序相信大家都不陌生,那么话不多说,我们直接上代码来展示一下:

这里我们展示的代码是优化版本的冒牌排序(设立了flag 放置有序情况下效率降低)

冒泡排序的时间复杂度:

最坏情况下时间复杂度:O(N^2)

最好情况下时间复杂度:O(N)  (数组顺序)

七.快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:

        任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

(一)递归算法

(1).霍尔版本

代码展示:

(2).挖坑法

代码展示:

(3).前后指针法

代码展示:

快速排序的时间复杂度:
                                O(NlogN)  (每一层的次数N*层数logN)

注意:

以上代码均是优化后的快速排序算法。快速排序算法的优化:

1.三数取中选择keyi值(避免有序情况下效率退化)(O(N*N)

2.小区间递归优化(当要排序个数小于10时,我们可以采用插入排序。其目的是不再进行递归分割,减小递归深度,防止溢出。)

(二)非递归算法

光是掌握快速排序的递归算法是远远不够的,我们还需要掌握它的非递归算法:

我们借助栈实现了快速排序的非递归算法。

八.归并排序

        归并排序,简而言之,我们将其总结为“分而治之”。分,即将待排数组分成一个个有序的序列,治,即排序,将这些有序的序列合并,得到完全有序的数组。

(一)递归算法

相信借助下图你可以对归并排序有一个更深入的理解:

代码展示:

归并排序的时间复杂度分析:

                        O(N*logN)   (每一层的次数N*层数logN)

归并排序的空间复杂度:

                        O(N)   (开辟了一个tmp数组)

 

(二)非递归算法

我们可以借助栈来实现归并排序的非递归算法:

注意:这里要谨防数组边界越界问题。

九.计数排序

计数排序是非比较排序的一种,它的实现原理非常的巧妙。

1.建立count数组,统计元素出现的次数

2.根据元素出现的次数回馈到原数组(排序)

代码展示:

本着减少空间浪费的原则,本代码采用了相对映射的方法。即设立一个range变量。在计数的时候,count的下标写为a[i]-min,在排序的时候,a[j]的值赋值为i+mi。count的下标存储的就是数值。

计数排序适用于数据较为集中且数据为整数的情况。

计数排序的时间复杂度:

                        O(MAX(range,N))

计数排序的空间复杂度:

                        Q(N)   (开辟了一个数组用以计数)

十.排序算法的稳定性分析

稳定性:

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

那么下面这个表格可以帮你快速梳理一下排序算法的相关性质:

今天关于排序算法的讲解就到这里,相信坚持学习到这里的小伙伴一定收获满满!如果有相关问题,欢迎大家私信留言!小编一定竭尽所能为大家指点迷津!我们下次再会!

相关文章:

【算法】常用排序算法(插入排序、希尔排序、堆排序、选择排序、冒泡排序、快速排序、归并排序、计数排序)超详细

排序算法是数据结构相关知识中非常重要的一节,相信很多小伙伴对这部分知识一知半解。那么接下来,小编就要带领大家一起来进行对排序算法的深入剖析学习,希望本篇文章能够使你有所收获! 一.常见的排序算法 排序算法有很多种&#…...

力扣 240.搜素矩阵II

题目描述: 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例 1: 输入:matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9…...

ASUS华硕ROG幻14Air笔记本GA403UI(UI UV UU UJ)工厂模式原厂Windows11系统安装包,带MyASUS in WinRE重置还原

适用型号:GA403UI、GA403UV、GA403UU、GA403UJ 链接:https://pan.baidu.com/s/1tz8PZbYKakfvUoXafQPLIg?pwd1mtc 提取码:1mtc 华硕原装WIN11系统工厂包带有ASUS RECOVERY恢复功能、自带面部识别,声卡,显卡,网卡,蓝牙等所有驱动、出厂主题…...

Spring Boot通过自定义注解和Redis+Lua脚本实现接口限流

😄 19年之后由于某些原因断更了三年,23年重新扬帆起航,推出更多优质博文,希望大家多多支持~ 🌷 古之立大事者,不惟有超世之才,亦必有坚忍不拔之志 🎐 个人CSND主页——Mi…...

硬件工程师的蜗牛成长路

一名合格的硬件工程师,需要掌握的知识有很多,知识点积累不是一蹴而就,而是细水长流,螺旋提升,不急,慢慢来,想掌握的都能掌握,就让时间来见证个人的成长路径。 ---大青山 2024/6/10 …...

简单记录玩4399游戏flash插件问题

一、因谷歌浏览器默认禁止flash插件自动运行,所以玩家在使用谷歌浏览器,访问www.4399.com平台页面或者4399小游戏(flash资源)时,可能会出现加载异常的情况。今天教大家如何开启flash插件 二、下载falsh官方插件 地址:Flash Player官方下载中心-Flash中国官网 三、如果您…...

GNU/Linux - 使用字符设备来操作GPIO

从 4.8 版开始,Linux 内核引入了基于字符设备的新用户空间 API,用于管理和控制 GPIO(通用输入/输出)。这篇文章介绍了新接口的基本原理,并通过一个简单的教程/示例演示了如何使用新 API 控制 GPIO。 教程中使用的硬件是…...

Android13 Settings 左上角箭头图标点击无效

最近在修改A311D2方案固件,系统Settings发现很多bug 最明显的是左上角有个箭头样子的图标,通常认为是返回键,点击之后没有任何效果,目测这个是ActionBar的按键。 SettingsBaseActivity里面有一段这样的代码: // Th…...

WinForms 应用(.NET 8.0)使用ReportViewerCore.WinForms显示打印RDLC报表

在要WinForms 应用(.NET 8.0)中,显示RDLC报表,就要使用ReportViewerCore.WinForms。原来的ReportViewer只能在.NET Framework框架下运行。 1.ReportViewerCore.WinForms 程序包说明 SQL Server Reporting Services ReportViewer…...

【网络安全】【深度学习】【入侵检测】SDN模拟网络入侵攻击并检测,实时检测,深度学习

文章目录 1. 前言2. Mininet 和 Ryu 的区别2.1 Mininet2.2 Ryu2.3 总结 3. 模拟攻击3.1 环境准备3.2 创建 Mininet 网络拓扑3.2 启动 Ryu 控制器3.3 模拟网络攻击3.4 捕获流量 4. 实时异常检测4.1 在 Ryu 控制器中4.2 在 h2 机器上的实验结果4.3 深度学习模型部署上h2机器 帮助…...

【CentOS】手动编译安装make、cmake、gcc、git

摘要 Centos7升级make和gcc版本到最新——CSDN make make 各个版本下载地址 http://ftp.gnu.org/pub/gnu/make 以4.4为例安装: # 下载 wget https://ftp.gnu.org/pub/gnu/make/make-4.4.tar.gz # 解压配置 tar zxf make-4.4.tar.gz cd make-4.4 ./configure --p…...

45.django - 开始建立第一个项目

1.django是什么? Django是一个高级的、免费的、开源的Web应用框架,它由Python编程语言编写而成。Django遵循模型-视图-控制器(MVC)的设计模式,但通常将其称为模型-视图-模板(MVT)架构。它的主要…...

# 梯影传媒T6投影仪刷机方法及一些刷机工具链接

梯影传媒T6投影仪刷机方法及一些刷机工具链接 文章目录 梯影传媒T6投影仪刷机方法及一些刷机工具链接1、安装驱动程序2、备份设备rom【boot、system】3、还原我要刷进设备的rom【system】4、打开开发者模式以便于安装apk5、root设备6、更多好链接: 梯影传媒T6使用的…...

【代码随想录算法训练营第37期 第三十二天 | LeetCode122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II】

代码随想录算法训练营第37期 第三十二天 | LeetCode122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II 一、122.买卖股票的最佳时机II 解题代码C&#xff1a; class Solution { public:int maxProfit(vector<int>& prices) {int result 0;for(int i 1; i &…...

DP:回文串模型

一、回文子串 . - 力扣&#xff08;LeetCode&#xff09; 该题有3种解法 &#xff08;1&#xff09;中心扩展算法&#xff08;在字符串章节有介绍&#xff09;时间复杂度O&#xff08;N^2&#xff09;,空间复杂度O&#xff08;1&#xff09; &#xff08;2&#xff09;马丁车…...

STM32CubeMX软件的安装以及配置

STM32CubeMX软件的配置过程可以详细分为以下几个步骤&#xff0c;以确保您能够顺利地使用该软件进行STM32微控制器的配置和代码生成&#xff1a; 1. 安装前准备 安装JAVA环境&#xff1a;由于STM32CubeMX软件是基于JAVA环境运行的&#xff0c;所以需要先安装Java Runtime Env…...

【适配鸿蒙next】Flutter 新一代混合栈管理框架

前言 据最新消息显示&#xff0c;华为今年下半年将全面转向其自主平台HarmonyOS&#xff0c;放弃Android系统。 报道中提到&#xff0c;下一版HarmonyOS预计将随华为即将推出的Mate 70旗舰系列一起发布。 据悉&#xff0c;HarmonyOS Next 已经扩展到4000个应用程序&#xff0c;…...

车载电子电气架构 --- 车载信息安全

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无利益不试图说服别人,是精神上的节…...

【数据结构(邓俊辉)学习笔记】图04——双连通域分解

文章目录 0. 概述1 关节点与双连通域2 蛮力算法3 可行算法4 实现5 示例6 复杂度 0. 概述 学习下双连通域分解&#xff0c;这里略微有一点点难&#xff0c;这个算是DFS算法的非常非常经典的应用&#xff0c;解决的问题也非常非常有用。 1 关节点与双连通域 连通性很好理解&am…...

UI学习(二)

UI学习&#xff08;二&#xff09; 文章目录 UI学习&#xff08;二&#xff09;布局子视图手动布局自动布局 导航控制器导航控制器基础导航控制器的切换导航栏工具栏 分栏控制器分栏控制器协议部分的内容UITableView基础部分相关的协议函数高级协议与单元格 多界面传值 布局子视…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...