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

目录

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的相对次序己发生了变化。

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

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

相关文章

软件工程:用例图相关知识和多实例分析

目录 一、用例图相关知识 1. 基本介绍 2. 常用符号 二、用例图实例分析 1. 新闻管理系统 2. 医院病房监护系统 3. 实验上机安排系统 4. 远程网络教学系统 一、用例图相关知识 1. 基本介绍 用例图&#xff08;use case diagram&#xff09;是用户与系统交互的最简表示…

HarmonyOS 组件通用属性之位置设置

本文 我们来说 通用属性中的位置设置 主要是针对组件的对齐方式 布局方向 显示位置 做过WEB开发的 对流式布局应该都不陌生 就是 一行放内容 不够放就换行 我们可以先这样写 Entry Component struct Index {build() {Row() {Column() {Stack(){Text("你好")Text(&…

Springboot整合MQ学习记录

Mq介绍 RabbitMQ是由erlang语言开发&#xff0c;基于AMQP&#xff08;Advanced Message Queue 高级消息队列协议&#xff09;协议实现的消息队列&#xff0c;它是一种应用程序之间的通信方法&#xff0c;消息队列在分布式系统开发中应用非常广泛。支持Windows、Linux/Unix、MA…

<HarmonyOS主题课>1~3课后习题汇总

&#xff1c;HarmonyOS第一课&#xff1e;1~10课后习题汇总 1使用DevEco Studio高效开发 单选题 用哪一种装饰器修饰的组件可作为页面入口组件&#xff1f;&#xff08;B&#xff09; A. ComponentB. EntryC. PreviewD. Builder ArkTS Stage模型支持API Version 9&#xf…

智能座舱的下一个价值“爆点”——让“光”更智能

汽车智能化快速升级&#xff0c;智能座舱作为人机交互的主要窗口&#xff0c;交互模态、用户体验也呈现多维度升级。 例如&#xff0c;今年下半年上市的多款高端智能车型纷纷基于高性能座舱硬件平台&#xff0c;集成了AR-HUD、DMS/OMS等高阶功能&#xff0c;同时结合超大屏/多…

简单介绍Java 的内存泄漏

java最明显的一个优势就是它的内存管理机制。你只需简单创建对象&#xff0c;java的垃圾回收机制负责分配和释放内存。然而情况并不像想像的那么简单&#xff0c;因为在Java应用中经常发生内存泄漏。 本教程演示了什么是内存泄漏&#xff0c;为什么会发生内存泄漏以及如何预防…

SpringMVC通用后台管理系统源码

整体的SSM后台管理框架功能已经初具雏形&#xff0c;前端界面风格采用了结构简单、 性能优良、页面美观大的Layui页面展示框架 数据库支持了SQLserver,只需修改配置文件即可实现数据库之间的转换。 系统工具中加入了定时任务管理和cron生成器&#xff0c;轻松实现系统调度问…

Glide加载不出图片与请求浏览器资源时中文转码问题

报错代码如图&#xff1a;Image load failed: Failed to load resourse 首先确保你的图片 URL 地址是正确的&#xff0c;可以通过在浏览器中直接访问这个 URL 来测试。另外&#xff0c;确保 URL 地址不包含特殊字符或空格&#xff0c;以免影响加载。 然后确定依赖库没有问题&am…

地平面--高速布线

https://baijiahao.baidu.com/s?id1764139038516816855&wfrspider&forpc 概念 回顾传输线&#xff0c;由任意两条有一定长度的导线组成&#xff0c;一条为信号路径&#xff0c;一条为返回路径。基本电路理论告诉我们&#xff0c;信号是由电流传播的&#xff0c;明确的…

目标检测-One Stage-YOLOv2

文章目录 前言一、YOLOv2的网络结构和流程二、YOLOv2的创新点预处理网络结构训练 总结 前言 根据前文目标检测-One Stage-YOLOv1可以看出YOLOv1的主要缺点是&#xff1a; 和Fast-CNN相比&#xff0c;速度快&#xff0c;但精度下降。&#xff08;边框回归不加限制&#xff09;…

高并发如何保证接口的幂等性?

前言 接口幂等性问题&#xff0c;对于开发人员来说&#xff0c;是一个跟语言无关的公共问题。本文分享了一些解决这类问题非常实用的办法&#xff0c;绝大部分内容我在项目中实践过的&#xff0c;给有需要的小伙伴一个参考。 不知道你有没有遇到过这些场景&#xff1a; 有时我…

Docker(八)Python+旧版本chrome+selenium+oss2+fastapi镜像制作

目录 一、背景二、能力三、核心流程图四、制作镜像1.资源清单2.Dockerfile3.制作镜像 五、启动测试 一、背景 近几年我们线下的创业团队已从零到一开发过好几个小程序项目&#xff0c;都是和体育相关。其中生成海报分享图片好像都是不可或缺的功能。之前的项目老板给的时间都比…

如何让CHAT使用python绘制概率密度图像?

问CHAT&#xff1a;用python绘制概率密度图像 CHAT回复&#xff1a;你可以使用Python的matplotlib库和numpy库进行概率密度的绘制。 以下是一个简单的例子&#xff1a; python import numpy as np import matplotlib.pyplot as plt #随机生成1000个正态分布的数 data np.rand…

《微机原理与应用》期末考试题库(附答案解析)

第1章 微型计算机概述 1.微型计算机的硬件系统包括___A _____。 A&#xff0e;控制器、运算器、存储器和输入输出设备 B&#xff0e;控制器、主机、键盘和显示器 C&#xff0e;主机、电源、CPU和输入输出 D&#xff0e;CPU、键盘、显示器和打印机 2.微处…

安装Keras用于影像分割

conda create -n tfkeras2024 python3.9.18 activate tfkeras2024 pip install tensorflow-gpu2.9.0 pip install keras pip install scipy pip install ipykernel ipython python -m ipykernel install --name tfkeras2024 删除环境conda remove -n tfkeras2024 --all

构建高效秒杀系统的设计原理及注意事项

&#x1f604; 19年之后由于某些原因断更了三年&#xff0c;23年重新扬帆起航&#xff0c;推出更多优质博文&#xff0c;希望大家多多支持&#xff5e; &#x1f337; 古之立大事者&#xff0c;不惟有超世之才&#xff0c;亦必有坚忍不拔之志 &#x1f390; 个人CSND主页——Mi…

G4周:CGAN,手势生成

本文为&#x1f517;365天深度学习训练营 中的学习记录博客 原作者&#xff1a;K同学啊|接辅导、项目定制 我的环境&#xff1a; 1.语言&#xff1a;python3.7 2.编译器&#xff1a;pycharm 3.深度学习框架Pytorch 1.8.0cu111 一、CGAN介绍 条件生成对抗网络&#xff08;…

transforms图像增强(一)

一、数据增强 数据增强&#xff08;Data Augmentation&#xff09;是一种常用的数据预处理技术&#xff0c;通过对训练集进行各种变换和扩增操作&#xff0c;可以增加训练数据的多样性和丰富性&#xff0c;从而提高模型的泛化能力。 数据增强的目的是通过对训练集中的图像进行…

安装PyTorch及环境配置(应用于Python上的YOLO)

这个基本都是Bilibili网站里面叫“小手丫子”up的视频教程&#xff0c;此前自己需要装了好几次又卸载了好几次&#xff0c;现在根据视频教学整理出来自己所理解的文档。 注意事项 1.安装的pycharm版本和anaconda版本无要求。 2.运行pycharm尽量以管理员身份运行。 3.Cuda是独…

使用CentOS 7.6搭建HTTP隧道代理服务器

在现代网络环境中&#xff0c;HTTP隧道代理服务器因其灵活性和安全性而受到广泛关注。CentOS 7.6&#xff0c;作为一个稳定且功能强大的Linux发行版&#xff0c;为搭建此类服务器提供了坚实的基础。 首先&#xff0c;我们需要明确HTTP隧道代理的基本原理。HTTP隧道代理允许客户…