数据结构和算法-交换排序中的快速排序（演示过程 算法实现 算法效率 稳定性）

文章目录

  • 总览
  • 快速排序（超级重要）
  • 啥是快速排序
  • 演示过程
  • 算法实现
    • 第一次quicksort函数
    • 第一次partion函数
    • 到第一次quicksort的第一个quicksort
    • 到第二次quicksort的第一个quicksort
    • 到第二次quicksort的第二个quicksort
    • 到第一次quicksort的第二个quicksort
    • 到第一次quicksort的第二个quicksort的partition
    • 到第一次quicksort的第二个quicksort的第一个quicksort
    • 到第一次quicksort的第二个quicksort的第一个quicksort的partition函数
    • 到第一次quicksort的第二个quicksort的第一个quicksort的第一个quicksort函数
    • 到第一次quicksort的第二个quicksort的第一个quicksort的第二个quicksort函数
    • 到第一次quicksort的第二个quicksort的第二个quicksort
    • 第一次quicksort的第二个quicksort执行完
    • 第一个quicksort执行完
  • 算法效率分析
    • 最好的情况
    • 最坏的情况
    • 优化
    • 算法效率小结
  • 稳定性
  • 小结

总览

在这里插入图片描述

快速排序（超级重要）

啥是快速排序

在这里插入图片描述

演示过程

此时选49为枢轴元素，接着low和high往中间移动，并且保证，low左边都是小于枢轴元素，high元素右边都是大于枢轴元素
此时high位置的49大于等于49，high左移
在这里插入图片描述
此时high所指的元素为27小于49，所以将high位置的元素移动到low位置
在这里插入图片描述
移动后，high的位置空出来，此时移动low位置，此时low的位置的元素为27，小于49，low移动在这里插入图片描述
此时low位置的元素依然小于49，low移动
在这里插入图片描述
此时low指向的元素65大于49，移动到high位置
在这里插入图片描述
此时low位置空了，移动high位置，此时high位置的元素大于49，high左移
在这里插入图片描述
此时high位置元素13小于49，13移动到low位置，
在这里插入图片描述
此时high空，移动low，此时13小于49，low右移
在这里插入图片描述
此时97大于49，将97移动到high

在这里插入图片描述
此时移动high，97大于49，high左移
在这里插入图片描述
此时76大于49，high左移
在这里插入图片描述
low和high碰到一起，此时左右元素都扫了一遍了，比49都小的元素都放到low的左边了，比49大的元素都放high的右边，
在这里插入图片描述
然后把枢轴元素放到low和high重合的位置
在这里插入图片描述

接下来对分别对左右两个子表进行刚刚的过程
此时是左子表，high位置元素13小于27，移动到low
在这里插入图片描述
此时移动low，13小于27，low右移，
在这里插入图片描述
此时38大于27，38移到high
在这里插入图片描述
此时移动high，38大于27，high左移
在这里插入图片描述
此时high和low重合，27放入该位置
在这里插入图片描述
此时该子表又划分两个子表，此时两个子表都只有一个元素，此时不需要处理，因为此时low左边元素小于枢轴，high右边元素大于枢轴，又因为此时左右都只有一个元素，所以已经有序
在这里插入图片描述
此时要处理右子表，high所指元素49小于76，49移动到low，
在这里插入图片描述
此时49小于76,low右移动
在这里插入图片描述
此时97大于76，97移动到high
在这里插入图片描述
此时high移动，97大于76，high左移
在这里插入图片描述
65小于76，65移动到low
在这里插入图片描述
low移动，65小于76，low右移，
在这里插入图片描述
low和high碰头，76放入该位置
在这里插入图片描述
此时再次划分为两个子表，对左子表处理
此时65大于49，high左移

在这里插入图片描述
low和high碰头，49放该位置

在这里插入图片描述
此时由于65和97都只有一个元素，所以直接确定位置
最后排序结果
在这里插入图片描述

算法实现

在这里插入图片描述

首先调用QuickSor函数，开始对整个表划分，并调用partition函数，此时划分整个表

第一次quicksort函数

在这里插入图片描述

第一次partion函数

pivot就是枢轴的意思
此时partion函数大循环的条件是low<high，当low=high时将停止循环
此时大循环中还有两个循环，先是high位置开始的循环，然后是low开始的循环
发现49大于要枢轴值
high左移在这里插入图片描述
此时27小于枢轴值
跳出while循环，并将此时的high的值赋值给low位置
在这里插入图片描述
此时跳到下一个while循环，比较low位置的值和枢轴的值，如果low的值小于枢轴的值，此时low往后移动
在这里插入图片描述
此时直到65发现low的值大于枢轴的值，跳出循环
此时移动low位置的值到high位置上去，此时回到大循环，发现low<high，继续下一次大循环，但大循环仍然是在溢依次分表之中
在这里插入图片描述
此时继续开始第一次小循环，到13跳出第一次小循环，并将high位置的值给low位置的值

在这里插入图片描述
此时开始第二次小循环，到97跳出第二次小循环，并将low值给high位置的值，然后进入下次大循环
在这里插入图片描述
此时进入第一次小循环，此时当high移动到与low相同才跳出第一次小循环，此时由于low=high，第二次小循环也会跳出，随后大循环条件不满足了，跳出大循环
在这里插入图片描述
然后将枢轴元素放到low的位置，并return low的值那么就完成了一次划分的工作
此时quicksort函数中pivotpos的值为该次划分的枢轴的位置
在这里插入图片描述

到第一次quicksort的第一个quicksort

此时处理之前划分的左子表，从low到之前返回得到的枢轴的位置
在这里插入图片描述
此时函数执行过程与之前类似，此时partition函数返回27，返回到第二次quicksort函数中
在这里插入图片描述

到第二次quicksort的第一个quicksort

此时的low和high相等，直接跳出if语句
在这里插入图片描述

到第二次quicksort的第二个quicksort

此时low依然等于high，直接跳出if

在这里插入图片描述

到第一次quicksort的第二个quicksort

此时low=3+1=4，high=7
在这里插入图片描述

到第一次quicksort的第二个quicksort的partition

执行过程于之前相同
在这里插入图片描述
结果
在这里插入图片描述

到第一次quicksort的第二个quicksort的第一个quicksort

此时之前的partition返回到pivotpos为6
此时的quicksort处理的low为4，high为6-1=5
在这里插入图片描述

到第一次quicksort的第二个quicksort的第一个quicksort的partition函数

此时结果
在这里插入图片描述

到第一次quicksort的第二个quicksort的第一个quicksort的第一个quicksort函数

此时之前的partition返回的pivotpos为4
则第一个quicksort对呀的low和4，high为4-1=3
此时不满足low<high，跳出if语句
在这里插入图片描述

到第一次quicksort的第二个quicksort的第一个quicksort的第二个quicksort函数

此时low=4+1=5，high=5，不满足low<high，跳出if语句
在这里插入图片描述

到第一次quicksort的第二个quicksort的第二个quicksort

此时low=6+1=7，high=7，同样不满足low<high,会跳出if
在这里插入图片描述

第一次quicksort的第二个quicksort执行完

在这里插入图片描述

第一个quicksort执行完

排序完成
在这里插入图片描述

算法效率分析

函数每次先得到该范围的枢轴的位置，然后再以该枢轴为中级元素分开两个范围，对各个范围进行函数

partion函数需要通过low和high将该范围的数据都遍历一遍，因为终止条件是low=high
在这里插入图片描述
此时空间复杂度为调用过程中调用函数栈最多的时候
在这里插入图片描述
每层quicksort都是上一层quicksort分成的子表处理，每层处理都分成两个子表在这里插入图片描述
递归层数就是二叉树的层数
在这里插入图片描述

最好的情况

在这里插入图片描述

最坏的情况

在这里插入图片描述
此时high需要左移low才行，第一层quicksort处理后，第二层只需对右边部分处理
在这里插入图片描述
此时依然high需要移到low
在这里插入图片描述
第二层处理后，第三层只需对右边部分处理
在这里插入图片描述
按照这样，需要8层quicksort调用
如果是逆序，第一层quicksort后，ow移动到最右边的位置即high位置，第二层都只需要处理左边部分，，之后的处理类似
在这里插入图片描述

优化

即让枢轴的值极可能不要是最大值或最小值
在这里插入图片描述

算法效率小结

实际情况实际复杂度都接近于最好时间复杂度
在这里插入图片描述

稳定性

看这个例子
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
是不稳定的
在这里插入图片描述

小结

下图时间复杂度最好和最坏写反了
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

大漠插件7.2353

大漠插件7.2353

工具名称:大漠插件7.2353 更新时间2023-12-29更新内容/v7.23531. FindPicSim优化,防止有些时候会找不到图2. 增加接口TerminateProcessTree3. 解决AsmCall 模式6在部分WIN11下无法正常生效的BUG/ 工具简介:大漠 综合 插件 (dm.dll)采用vc6.0编写&#xff0c;识别速度超级快&…
阅读更多...
怎样在Anaconda下安装pytorch(conda安装和pip安装)

怎样在Anaconda下安装pytorch(conda安装和pip安装)

前言 文字说明 本文中标红的&#xff0c;代表的是我认为比较重要的。 版本说明 python环境配置&#xff1a;jupyter的base环境下的python是3.10版本。CUDA配置是&#xff1a;CUDA11.6。目前pytorch官网提示支持的版本是3.7-3.9 本文主要用来记录自己在安装pytorch中出现的问…
阅读更多...
【软件测试】学习笔记-脚本与数据的解耦 + Page Object模型

【软件测试】学习笔记-脚本与数据的解耦 + Page Object模型

本篇文章介绍GUI测试中两个非常重要的概念&#xff1a;测试脚本和数据的解耦&#xff0c;以及页面对象&#xff08;Page Object&#xff09;模型。 测试脚本和数据的解耦 GUI自动化测试适用的场景&#xff0c;尤其适用于需要回归测试页面功能的场景。如果在测试脚本中硬编码&a…
阅读更多...
开源的RNA-Seq分析软件Trinity的详细介绍和使用方法

开源的RNA-Seq分析软件Trinity的详细介绍和使用方法

介绍 GitHub - trinityrnaseq/trinityrnaseq: Trinity RNA-Seq de novo transcriptome assembly Trinity是一种开源的RNA-Seq分析软件&#xff0c;用于转录组的de novo组装。转录组de novo组装是通过将RNA-Seq数据中的短序列片段&#xff08;reads&#xff09;重新组装成完整的…
阅读更多...
Java8 Stream集合的筛选、归约、分组、聚合讲解

Java8 Stream集合的筛选、归约、分组、聚合讲解

目录 1 Stream概述 2 Stream的创建 3 Stream的使用 3.1 Optional 3.2 案例 3.2.1 遍历/匹配&#xff08;foreach/find/match&#xff09; 3.2.2 筛选&#xff08;filter&#xff09; 3.2.3 聚合&#xff08;max/min/count) 3.2.4 映射(map/flatMap) 3.2.5 归约(reduce…
阅读更多...
仿stackoverflow名片与b站名片实现（HTML、CSS）

仿stackoverflow名片与b站名片实现（HTML、CSS）

目录 前言一、仿stackoverflow名片HTMLCSS 二、仿b站名片HTMLCSS 素材 前言 学习自ACwing - Web应用课 一、仿stackoverflow名片 HTML <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport&…
阅读更多...
【实用技巧】Windows 电脑向iPhone或iPad传输视频方法1：无线传输

【实用技巧】Windows 电脑向iPhone或iPad传输视频方法1：无线传输

一、内容简介 本文介绍如何使用 Windows 电脑向 iPhone 或 iPad 传输视频&#xff0c;以 iPhone 为例&#xff0c;iPad的操作方法类似&#xff0c;本文不作赘述。 二、所需原材料 Windows 电脑&#xff08;桌面或其它文件夹中存有要导入的视频&#xff09;、iPhone 14。 待…
阅读更多...
双向孟德尔随机化 | 基础代谢率与心血管疾病因果关系研究发表医学一区文章...

双向孟德尔随机化 | 基础代谢率与心血管疾病因果关系研究发表医学一区文章...

欢迎报名2024年孟德尔随机化方法高级班课程&#xff01; 郑老师团队开设的孟德尔随机化高级班2024年1月20-21日开课&#xff0c;欢迎报名 2023年12月29日&#xff0c;一篇题为Causal Effects of Basal Metabolic Rate on Cardiovascular Disease: A Bidirectional Mendelian Ra…
阅读更多...
期货日数据维护与使用_日数据维护_主力合约计算逻辑

期货日数据维护与使用_日数据维护_主力合约计算逻辑

目录 主力合约换月规则&#xff08;文化财经&#xff09; 主力合约计算逻辑 数据准备 代码 ​下载 主力合约换月规则&#xff08;文化财经&#xff09; 主力合约计算逻辑 数据准备 本文以沪银为例&#xff0c;将沪银所有日数据文件放入一个文件夹中&#xff0c;文件名命…
阅读更多...
Git删除远程仓库某次提交记录后的所有提交

Git删除远程仓库某次提交记录后的所有提交

1、鼠标右键->git bash here&#xff0c;然后cd切换到代码目录&#xff1b; 2、git log查看提交记录&#xff0c;获取commit id 3、git reset commit id&#xff08;commit id指要保留的最新的提交记录id&#xff09; 4、git push --force&#xff0c;强制push 如果出现…
阅读更多...
TypeScript基础（五）泛型

TypeScript基础（五）泛型

✨ 专栏介绍 TypeScript是一种由微软开发的开源编程语言&#xff0c;它是JavaScript的超集&#xff0c;意味着任何有效的JavaScript代码都是有效的TypeScript代码。TypeScript通过添加静态类型和其他特性来增强JavaScript&#xff0c;使其更适合大型项目和团队开发。 在TypeS…
阅读更多...
【机器学习】模型参数优化工具：Optuna使用分步指南（附XGB/LGBM调优代码）

【机器学习】模型参数优化工具：Optuna使用分步指南（附XGB/LGBM调优代码）

常用的调参方式和工具包 常用的调参方式包括网格搜索(Grid Search)、**随机搜索(Random Search)和贝叶斯优化(Bayesian Optimization)**等。 工具包方面&#xff0c;Scikit-learn提供了GridSearchCV和RandomizedSearchCV等用于网格搜索和随机搜索的工具。另外&#xff0c;有一…
阅读更多...
CodeWave智能开发平台--03--目标:应用创建--08联系人管理

CodeWave智能开发平台--03--目标:应用创建--08联系人管理

摘要 本文是网易数帆CodeWave智能开发平台系列的第11篇&#xff0c;主要介绍了基于CodeWave平台文档的新手入门进行学习&#xff0c;实现一个完整的应用&#xff0c;本文主要完成08联系人管理 CodeWave智能开发平台的11次接触 CodeWave参考资源 网易数帆CodeWave开发者社区…
阅读更多...
Linux第21步_取消鼠标中键的复制粘贴功能

Linux第21步_取消鼠标中键的复制粘贴功能

在ubuntu18.04操作系统中&#xff0c;选中文本后&#xff0c;若按下鼠标中键&#xff0c;就可以执行复制粘贴&#xff0c;相当于 CtrlshiftC 后又按了 CtrlshiftV。在Linux系统中&#xff0c;基本上都是这么配置的。在windows系统中&#xff0c;我们习惯用Ctrl-C复制&#xff0…
阅读更多...
intellij idea导入别人项目版本问题解决方案

intellij idea导入别人项目版本问题解决方案

当导入别人的项目太慢,原因是gradle版本不一致,这时android studio自动下载匹配的gradle版本导致长时间下载的问题。原因主要还是&#xff1a;这个下载地址是国外的&#xff0c;需要翻墙&#xff0c;否则会特别慢。 1.一般下载下来的项目都有这些文件夹&#xff0c;在导入项目…
阅读更多...
51单片机介绍

51单片机介绍

1 单片机简介 单片机&#xff0c;英文Micro Controller Unit&#xff0c;简称MCU 内部集成了CPU、RAM、ROM、定时器、中断系统、通讯接口等一系列电脑的常用硬件功能 单片机的任务是信息采集&#xff08;依靠传感器&#xff09;、处理&#xff08;依靠CPU&#xff09;和硬件设…
阅读更多...
uniapp 创建组件

uniapp 创建组件

组件&#xff1a;用于将某个功能的 HTML、CSS、JS 封装到一个文件中&#xff0c;提高代码的复用性和可维护性。 创建组件 一、在根目录中创建 components 文件夹&#xff0c;右键点击新建组件。 二、输入组件名称、选择默认模板、点击创建组件。 三、在组件中正常编写内容即可…
阅读更多...
AcWing 203. 同余方程（扩展欧几里得算法）

AcWing 203. 同余方程（扩展欧几里得算法）

题目链接 203. 同余方程 - AcWing题库高质量的算法题库https://www.acwing.com/problem/content/205/ 来源 《算法竞赛进阶指南》, NOIP2012提高组 题解 本题中的同余方程可以转化为ax by 1的形式&#xff0c;利用扩展欧几里得算法可以求得特解为&#xff0c;则通解为。 代…
阅读更多...
Linux系统使用超详细(九)~用户和组管理

Linux系统使用超详细(九)~用户和组管理

本篇将要梳理有关用户和用户组的学习笔记&#xff0c;内容主要是基本的概念理解和常用命令的使用方法 &#xff01; 目录 一、用户和用户组认识 1.1用户说明 1.1.1查看用户信息 ①id命令&#xff1a; ②whoami 命令 ③cat /etc/passwd 命令 ④getent passwd 命令 ⑤仅显…
阅读更多...
Python轴承故障诊断 (十)基于VMD+CNN-Transfromer的故障分类

Python轴承故障诊断 (十)基于VMD+CNN-Transfromer的故障分类

目录 1 变分模态分解VMD的Python示例 2 轴承故障数据的预处理 2.1 导入数据 2.2 故障VMD分解可视化 3 基于VMDCNN-Transformer的轴承故障诊断分类 3.1 定义VMD-CNN-Transformer分类网络模型 3.2 设置参数&#xff0c;训练模型 3.3 模型评估 代码、数据如下&#xff1a…
阅读更多...
最新文章

Copyright @ 2022~2023