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

排序算法——关于快速排序的详解

目录

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排序过程 &#xff08;1&#xff09;选择基准值 &#xff08;2&#xff09;分割过程&#xff08;Partition&#xff09; &#xff08;3&#xff09;递归排序 &#xff08;4&#xff09;合并过程 2.3具体实例 2.4实现代码 2.5关键要…...

序言:《未来已来》

尊敬的读者&#xff0c; 你是否曾经在面对冗长的报告、繁琐的工作、沉重的生活压力时感到困扰&#xff0c;渴望找到一种方式来提升效率&#xff0c;释放压力&#xff1f;你是否曾经在自我创业的道路上&#xff0c;苦于找不到有效的市场营销方式&#xff0c;寻求突破&#xff1f…...

【Spring实战】22 Spring Actuator 入门

文章目录 1. 定义2. 功能3. 依赖4. 配置5. 常用的应用场景1&#xff09;环境监控2&#xff09;运维管理3&#xff09;性能优化 结论 Spring Actuator 是 Spring 框架的一个模块&#xff0c;为开发人员提供了一套强大的监控和管理功能。本文将深入探讨 Spring Actuator 的定义、…...

JSON安全性

确保JSON处理的安全性是现代Web开发中重要的一环。以下是一些关键的安全实践&#xff0c;用于防止JSON注入攻击以及确保数据在传输过程中的安全性&#xff1a; 1. **验证和清洗输入&#xff1a;** - 在将任何数据写入数据库之前&#xff0c;请确保验证用户输入。对于期望的JSON…...

spring-boot-maven插件repackage(goal)的那些事

前言&#xff1a;在打包Springboot项目成jar包时需要在pom.xml使用spring-boot-maven-plugin来增加Maven功能&#xff0c;在我的上一篇博客<<Maven生命周期和插件的那些事&#xff08;2021版&#xff09;>>中已经介绍过Maven和插件的关系&#xff0c;在此不再赘述&…...

ubuntu的boot分区被删除恢复

在鼓捣黑苹果的时候&#xff0c;误删了ubuntu的boot分区&#xff0c;进系统的时候出现emergency mode&#xff0c;那么现在来讲讲怎么恢复 首先做一个ubuntu的启动盘&#xff0c;然后进入启动盘的系统选择试用 呼出命令行&#xff0c;然后添加一个源 sudo add-apt-repository…...

【userfaultfd 条件竞争】starCTF2019 - hackme

前言 呜呜呜&#xff0c;这题不难&#xff0c;但是差不多一个多月没碰我的女朋友 kernel pwn 了&#xff0c;对我的 root 宝宝也是非常想念&#xff0c;可惜这题没有找到我的 root 宝宝&#xff0c;就偷了她的 flag。 哎有点生疏了&#xff0c;这题没看出来堆溢出&#xff0c…...

深度学习中的自动化标签转换:对数据集所有标签做映射转换

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

c语言-函数指针

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

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的优缺点 优点&#xff1a;渐进式&#xff0c;组件化&#xff0c;轻量级&#xff0c;虚拟dom&#xff0c;响应式&#xff0c;单页面路由&#xff0c;数据与视图分开缺点&#xff1a;单页面不利于seo&#xff0c;不支持IE8以下&#xff0c;首屏加载时间长 2、为什么…...

Scrapy 1.3.0 使用简介

scrapy 1.3.0 python 2.7 创建一个项目&#xff1a; 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 然后就会得到一系列文件&#xff1a; 第一个爬…...

单机+内部备份_全备案例

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

【kettle】pdi/data-integration 打开ktr文件报错“Unable to load step info from XML“

一、报错内容&#xff1a; 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文档&#xff0c;文档还是比较详细&#xff0c;游戏的方方面面都涉及到了 官方手册&#xff1a; http://docs.cocos.com/creator/manual/zh/官方api文档&#xff1a; http://docs.cocos.com/creator/api/zh/官方论坛&#xff1a; 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成员

先看一个代码例子&#xff1a; #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++ 远程数据采集上位机+服务器

一、项目介绍&#xff1a; 远程数据采集与传输 课题要求:编写个基于TCP的网络数据获取与传输的应用程序; 该程序具备以下功能: 1)本地端程序够通过串口与下位机(单片机)进行通信&#xff0c;实现数据采集任务 2)本地端程序能将所获取下位机数据进行保存(如csv文本格式等); 3…...

算法每日一题:保龄球游戏的获胜者

大家好&#xff0c;我是星恒 今天的每一一题是一道简单题目&#xff0c;但是没能秒掉&#xff0c;原因就是题意理解不到位&#xff0c;边界问题没有判断清楚 不过这本来就是一个试错&#xff0c;迭代&#xff0c;积累经验的过程&#xff0c;加油加油&#xff0c;相信做多了&…...

Do you know about domestic CPUs

Do you know about domestic CPUs CPU指令集国产CPU CPU指令集 国产CPU 参考文献 国产CPU之4种架构和6大品牌指令集及架构一文深入了解 CPU 的型号、代际架构与微架构国产GPU芯片厂商有哪些深入GPU硬件架构及运行机制详解服务器GPU架构和基础知识...

软件设计模式 --- 类,对象和工厂模式的引入

Q1&#xff1a;什么是软件设计模式&#xff1f; A&#xff1a;软件设计模式&#xff0c;又称设计模式。它是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性、程序的重用性。综上&…...

LeetCode74二分搜索优化:二维矩阵中的高效查找策略

题目描述 力扣地址 给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true &#xff1b;否则&…...

三极管组成的光控开关电路原理图

什么是光控开关 光控开关/光控时控器采用先进的嵌入式微型计算机控制技术&#xff0c;融光控功能和普通时控器两大功能为一体的多功能高级时控器&#xff08;时控开关&#xff09;&#xff0c;根据节能需要可以将光控探头&#xff08;功能&#xff09;与时控功能同时启用&…...

【PostgreSQL】从零开始:(四十二)系统列

PostgreSQL 中的系统列 PostgreSQL 中的系统列是一组特殊的列&#xff0c;用于存储关于表和视图的元数据信息。这些列是由 PostgreSQL 数据库自动创建和维护的&#xff0c;并且不能直接修改或删除。 每个表都有多个系统列&#xff0c;这些列由系统隐式定义。因此&#xff0c;…...

快速、准确地检测和分类病毒序列分析工具 ViralCC的介绍和详细使用方法, 附带应用脚本

介绍 viralcc是一个基因组病毒分析工具&#xff0c;可以用于快速、准确地检测和分类病毒序列。 github&#xff1a;dyxstat/ViralCC: ViralCC: leveraging metagenomic proximity-ligation to retrieve complete viral genomes (github.com) Instruction of reproducing resul…...

DNs服务学习笔记

DNS&#xff1a;域名系统&#xff08;英文&#xff1a;Domain Name System)是一个域名系统&#xff0c;是万维网上作为域名和IP地址相互映射的一个分布式数据库&#xff0c;能够使用户更方便的访问互联网&#xff0c;而不用去记住能够被机器直接读取的IP数串。类似于生活中的11…...

获取线程池中任务执行数量

获取线程池中任务执行数量 通过线程池进行任务处理&#xff0c;有时我们需要知道线程池中任务的执行状态。通过ThreadPoolExecutor的相关API实时获取线程数量&#xff0c;排队任务数量&#xff0c;执行完成线程数量等信息。 实例 private static ExecutorService es new Thr…...

RK3566 Android 11平台上适配YT8512C 100M PHY

RK3566代码之前适配的1000M IC RTL8211F , 现在需要在之前的基础上修改PHY IC 为裕泰的YT8512C ----------------------------------------------------------------------//将1000M 的配置关掉&#xff0c;改为100M 配置,查看RK3566 资料关于以太网的配置即可知道如何修改 #if…...

docker 部署haproxy cpu占用特别高

在部署mysql 主主高可用时&#xff0c;使用haproxy进行负载&#xff0c;在服务部使用的情况下发现服务器cpu占比高&#xff0c;负载也高&#xff0c;因此急需解决这个问题。 1.解决前现状 1.1 部署配置文件 cat > haproxy.cfg << EOF globalmaxconn 4000nbthrea…...

Oracle导出CSV文件

利用spool spool基本格式&#xff1a; spool 路径文件名 select col1||,||col2||,||col3||,||col4 from tablename; spool off spool常用的设置&#xff1a; set colsep ;    //域输出分隔符 set echo off;    //显示start启动的脚本中的每个sql命令&#xff0c;缺…...

wordpress 培训插件/网站排名优化方法

1. 编写程序&#xff0c;声明一个method方法&#xff0c;在方法中打印一个108 的型矩形&#xff0c; 在main方法中调用该方法。 2. 修改上一个程序&#xff0c;在method方法中&#xff0c;除打印一个108的型矩形外&#xff0c;再 计算该矩形的面积&#xff0c;并将其作为方法返…...

无锡网站推广公司/app制作公司

转载于:https://www.cnblogs.com/nkwy2012/p/7975808.html...

新浪sae安装wordpress/东莞搜索引擎推广

大家在做淘宝的时候&#xff0c;每个小伙伴的店铺都肯定会有新品上架&#xff0c;既然是新品上架&#xff0c;遇到的问题肯定也是非常多的&#xff0c;那么今天我们来讲的是新品上架时如何获得高权重&#xff1f; 第一步&#xff1a;产品上架 一、小伙伴们都知道新的产品上架的…...

wordpress彩色标签云设置方法/网站外链优化方法

Android上面为很多库做了kotlin拓展&#xff0c;但是需要引入为kotlin拓展的库才能使用某些方式&#xff0c;比如以下的方式 private val aViewModel: AViewModel by viewModels()https://developer.android.google.cn/kotlin/ktx/extensions-list...

做网站外包的公司好干嘛/企业网络营销顾问

我们看一个跨库事务一致性的问题&#xff0c;这是一个简单的场景&#xff1a;有新老两个系统&#xff0c;对应新老两套数据库&#xff0c;新数据库采用分库分表的设计&#xff0c;考虑到项目发布之后可能存在风险&#xff0c;采取了新老系统的并行方案。这个系统的业务比较简单…...

wordpress 文章幻灯片/网站建设平台哪家好

看到百威啤酒的客户端主界面的按钮&#xff0c;感觉比较新奇&#xff0c;先看下图片&#xff1a; 注意图中我画的箭头&#xff0c;当时鼠标点击的黑色圈圈的位置&#xff0c;然后按钮出现了按下的效果&#xff08;黄色的描边&#xff09; 刚开始看到这种效果很是好奇&#xff0…...