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

八大排序算法(2)交换排序-冒泡排序 和 快速排序

快速排序(Quick Sort)冒泡排序(Bubble Sort) 都是常见的交换排序算法,它们的核心思想都是通过交换元素来实现排序。但是,它们的工作原理和性能差异非常大。下面我们来详细对比这两种排序算法:

1. 冒泡排序(Bubble Sort)

工作原理:

冒泡排序的基本思想是通过重复遍历数组,在每一轮中将未排序部分的最大元素“冒泡”到数组的末尾。

在每一轮中,比较相邻的元素,如果它们的顺序错误,就交换它们。这样,经过每一轮遍历,当前未排序部分的最大元素会被放到正确的位置。

这个过程持续进行,直到没有元素需要交换为止,数组被排序好。

时间复杂度:

最优时间复杂度O(n),当数组已经是有序的时,冒泡排序只需要进行一次遍历就可以完成排序。

最坏时间复杂度O(n^2),当数组是逆序的时,每一轮都需要进行大量的交换,导致时间复杂度达到平方级别。

平均时间复杂度O(n^2),由于每次都需要比较和交换,尤其是对大规模数据集时,性能较差。

空间复杂度:

空间复杂度O(1),冒泡排序是原地排序算法,不需要额外的存储空间。

稳定性:

稳定性:冒泡排序是稳定排序算法,相等的元素不会改变相对顺序。

优缺点:

优点:简单易懂,容易实现。

缺点:效率低,特别是对于大规模数据集时,不适用于大数据排序。

2. 快速排序(Quick Sort)

工作原理:

快速排序是一种分治法的排序算法。其基本思想是:选择一个基准元素(pivot),然后将数组中的元素分成两部分:

左边部分所有元素都小于基准元素

右边部分所有元素都大于基准元素

递归地对左右两部分进行排序,直到数组完全有序。

快速排序的核心是通过分区操作将数组分成两部分,每次递归地进行排序。

时间复杂度:

最优时间复杂度O(n log n),每次分区都能均匀地将数组分成两半,递归深度为 log n,每次分区操作的时间为 O(n)

最坏时间复杂度O(n^2),当基准元素选得不好(如每次选到最大或最小元素)时,划分不均匀,导致递归的深度接近 n,此时性能与冒泡排序类似。

平均时间复杂度O(n log n),通常情况下,快速排序的时间复杂度非常好,适用于大规模数据。

空间复杂度:

空间复杂度O(log n),由于递归调用,最多需要 log n 的栈空间。

稳定性:

稳定性:快速排序通常不是稳定排序。因为相等的元素可能会被交换位置,导致它们的相对顺序发生变化。

优缺点:

优点:平均时间复杂度 O(n log n),非常高效,特别适用于大规模数据排序。

缺点:最坏情况下时间复杂度为 O(n^2),而且不是稳定的排序。

快速排序与冒泡排序的对比

特性冒泡排序快速排序
时间复杂度最优:O(n),最坏:O(n^2),平均:O(n^2)最优:O(n log n),最坏:O(n^2),平均:O(n log n)
空间复杂度O(1)O(log n)
稳定性稳定不稳定
实现难度简单,易于理解相对复杂,需要递归和分区操作
适用场景小规模数据,或者数据几乎已经有序时大规模数据,性能优于冒泡排序
优缺点优:实现简单,缺:效率低优:高效,缺:可能会退化为 O(n^2),不稳定

相关文章:

八大排序算法(2)交换排序-冒泡排序 和 快速排序

快速排序(Quick Sort) 和 冒泡排序(Bubble Sort) 都是常见的交换排序算法,它们的核心思想都是通过交换元素来实现排序。但是,它们的工作原理和性能差异非常大。下面我们来详细对比这两种排序算法&#xff1…...

Python的那些事第二十三篇:Express(Node.js)与 Python:一场跨语言的浪漫邂逅

摘要 在当今的编程世界里,Node.js 和 Python 像是两个性格迥异的超级英雄,一个以速度和灵活性著称,另一个则以强大和优雅闻名。本文将探讨如何通过 Express 框架将 Node.js 和 Python 结合起来,打造出一个高效、有趣的 Web 应用。我们将通过一系列幽默风趣的实例和表格,展…...

STM32MP157A单片机移植Linux驱动

在stm32mp157a单片机移植Linux操作系统,并移植内核驱动,在应用程序中使用3个线程,分别实现控制单片机上3个led流水灯的功能、蜂鸣器控制的功能、风扇控制的功能。 需求整理: 1.驱动程序-->led1.c,led2.c&#xff…...

Qt程序退出相关资源释放问题

目录 问题背景: aboutToQuit 代码举例 closeEvent事件 代码举例 程序退出方式 quit() exit(int returnCode 0) close() 问题背景: 实际项目中程序退出前往往需要及进行一些资源释放、配置保存、线程中断等操作,避免资源浪费&#xff…...

【大学生职业规划大赛备赛PPT资料PDF | 免费共享】

自取链接: 链接:https://pan.quark.cn/s/4fa45515325e 📢 同学,你是不是正在为职业规划大赛发愁? 想展示独特思路却不知如何下手? 想用专业模板却找不到资源? 别担心!我整理了全网…...

win32汇编环境,对话框中使用菜单示例一

;运行效果 ;win32汇编环境,对话框中使用菜单示例一 ;最基本的应用,即添加菜单及点击后响应的操作方法 ;直接抄进RadAsm可编译运行。重要部分加备注。 ;下面为asm文件 ;>>>>>>>>>>>>>>>>>>>>>>&g…...

AutoDock CrankPep or ADCP进行蛋白质多肽对接

需求描述 使用AutoDock CrankPep or ADCP进行蛋白质多肽对接 硬件及系统配置 自用电脑型号如下: 电脑:Precision Tower 7810 (Dell Inc.) CPU : Intel Xeon CPU E5-2686 v4 2.30GHz GPU: NVIDIA GeForce GTX 1070 Linux版本&a…...

高压直流熔断器研究

1.1 定义与作用 高压直流熔断器是一种用于直流电路的过电流保护装置,其主要作用是在电路中检测到过载电流或短路电流时,迅速切断电路,以防止电力设备受损或发生火灾等事故。根据 ISO-8820 和 QC/T420-2004 等标准的定义,熔断器是…...

微信小程序(uni)+蓝牙连接+Xprint打印机实现打印功能

1.蓝牙列表实现&#xff0c;蓝牙设备展示&#xff0c;蓝牙连接 <template><view class"container"><view class"container_top"><view class"l">设备名称</view><view class"r">{{state.phoneNam…...

使用 Docker 部署 Flask 应用

使用 Docker 部署 Flask 应用 一、引言 在现代软件开发中,应用的部署和环境管理是至关重要的环节。传统的部署方式常常会遇到 “在我机器上能运行,在你机器上不行” 的问题,而 Docker 的出现很好地解决了这个痛点。Docker 是一个用于开发、部署和运行应用程序的开放平台,…...

深入浅出GraphQL:现代API设计的未来

文章目录 一、引言二、什么是GraphQL&#xff1f;三、GraphQL的优势3.1 精确获取数据3.2 强类型系统3.3 单一端点3.4 实时数据 四、实际应用4.1 定义Schema4.2 实现解析器4.3 启动GraphQL服务器 五、结论 一、引言 在当今的 Web 开发中&#xff0c;API&#xff08;应用程序编程…...

深入理解Zookeeper:分布式系统的协调者

引言 在现代分布式系统中&#xff0c;协调和管理多个节点之间的状态和行为是一个复杂且关键的任务。Zookeeper作为一个分布式协调服务&#xff0c;为开发者提供了一种高效、可靠的方式来处理分布式系统中的一致性问题。本文将介绍Zookeeper的基本概念、使用场景以及如何通过示…...

python绘图之回归拟合图

回归拟合图在数据分析中具有重要作用&#xff0c;它不仅可以帮助我们理解变量之间的关系&#xff0c;还可以评估模型的拟合效果、进行预测和推断、发现异常值&#xff0c;以及用于模型比较和结果展示。 import pandas as pd import seaborn as sns import matplotlib.pyplot as…...

C语言学习笔记(第二部份)

说明&#xff1a;由于所有内容放在一个md文件中会非常卡顿&#xff0c;本文件将接续C.md文件的第二部分 结构体 结构是一些值的集合&#xff0c;这些值称为成员变量。结构的每个成员可以是不同类型的变量。 结构体的成员可以是标量&#xff0c;数组&#xff0c;指针&#xff0c…...

jQuery UI CSS 框架 API

jQuery UI CSS 框架 API 概述 jQuery UI 是一个基于 jQuery 的用户界面和交互库,它提供了一套丰富的交互组件和视觉效果,旨在帮助开发者快速构建具有吸引力和互动性的网页应用。jQuery UI CSS 框架 API 是 jQuery UI 的一部分,它允许开发者通过简单的 CSS 类来控制 UI 组件…...

Redis7——基础篇(六)

前言&#xff1a;此篇文章系本人学习过程中记录下来的笔记&#xff0c;里面难免会有不少欠缺的地方&#xff0c;诚心期待大家多多给予指教。 基础篇&#xff1a; Redis&#xff08;一&#xff09;Redis&#xff08;二&#xff09;Redis&#xff08;三&#xff09;Redis&#x…...

Windows网络安全基础

随着互联网的发展和普及&#xff0c;Windows网络安全问题愈发严重。在本文中&#xff0c;我们将会介绍Windows网络安全的基本概念&#xff0c;包括网络攻击类型、网络安全威胁、网络安全防御措施等等&#xff0c;帮助初学者更好地了解Windows网络安全。 一、网络攻击类型 网络…...

spring boot知识点4

1.如何监视所有spring boot微服务 安装actuator插件&#xff0c;然后通过接口查询 /actuator/health 2.spring boot项目性能如何优化 a.优化启动时间&#xff0c;去除重复的依赖 b.JVM优化&#xff08;java虚拟机优化&#xff09;&#xff0c;限制堆的最小最大值 c.数据库…...

【大模型系列篇】DeepSeek-R1如何通过强化学习有效提升大型语言模型的推理能力?

如何通过强化学习&#xff08;RL&#xff09;有效提升大型语言模型&#xff08;LLM&#xff09;的推理能力&#xff1f; 《DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning》由DeepSeek-AI团队撰写&#xff0c;主要介绍了他们开发的第一代…...

主表增一个子表批量新增

1、在新增接口里&#xff0c;先随机生成编码&#xff0c;生成RedisLock&#xff0c;逻辑校验&#xff0c;Dto转bean&#xff0c;新增主表&#xff0c;获取主表的ID&#xff0c;新增子表&#xff0c;最后释放锁 2、在修改接口里&#xff0c;获取主表ID&#xff0c;先修改主表&am…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...