【排序算法对比】快速排序、归并排序、堆排序

排序算法对比:快速排序、归并排序、堆排序

1. 快速排序(Quick Sort)

原理

快速排序采用 分治法(Divide and Conquer),通过选取基准值(pivot),将数组划分为 小于基准值大于基准值 的两个部分,并递归排序。

特点

  • 时间复杂度
    • 最优:O(n log n)
    • 平均:O(n log n)
    • 最差:O(n²)(当选取的 pivot 总是最小或最大值时,会退化成冒泡排序)
  • 空间复杂度O(log n)(递归调用栈)
  • 是否稳定:❌ 不稳定(交换过程中可能改变相同元素的相对位置)
  • 适用场景
    • 适用于大规模数据排序
    • 数据较随机时性能较优
    • 不适用于数据接近有序需要稳定性的场景

2. 归并排序(Merge Sort)

原理

归并排序同样采用 分治法,将数组拆分成 左右两部分,分别排序后再 合并(merge),确保整体有序。

特点

  • 时间复杂度
    • 最佳、最差、平均O(n log n)(即使是最坏情况下也能保持 O(n log n)
  • 空间复杂度O(n)(额外存储归并时的数组)
  • 是否稳定:✅ 稳定(归并过程不会打乱相同元素的相对顺序)
  • 适用场景
    • 适用于数据量大且需要稳定性的情况
    • 适用于链表排序
    • 适用于外部排序(大数据排序),因其可并行处理数据

3. 堆排序(Heap Sort)

原理

堆排序基于 二叉堆(Binary Heap) 数据结构,先将数组构造成 最大堆(Max Heap),然后依次取出堆顶元素(最大值),调整堆结构,最终得到一个有序数组。

特点

  • 时间复杂度
    • 最优、平均、最差:O(n log n)
  • 空间复杂度O(1)(原地排序,不需要额外空间)
  • 是否稳定:❌ 不稳定(堆调整过程中可能改变相同元素的相对位置)
  • 适用场景
    • 适用于 大规模数据排序
    • 适用于 对最坏情况有较好保证 的场景
    • 适用于 优先队列的实现

4. 排序算法对比

排序算法时间复杂度(最优)时间复杂度(平均)时间复杂度(最差)空间复杂度是否稳定适用场景
快速排序O(n log n)O(n log n)O(n²)(退化)O(log n)❌ 不稳定适用于大规模数据,且数据较随机时性能较优
归并排序O(n log n)O(n log n)O(n log n)O(n)✅ 稳定适用于数据量较大且需要稳定性的情况,如链表排序、外部排序
堆排序O(n log n)O(n log n)O(n log n)O(1)❌ 不稳定适用于 原地排序 且对 最坏情况 有较好保证的场景

5. 选择哪种排序?

  • 快速排序:一般情况下最快,适用于数据规模大、数据随机分布的情况。
  • 归并排序:适用于数据量大、稳定性要求高 的情况,如数据库排序。
  • 堆排序:适用于 大规模数据排序,适用于 时间复杂度需要稳定的情况

推荐:

  • 如果数据量大,推荐 快速排序(但注意避免最坏情况)。
  • 如果要求稳定排序,推荐 归并排序
  • 如果空间受限,推荐 堆排序(因为它是 O(1) 空间复杂度的 O(n log n) 排序算法)。

总结:

  1. 快速排序 是平均情况下最快的 O(n log n) 排序,但最坏情况下退化为 O(n²)
  2. 归并排序 始终O(n log n),但需要额外 O(n) 空间,是稳定排序。
  3. 堆排序 适用于大数据且需要 O(1) 额外空间,但不稳定。

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

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

相关文章

Python----数据分析(Pandas二:一维数组Series,Series的创建,Series的属性,Series中元素的索引与访问)

一、一维数组Series Series:一维数组,与Numpy中的一维array类似。它是一种类似于一维数组的对象,是由一组数据(各种 NumPy 数据类型)以及一组与之相关的数据标签(即索引)组成。 仅由一组数据也可产生简单的 Series 对象,用值列表生成 Series …

小程序配置

注册小程序账号和安装开发工具 参考文档:注册小程序账号和安装开发工具https://blog.csdn.net/aystl_gss/article/details/127878658 HBuilder新建项目 填写项目名称,选择UNI-APP,修改路径,点击创建 manifest.json 配置 需要分别…

前端UI编程基础知识:基础三要素(结构→表现→行为)

以下是重新梳理的前端UI编程基础知识体系&#xff0c;结合最新技术趋势与实战要点&#xff0c;以更适合快速掌握的逻辑结构呈现&#xff1a; 一、基础三要素&#xff08;结构→表现→行为&#xff09; 1. HTML5 核心能力 • 语义化标签&#xff1a;<header>, <nav&g…

【eNSP实战】将路由器配置为DHCP服务器

拓图 要求&#xff1a; 为 office100 和 office200 分别配置地址池 AR1接口配置 interface GigabitEthernet0/0/0ip address 192.168.100.1 255.255.255.0 # interface GigabitEthernet0/0/1ip address 192.168.200.1 255.255.255.0 AR1路由器上创建office100地址池 [AR1…

Stable Diffusion 模型具体如何设置参数?

基础参数设置 随机种子&#xff08;seed&#xff09;&#xff1a;设置一个固定的随机种子值&#xff0c;可以确保在相同文本提示下生成相同的图像。如果设置为-1&#xff0c;则每次生成的图像都是随机的。 num_inference_steps&#xff1a;控制模型推理的步数。步数越多&#…

阿里云服务器购买及环境搭建宝塔部署springboot和vue项目

云服务器ECS_云主机_服务器托管_计算-阿里云 一、前言 对于新手或者学生党来说&#xff0c;有时候就想租一个云服务器来玩玩或者练练手&#xff0c;duck不必花那么多钱去租个服务器。这些云服务厂商对学生和新手还是相当友好的。下面将教你如何快速搭建自己的阿里云服务器&…

ABAP语言的动态编程(4) - 综合案例:管理费用明细表

本篇来实现一个综合案例&#xff1a;管理费用明细表。报表在实际项目中&#xff0c;也有一定的参考意义&#xff0c;一方面展示类似的报表&#xff0c;比如管理费用、研发费用等费用的明细&#xff0c;使用业务比较习惯的展示格式&#xff1b;另一方面正好综合运用前面学习的动…

【Python办公】Excel通用匹配工具(双表互匹)

目录 专栏导读1、背景介绍2、库的安装3、核心代码4、完整代码总结专栏导读 🌸 欢迎来到Python办公自动化专栏—Python处理办公问题,解放您的双手 🏳️‍🌈 博客主页:请点击——> 一晌小贪欢的博客主页求关注 👍 该系列文章专栏:请点击——>Python办公自动化专…

2025-03-15 吴恩达机器学习2——线性回归模型

文章目录 1 概述1.1 案例1.2 分析 2 代价函数2.1 代价函数公式2.2 理解代价函数2.3 可视化代价函数 3 梯度下降3.1 实现步骤3.2 理解梯度下降3.3 学习率 4 最佳实践4.1 导入数据4.2 代码实现4.3 可视化 1 概述 ​ 线性回归模型是使用最广泛的学习算法&#xff0c;让我们从一个…

Webpack 前端性能优化全攻略

文章目录 1. 性能优化全景图1.1 优化维度概览1.2 优化效果指标 2. 构建速度优化2.1 缓存策略2.2 并行处理2.3 减少构建范围 3. 输出质量优化3.1 代码分割3.2 Tree Shaking3.3 压缩优化 4. 运行时性能优化4.1 懒加载4.2 预加载4.3 资源优化 5. 高级优化策略5.1 持久化缓存5.2 模…

实验篇| CentOS 7 下 Keepalived + Nginx 实现双机高可用

为什么要做双机高可用&#xff1f;‌ 想象一下&#xff1a;你的网站突然宕机&#xff0c;用户无法访问&#xff0c;订单流失、口碑暴跌…&#x1f4b8; ‌双机热备‌就是解决这个痛点的终极方案&#xff01;两台服务器互为备份&#xff0c;724小时无缝切换&#xff0c;保障业务…

C语言【内存函数】详解加模拟实现

目录&#xff1a; 1. memcpy使用和模拟实现 2. memmove使用和模拟实现 3. memset函数的使用 4. memcmp函数的使用 以上函数均包含在一个头文件<string.h>里面 一、memcpy的使用和模拟实现。 memcpy函数介绍&#xff1a; 函数原型&#xff1a; void * memcpy ( void…

Flutter——Android与Flutter混合开发详细教程

目录 1.创建FlutterModule项目&#xff0c;相当于Android项目里面的module库&#xff1b;2.或者编辑aar引用3.创建Android原生项目3.直接运行跑起来 1.创建FlutterModule项目&#xff0c;相当于Android项目里面的module库&#xff1b; 2.或者编辑aar引用 执行 flutter build a…

Windows根据文件名批量在文件夹里查找文件并复制出来,用WPF实现的详细步骤

项目前言 在日常工作和生活中&#xff0c;我们常常会遇到需要从大量文件中根据文件名批量查找特定文件并复制到指定位置的情况。手动一个个查找和复制文件不仅效率低下&#xff0c;还容易出错。使用 Windows Presentation Foundation (WPF) 可以创建一个用户友好的图形界面应用…

matlab 控制系统GUI设计-PID控制超前滞后控制

1、内容简介 matlab164-控制系统GUI设计-PID控制超前滞后控制 可以交流、咨询、答疑 2、内容说明 略 3、仿真分析 略 4、参考论文 略

【大模型基础_毛玉仁】2.4 基于 Encoder-Decoder 架构的大语言模型

更多内容&#xff1a;XiaoJ的知识星球 目录 2.4 基于 Encoder-Decoder 架构的大语言模型2.4.1 Encoder-Decoder 架构2.4.2 T5 语言模型1&#xff09;T5 模型结构2&#xff09;T5 预训练方式3&#xff09;T5 下游任务 2.4.3 BART 语言模型1&#xff09;BART 模型结构2&#xff0…

AI智能代码疫苗技术,赋能数字化应用内生安全自免疫

“DevSecOps市占率持续领先&#xff0c;IAST探针覆盖率十倍增长&#xff0c;代码疫苗技术已成功帮助上千家行业用户成功抵御‘Log4j2.x’等重大未知漏洞的利用攻击。”子芽在腾讯专访中透露。 这是2021年悬镜安全交出的一张成绩单。悬镜安全是DevSecOps敏捷安全先行者&#xf…

【初级篇】如何使用DeepSeek和Dify构建高效的企业级智能客服系统

在当今数字化时代,企业面临着日益增长的客户服务需求。使用Dify创建智能客服不仅能够提升客户体验,还能显著提高企业的运营效率。关于DIfy的安装部署,大家可以参考之前的文章: 【入门级篇】Dify安装+DeepSeek模型配置保姆级教程_mindie dify deepseek-CSDN博客 AI智能客服…

【机器学习-基础知识】统计和贝叶斯推断

1. 概率论基本概念回顾 1. 概率分布 定义: 概率分布(Probability Distribution)指的是随机变量所有可能取值及其对应概率的集合。它描述了一个随机变量可能取的所有值以及每个值被取到的概率。 对于离散型随机变量,使用概率质量函数来描述。对于连续型随机变量,使用概率…

正点原子[第三期]Arm(iMX6U)Linux移植学习笔记-4 uboot目录分析

前言&#xff1a; 本文是根据哔哩哔哩网站上“Arm(iMX6U)Linux系统移植和根文件系统构键篇”视频的学习笔记&#xff0c;在这里会记录下正点原子 I.MX6ULL 开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了正点原子教学视频和链接中的内容。 引用&#xff1a; …