排序算法——关于快速排序的详解
目录
1.基本思想
2.基本原理
2.1划分思想
2.2排序过程
(1)选择基准值
(2)分割过程(Partition)
(3)递归排序
(4)合并过程
2.3具体实例
2.4实现代码
2.5关键要点
3.性能分析
3.1空间效率
3.2时间效率
3.3稳定性
1.基本思想
快速排序(Quick Sort)是一种常用的排序算法,它采用分治法的思想,通过递归地将数据分解成小于基准值和大于基准值的两部分,然后对这两部分进行排序,最终将它们合并起来。
2.基本原理
2.1划分思想
在待排序表L[l...n]中任取一个元素pivot作为枢轴(或称基准,通常取首元素),通过一趟排序将待排序表划分为独立的两部分L[l...k-1]和L[k+l...n],使得L[l...k-l]中的所有元素小于pivot;L[k+l...n]中的所有元素大于或等于pivot,则pivot放在了其最终位置L(k)上,这个过程称为一次划分。
2.2排序过程
(1)选择基准值
从待排序数组中选择一个元素作为基准值。通常选择第一个元素,但也可以选择随机元素或数组中间的元素。
(2)分割过程(Partition)
将数组按照基准值进行分割,将小于等于基准值的元素放在基准值的左侧,大于基准值的元素放在右侧。同时,基准值所在的位置被确定,这个位置之前的元素都小于等于基准值,之后的元素都大于基准值。这一过程可以使用双指针法来实现。
(3)递归排序
对基准值左侧和右侧的子数组分别进行递归排序。即对左侧子数组和右侧子数组分别重复步骤1和步骤2。
(4)合并过程
递归排序完成后,整个数组已经被拆分成若干有序的子数组,只需简单地将这些子数组合并即可得到最终的有序数组。
2.3具体实例
一趟快速排序的过程是一个交替搜索和交换的过程,下面通过实例来介绍
*来自2024版王道数据结构考研复习指导
设两个指针i和j,初值分别为low和high,取第一个元素49为枢轴赋值到变量pivot。
对算法的最好理解方式是手动地模拟一遍这些算法。
2.4实现代码
void Quicksort(ElemType A[], int low, int high) {if (low < high) {//递归跳出的条件//Partition()就是划分操作,将表A [low…high]划分为满足上述条件的两个子表int pivotpos = Partition(A, low, high);//划分Quicksort(A, low, pivotpos - 1);//依次对两个子表进行递归排序Quicksort(A, pivotpos + 1, high);}
}
int Partition(ElemType A[], int low, int high) {//一趟划分ElemType pivot = A[low]; //将当前表中第一个元素设为枢轴,对表进行划分while (low < high) {//循环跳出条件while (low < high && A[high] >= pivot)--high;A[low] = A[high];//将比枢轴小的元素移动到左端while (low < high && A[low] < pivot)++low;A[high] = A[low];//将比枢轴大的元素移动到右端}A[low] = pivot;//枢轴元素存放到最终位置return low;//返回存放枢轴的最终位置
}
2.5关键要点
(1)基准值的选择:选择待排序数组中的一个元素作为基准值。通常情况下选择第一个元素,但也可以采用其他策略,如随机选择。
(2)分割过程:将数组分割成两个子数组,一个包含小于等于基准值的元素,另一个包含大于基准值的元素。这个过程通常被称为分区(partition)。
(3)递归排序:对分割得到的两个子数组递归地应用快速排序算法。这是分治策略的关键,通过不断递归排序,最终实现整个数组的排序。
(4)合并过程:将排好序的子数组与基准值合并起来,形成最终的有序数组。
(5)终止条件:当子数组的长度为1或0时,不再进行递归,因为长度为1或0的数组被认为是有序的。
(6)不稳定性:快速排序是一种不稳定的排序算法,即相等元素的相对位置可能在排序前后发生变化。
(7)空间复杂度:快速排序是原地排序算法,不需要额外的存储空间,只需要在递归调用时保持一些辅助变量。
(8)平均时间复杂度:快速排序的平均时间复杂度为O(n log n),其中n是数组的长度。最坏情况下为O(n^2),但在实际应用中,快速排序通常表现良好。
3.性能分析
3.1空间效率
由于快速排序是递归的,需要借助一个递归工作栈来保存每层递归调用的必要信息,其容量与递归调用的最大深度一致。最好情况下为O(log2n);最坏情况下,因为要进行n-1次递归调用,所以栈的深度为O(n);平均情况下,栈的深度为O(log2n)。
3.2时间效率
快速排序的运行时间与划分是否对称有关,快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时,这种最大限度的不对称性若发生在每层递归上,即对应于初始排序表基本有序或基本逆序时,就得到最坏情况下的时间复杂度为0(n^2)。
快速排序是所有内部排序算法中平均性能最优的排序算法
3.3稳定性
在划分算法中,若右端区间有两个关键字相同,且均小于基准值的记录,则在交换到左端区间后,它们的相对位置会发生变化,即快速排序是一种不稳定的排序方法。例如,表L={3,2,2},经过一趟排序后L={2,2,3},最终排序序列也是L={2,2,3),显然,2与2的相对次序己发生了变化。
相关文章:

排序算法——关于快速排序的详解
目录 1.基本思想 2.基本原理 2.1划分思想 2.2排序过程 (1)选择基准值 (2)分割过程(Partition) (3)递归排序 (4)合并过程 2.3具体实例 2.4实现代码 2.5关键要…...
序言:《未来已来》
尊敬的读者, 你是否曾经在面对冗长的报告、繁琐的工作、沉重的生活压力时感到困扰,渴望找到一种方式来提升效率,释放压力?你是否曾经在自我创业的道路上,苦于找不到有效的市场营销方式,寻求突破?…...

【Spring实战】22 Spring Actuator 入门
文章目录 1. 定义2. 功能3. 依赖4. 配置5. 常用的应用场景1)环境监控2)运维管理3)性能优化 结论 Spring Actuator 是 Spring 框架的一个模块,为开发人员提供了一套强大的监控和管理功能。本文将深入探讨 Spring Actuator 的定义、…...
JSON安全性
确保JSON处理的安全性是现代Web开发中重要的一环。以下是一些关键的安全实践,用于防止JSON注入攻击以及确保数据在传输过程中的安全性: 1. **验证和清洗输入:** - 在将任何数据写入数据库之前,请确保验证用户输入。对于期望的JSON…...

spring-boot-maven插件repackage(goal)的那些事
前言:在打包Springboot项目成jar包时需要在pom.xml使用spring-boot-maven-plugin来增加Maven功能,在我的上一篇博客<<Maven生命周期和插件的那些事(2021版)>>中已经介绍过Maven和插件的关系,在此不再赘述&…...
ubuntu的boot分区被删除恢复
在鼓捣黑苹果的时候,误删了ubuntu的boot分区,进系统的时候出现emergency mode,那么现在来讲讲怎么恢复 首先做一个ubuntu的启动盘,然后进入启动盘的系统选择试用 呼出命令行,然后添加一个源 sudo add-apt-repository…...

【userfaultfd 条件竞争】starCTF2019 - hackme
前言 呜呜呜,这题不难,但是差不多一个多月没碰我的女朋友 kernel pwn 了,对我的 root 宝宝也是非常想念,可惜这题没有找到我的 root 宝宝,就偷了她的 flag。 哎有点生疏了,这题没看出来堆溢出,…...

深度学习中的自动化标签转换:对数据集所有标签做映射转换
在机器学习中,特别是在涉及图像识别或分类的项目中,标签数据的组织和准确性至关重要。本文探讨了一个旨在高效转换标签数据的 Python 脚本。该脚本在需要更新或更改类标签的场景中特别有用,这是正在进行的机器学习项目中的常见任务。我们将逐…...

c语言-函数指针
目录 前言一、函数指针1.1 函数指针定义1.2 函数指针调用函数1.3 函数指针代码分析 总结 前言 本篇文章介绍c语言中的函数指针以及函数指针的应用。 一、函数指针 函数指针:指向函数的指针。 函数在编译时分配地址。 &函数名 和 函数名代表的意义相同…...

conda
一、安装 推荐清华源 https://mirrors.tuna.tsinghua.edu.cn/anaconda/miniconda/?CN&OD选择版本 Miniconda3-py39_4.12.0-MacOSX-arm64.pkg测试命令 conda help二、更换仓库 配置加速 https://mirrors.tuna.tsinghua.edu.cn/help/anaconda/没有 .condarc 文件则执行…...
【Vue】灵魂拷问
1、说说Vue的优缺点 优点:渐进式,组件化,轻量级,虚拟dom,响应式,单页面路由,数据与视图分开缺点:单页面不利于seo,不支持IE8以下,首屏加载时间长 2、为什么…...
Scrapy 1.3.0 使用简介
scrapy 1.3.0 python 2.7 创建一个项目: Before you startscraping, you will have to set up a new Scrapy project. Enter a directory whereyou’d like to store your code and run: scrapy startproject tutorial 然后就会得到一系列文件: 第一个爬…...

单机+内部备份_全备案例
此场景为单机数据库节点内部备份,方便部署和操作,但备份REPO与数据库实例处于同一个物理主机,冗余度较低。 前期准备 配置ksql免密登录(必须) 在Kingbase数据库运行维护中,经常用到ksql工具登录数据库,本地免密登录…...

【kettle】pdi/data-integration 打开ktr文件报错“Unable to load step info from XML“
一、报错内容: Unable to load step info from XML step nodeorg.pentaho.di.core.exception.KettleXMLException: Unable to load step info from XMLat org.pentaho.commons.launcher.Launcher.main (Launcher.java:92)at java.lang.reflect.Method.invoke (Met…...
cocos creator人开发小游戏免费素材资源
1、首先熟悉官方的手册和api文档,文档还是比较详细,游戏的方方面面都涉及到了 官方手册: http://docs.cocos.com/creator/manual/zh/官方api文档: http://docs.cocos.com/creator/api/zh/官方论坛: https://forum.coco…...
除了sd webui,compfy还有一个sd UI
GitHub - VoltaML/voltaML-fast-stable-diffusion: Beautiful and Easy to use Stable Diffusion WebUI...
c++属于同一个类的不同对象之间可相互访问private和protected成员
先看一个代码例子: #include <stdio.h>class A { private:char* name;void printA_Name() const {printf(name);} public:A(char* name) {this->name name;}void printA_Name(const A& a) {printf(a.name);}void printA_Name2(const A& a) {a.pr…...

QT/C++ 远程数据采集上位机+服务器
一、项目介绍: 远程数据采集与传输 课题要求:编写个基于TCP的网络数据获取与传输的应用程序; 该程序具备以下功能: 1)本地端程序够通过串口与下位机(单片机)进行通信,实现数据采集任务 2)本地端程序能将所获取下位机数据进行保存(如csv文本格式等); 3…...
算法每日一题:保龄球游戏的获胜者
大家好,我是星恒 今天的每一一题是一道简单题目,但是没能秒掉,原因就是题意理解不到位,边界问题没有判断清楚 不过这本来就是一个试错,迭代,积累经验的过程,加油加油,相信做多了&…...
Do you know about domestic CPUs
Do you know about domestic CPUs CPU指令集国产CPU CPU指令集 国产CPU 参考文献 国产CPU之4种架构和6大品牌指令集及架构一文深入了解 CPU 的型号、代际架构与微架构国产GPU芯片厂商有哪些深入GPU硬件架构及运行机制详解服务器GPU架构和基础知识...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...