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

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

一.常见的排序算法

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

        

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

二..插入排序

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

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

代码展示:

时间复杂度问题:

插入排序最好的时间复杂度是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]之前,则称这种排 序算法是稳定的;否则称为不稳定的。

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

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

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

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

相关文章

‘AndroidStudio工具平台’尝试运行‘Android原生项目’

AndroidStudio工具平台 (内嵌Intelli IDEA集成环境) /Users/haijunyan/Library/Android/sdk 配置环境变量: #adb命令,安装APK查看连接设备 platform-tools #emulator命令,通过命令创建模拟器 tools #用NDK框架搭建的项目,用到下面的命令编译 …

【Oracle】Oracle导入导出dmp文件

文章目录 前言一、什么是dmp?二、imp/impdp、exp/expdp对比及示例1.区别2.imp/impdp对比及示例a. impb. impbp 3.exp/expdp对比及示例a. expb.expdp 3.其他事项 三、执行导入导出前置条件1.创建角色并授权2.创建目录映射 前言 在工作中,经常会遇到需要备…

Serif Affinity 2.5 (macOS, Windows) - 专业创意软件

Serif Affinity 2.5 (macOS, Windows) - 专业创意软件 Affinity Designer 2, Affinity Photo 2, Affinity Publisher 2 请访问原文链接:Serif Affinity 2.5 (macOS, Windows) - 专业创意软件,查看最新版。原创作品,转载请保留出处。 作者主…

【数据结构(邓俊辉)学习笔记】图06——最小支撑树

文章目录 0. 概述1. 支撑树2. 最小支撑树3. 歧义性4. 蛮力算法5. Prim算法5.1 割与极短跨越边5.2 贪心迭代5.3 实例5.4 实现5.5 复杂度 0. 概述 学习下最小支撑树和prim算法。 1. 支撑树 最小的连通图是树。 连通图G的某一无环连通子图T若覆盖G中所有的顶点,则称…

【算法小记】深度学习——时间序列数据分析 Time series Data Analysis

在本篇博客中将简单介绍常见的几种循环神经网络和一维卷积神经网络,并使用一些简答的数据进行拟合分析。本文相对适合刚入门的同学,同时也作为自己过去一段时间学习的总结和记录,现在神经网络框架已经非常完善的支持了很多常见和有效的深度学…

Channels无法使用ASGI问题

Django Channels是一个基于Django的扩展, 用于处理WebSockets, 长轮询和触发器事件等实时应用程序. 它允许Django处理异步请求, 并提供了与其他WebSockets库集成的功能.当我们在Django Channels中使用ASGI_APPLICATION设置时, 我们可以指定一个新的ASGI应用程序来处理ASGI请求.…

Linux基础I/O

一&#xff0c;系统文件I/O 写文件: #include <stdio.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <unistd.h> #include <string.h> int main() {umask(0);int fd open("myfile", O_WRO…

Docker高级篇之Docker微服务实战

文章目录 1. 构建一个简单的微服务项目2. 编写Dockerfile发布微服务部署到docker容器 1. 构建一个简单的微服务项目 创建一个SpringBoot项目 创建一个Controller RestController public class OrderController {Value("${server.port")private String port;Reques…

C语言:双链表

一、什么是双链表&#xff1f; 双链表&#xff0c;顾名思义&#xff0c;是一种每个节点都包含两个链接的链表&#xff1a;一个指向下一个节点&#xff0c;另一个指向前一个节点。这种结构使得双链表在遍历、插入和删除操作上都表现出色。与单链表相比&#xff0c;双链表不仅可以…

Rust 实战丨SSE(Server-Sent Events)

&#x1f4cc; SSE&#xff08;Server-Sent Events&#xff09;是一种允许服务器向客户端浏览器推送信息的技术。它是 HTML5 的一部分&#xff0c;专门用于建立一个单向的从服务器到客户端的通信连接。SSE的使用场景非常广泛&#xff0c;包括实时消息推送、实时通知更新等。 S…

C++中的priority_queue和deque以及适配器

C中的priority_queue和deque 一丶 priority_queue1.1 priority_queue的介绍1.2 priority_queue的使用1.3 priority_queue的模拟实现 二丶 deque2.1 deque的简单介绍2.2 deque的缺陷2.3 为什么要选择deque作为stack和queue的迭代器 三丶 容器适配器3.1 什么是适配器3.2 STL标准库…

Effective Java 2 遇到多个构造器参数时要考虑使用构建器

第2个经验法则&#xff1a;用遇到多个构造器参数时要考虑使用构建器&#xff08;consider a builder when faced with many constructor parameters&#xff09; 上一条讨论了静态工厂相对于构造器来说有五大优势。但静态工厂和构造器有个共同的局限性:它 们都不能很好地扩展到…

开源网关Apache APISIX启用JWT身份验证

说明&#xff1a; 本文APISIX的配置参考我之前写的《Ubuntu部署Apache APISIX》 创建最小API 首先&#xff0c;确保你已经安装了.NET 6 SDK。创建文件夹“MinimalApiDemo”&#xff0c;VS Code打开文件夹&#xff0c;打开终端 dotnet new web -o MinimalApiDemo cd Minimal…

【JMeter接口测试工具】第二节.JMeter基本功能介绍(上)【入门篇】

文章目录 前言一、获取所有学院信息接口执行二、线程组的介绍 2.1 并发和顺序执行 2.2 优先和最后执行线程组 2.3 线程组的设置细节三、HTTP请求的介绍四、查看结果树的配置使用总结 前言 一、获取所有学院信息接口执行 我们先针对一条简单的接口进行执行&#…

代码随想录刷题笔记-哈希表篇

文章目录 242 有效的字母异位词(easy)力扣地址题目描述题目实例解题思路代码实现 383 赎金信(easy)力扣地址题目描述题目实例解题思路代码实现 49 字母异位词分组(mid)力扣地址题目描述题目实例解题思路代码实现 438 找到字符串中所有字母异位词(mid)力扣地址题目描述题目实例解…

3038. 相同分数的最大操作数目 I(Rust模拟击败100%Rust用户)

题目 给你一个整数数组 nums &#xff0c;如果 nums 至少 包含 2 个元素&#xff0c;你可以执行以下操作&#xff1a; 选择 nums 中的前两个元素并将它们删除。 一次操作的 分数 是被删除元素的和。 在确保 所有操作分数相同 的前提下&#xff0c;请你求出 最多 能进行多少次…

SpringBoot整合钉钉实现消息推送

前言 钉钉作为一款企业级通讯工具&#xff0c;具有广泛的应用场景&#xff0c;包括但不限于团队协作、任务提醒、工作汇报等。 通过Spring Boot应用程序整合钉钉实现消息推送&#xff0c;我们可以实现以下功能&#xff1a; 实时向指定用户或群组发送消息通知。自定义消息内容…

Python进阶-部署Flask项目(以TensorFlow图像识别项目WSGI方式启动为例)

本文详细介绍了如何通过WSGI方式部署一个基于TensorFlow图像识别的Flask项目。首先简要介绍了Flask框架的基本概念及其特点&#xff0c;其次详细阐述了Flask项目的部署流程&#xff0c;涵盖了服务器环境配置、Flask应用的创建与测试、WSGI服务器的安装与配置等内容。本文旨在帮…

【iOS】——Runtime学习

文章目录 一、Runtime介绍二、Runtime消息传递三、实例对象、类对象、元类对象四、isa_t结构体的具体实现五、cache_t的具体实现六、class_data_bits_t的具体实现七、Runtime消息转发动态方法解析备用接收者完整消息转发 一、Runtime介绍 iOS的Runtime&#xff0c;通常称为Obj…

使用汇编和proteus实现仿真数码管显示电路

proteus介绍&#xff1a; proteus是一个十分便捷的用于电路仿真的软件&#xff0c;可以用于实现电路的设计、仿真、调试等。并且可以在对应的代码编辑区域&#xff0c;使用代码实现电路功能的仿真。 汇编语言介绍&#xff1a; 百度百科介绍如下&#xff1a; 汇编语言是培养…