数据结构 (36)各种排序方法的综合比较

一、常见排序方法分类

  1. 插入排序类

    • 直接插入排序:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
    • 希尔排序:是插入排序的一种改进版本,先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
  2. 选择排序类

    • 简单选择排序:在未排序序列中找到最小(或最大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(或最大)元素,放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
    • 堆排序:利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质,即子节点的键值或索引总是小于(或者大于)它的父节点。
  3. 交换排序类

    • 冒泡排序:重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的,直到没有再需要交换的元素为止。
    • 快速排序:选择一个基准元素,通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
  4. 归并排序

    原理:采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。
  5. 基数排序

    原理:一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。
  6. 计数排序

    原理:不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

二、综合比较

  1. 时间复杂度

    • 冒泡排序、简单选择排序、直接插入排序:最坏情况下时间复杂度为O(n^2),适用于数据量较小的情况。
    • 希尔排序:时间复杂度依赖于增量序列的选择,但通常优于O(n^2)。
    • 快速排序:平均时间复杂度为O(n log n),但在最坏情况下(如数组已经有序)时间复杂度为O(n^2)。通过优化,如随机选择基准元素,可以降低最坏情况的发生概率。
    • 堆排序、归并排序:时间复杂度稳定为O(n log n),适用于数据量较大的情况。
    • 基数排序、计数排序:时间复杂度为O(n+k),其中k与数据的具体分布有关。基数排序适用于整数排序且数据位数较多的情况;计数排序适用于数据范围较小且为整数的情况。
  2. 空间复杂度

    • 冒泡排序、简单选择排序、直接插入排序:空间复杂度为O(1),即只需要常数级别的额外空间。
    • 希尔排序:空间复杂度为O(1),但实现时可能需要额外的数组来存储增量序列。
    • 快速排序:空间复杂度为O(log n),主要用于递归调用栈的空间开销。通过迭代实现可以降低空间复杂度,但可能增加代码复杂度。
    • 堆排序:空间复杂度为O(1),但需要额外的空间来维护堆结构(通常在原数组上进行操作)。
    • 归并排序:空间复杂度为O(n),需要额外的数组来存储合并后的结果。通过原地归并可以减少空间开销,但实现较为复杂。
    • 基数排序、计数排序:空间复杂度为O(n+k),其中k与数据的具体分布有关。需要额外的数组来存储桶或计数结果。
  3. 稳定性

    • 冒泡排序、直接插入排序、归并排序:稳定排序,即相等元素的相对顺序在排序前后保持不变。
    • 简单选择排序、快速排序、堆排序:不稳定排序,即相等元素的相对顺序可能会发生变化。
    • 希尔排序:不稳定排序,因为分组插入排序可能破坏相等元素的相对顺序。
    • 基数排序:稳定排序,因为每次分配和收集操作都保持相等元素的相对顺序。
    • 计数排序:稳定排序,因为计数和排序过程都保持相等元素的相对顺序。
  4. 适用场景

    • 数据量较小且对稳定性有要求时,可以选择冒泡排序、直接插入排序或归并排序。
    • 数据量较大且对空间复杂度有要求时,可以选择堆排序或快速排序(通过优化降低最坏情况的发生概率)。
    • 数据为整数且位数较多时,可以选择基数排序。
    • 数据范围较小且为整数时,可以选择计数排序。

 结语    

清醒时做事,糊涂时读书

大怒时睡觉,独处时思考

!!!

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

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

相关文章

计算机网络安全 —— 实体鉴别与生成大随机数

一、实体鉴别# ​ 实体鉴别(经常简称为鉴别)就是一方验证另一方身份的技术。一个实体可以是人、客户/服务器进程等。这里仅讨论如何鉴别通信对端 实体的身份,即验证正在通信的对方确实是所认为的通信实体,而不是其他的假冒者。进…

【SpringBug】lombok插件中@Data不能生成get和set方法

一:问题引入 可以看到我们在类UserInfo上写了Data注解,但是在测试文件中生成的反编译target文件Us二Info中没有get和set方法 二:解决方法 1:Spring升级问题(解决了我的问题) 原因是Spring官方进行了升级…

Unity 基于Collider 组件在3D 物体表面放置3D 物体

实现 从鼠标点击的屏幕位置发送射线,以射线监测点击到的物体,根据点击物体的法线向量调整放置物体的位置及朝向。 Ray ray Camera.main.ScreenPointToRay(Input.mousePosition); if (Physics.Raycast(ray, out RaycastHit hit, 100)) {obj.transform.…

宝塔内设置redis后,项目以及RedisDesktopManager客户端连接不上!

项目展现问题: Unable to connect to Redis; nested exception is io.lettuce.core.RedisConnectionException: Unable to connect to xxx.宝塔外链.ip.xxxx:6379 redis客户端连接失败: 1、宝塔中确认redis端口已放行 2、修改redis的配置 bind&#x…

2024 年 11 月区块链游戏研报:牛市加持下的 GameFi 破局之路

2024 年 11 月区块链游戏研报 作者:Stella L (stellafootprint.network) 数据来源:Footprint Analytics 区块链游戏 Research 页面 2024 年 11 月 Web3 游戏行业市场增长显著但大规模采用策略仍在演进。随着比特币创下历史新高并接近 10 万美元里程碑…

[软件工程]十.可靠性工程(reliable engineering)

1.什么是可靠性工程 我们希望软件在给定的时间内,运行的时候不会崩溃或者发生失效,同时能保护我们的数据和个人信息。我们要能够信任我们所使用的软件,这意味着软件必须是可靠的。可靠性(reliability):系统…

学生信息管理系统(简化版)

前端部分&#xff08;vue2&#xff09; &#xff01;&#xff01;前端采用vue2框架&#xff0c;下面只写出必要的代码文件&#xff0c;想要使用需自行先创建vue项目 部分截图 下面是目录结构 下面是public文件夹里面的html文件 <!DOCTYPE html> <html lang"&q…

Facebook广告文案流量秘诀

Facebook 广告文案是制作有效 Facebook 广告的关键方面。它侧重于伴随广告视觉元素的文本内容。今天我们的博客将深入探讨成功的 Facebook 广告文案的秘密&#xff01; 一、广告文案怎么写&#xff1f; 正文&#xff1a;这是帖子的正文&#xff0c;出现在您姓名的正下方。它可…

VBA高级应用30例应用在Excel中的ListObject对象:向表中添加注释

《VBA高级应用30例》&#xff08;版权10178985&#xff09;&#xff0c;是我推出的第十套教程&#xff0c;教程是专门针对高级学员在学习VBA过程中提高路途上的案例展开&#xff0c;这套教程案例与理论结合&#xff0c;紧贴“实战”&#xff0c;并做“战术总结”&#xff0c;以…

create-react-app react19 搭建项目报错

报错截图 此时运行会报错&#xff1a; 解决方法&#xff1a; 1.根据提示安装依赖法 执行npm i web-vitals然后重新允许 2.删除文件法 在index.js中删除对报错文件的引入&#xff0c;删除报错文件

【MySQL 进阶之路】事务并发情况分析

MySQL事务并发控制分析笔记 在数据库系统中&#xff0c;事务并发控制至关重要&#xff0c;能够确保多个事务并发执行时的数据一致性、隔离性和正确性。MySQL通过不同的锁机制控制并发操作&#xff0c;以确保事务的隔离性。以下是对事务A和事务B并发行为的详细分析&#xff0c;…

NanoLog起步笔记-6-StaticLogInfo

nonolog起步笔记-6-StaticLogInfo StaticLogInfo文件名和行号文件名和行号的传入log参数 RuntimeLogger::registerInvocationSitelogid为什么只能被赋一次值 reserveAlloc加入消息头finishAlloc返回 StaticLogInfo 写C语言编译前端时&#xff0c;给我印象深刻的一部分是&#…

不是“我应该做什么”,而是“我想做什么”

1. 识别内心的渴望 首先&#xff0c;我们需要识别自己真正的愿望和激情所在。这可能需要一些时间和自我反思。问自己&#xff1a;在没有任何外界压力的情况下&#xff0c;我真正想做的是什么&#xff1f;是赚钱、生活、旅行、追星&#xff0c;还是其他什么&#xff1f;识别这些…

Java-JMX (官方文档解读)

JMX 简介 JMX&#xff08;Java Management Extensions&#xff09;是Java平台的一个标准管理框架&#xff0c;自Java 1.5版本起成为Java 平台标准版 (Java SE 平台) 的标准组成部分。JMX 技术提供了一种简单、标准的方法来管理资源&#xff08;例如应用程序、设备和服务&#x…

商品期权开户条件是什么?

商品期权开户条件是什么&#xff1f; 商品期权是一种金融衍生品&#xff0c;它赋予期权持有者在特定日期&#xff08;欧式期权&#xff09;或在特定日期之前&#xff08;美式期权&#xff09;&#xff0c;以特定价格&#xff08;行权价格&#xff09;买入或卖出一定数量的某种…

RISC-V IO 虚拟化架构在 X100 芯片上的实现

安全之安全(security)博客目录导读 本篇博客,我们聚焦RISC-V 2024中国峰会上RISC-V虚拟化相关专题中的IOMMU虚拟化在X100芯片上的实现,来自进迭时空郑律老师。 我们先来看下X100的RISC-V芯片和已有的关于处理器内核虚拟化和内存虚拟化相关的支持 关于IOMMU的特性支持,下图红…

Windows 系统没有网络链接常见原因以及解决方案

在使用 Windows 电脑时&#xff0c;有时会遇到电脑显示已连接网络&#xff0c;但却无法访问 Internet 的情况&#xff0c;这可能是由多种原因导致的。以下简鹿办公将详细介绍一些常见原因及对应的解决方案。 一、网络连接问题 原因 路由器故障&#xff1a;路由器长时间运行可…

【Rive】事件回调

1 前言 Android 中可以通过 RiveAnimationView 的 addEventListener 方法添加动画监听器&#xff0c;用于监听状态动画和过渡动画的开始和结束时机&#xff0c;实现动画开始和结束时的事件回调&#xff1b;也可以监听 Rive 事件触发的时机&#xff0c;在事件触发时响应回调。 …

Springboot3整合Redis

书接上篇《Redis 安装篇&#xff08;阿里云服务器&#xff09;_阿里云安装redis-CSDN博客》&#xff0c;安装好Redis后&#xff0c;就需要在springboot项目中使用Redis了。 一、SpringBoot整合Redis 1.添加坐标 <!--redis--> <dependency><groupId>org.sp…

REDMI瞄准游戏赛道,推出小屏平板

近日&#xff0c;REDMI推出了一款8.8英寸的小屏平板&#xff0c;引发市场关注。该平板采用LCD屏幕&#xff0c;搭载天玑9400处理器&#xff0c;定位游戏市场&#xff0c;意在开拓小屏平板的新领域‌。 ‌小屏平板新尝试‌ 这款REDMI平板未追随大屏潮流&#xff0c;而是选择了8…