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

算法通关村-----快速排序的原理和实现

快速排序介绍

快速排序是一种经典高效的排序方法,是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列,最终将各个小的有序序列合并成一个大的有序序列。

快速排序的实现原理

选择一个基准值,将小于基准值的元素放在基准值左侧,大于基准值的元素放在基准值右侧,基准值放在中间。基准值可以选择待排序列的第一个元素,最后一个元素,中间元素,也可以选择三者的中位数提高快排效率。一轮快速排序后,基准值已经有序,之后对基准值两侧的数据分别进行快排,这是一个递归的过程,最终整个序列有序。整个过程类似于树的前序遍历,每一轮的过程使用双指针,所以快排本质上是树的前序遍历+双指针。

快速排序的具体实现

基准值选择不同,代码实现不同,但本质上都是树的前序遍历+双指针

选择第一个元素作为基准值代码实现

代码实现

public void quickSort(int[] array, int left, int right) {if (left < right) {int pivot = array[left];int i = right + 1;for (int j = right; j > left; j--) {if (array[j] > pivot) {i--;int temp = array[i];array[i] = array[j];array[j] = temp;}}int pivotIndex = i - 1;int temp = array[pivotIndex];array[pivotIndex] = array[left];array[left] = temp;quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex + 1, right);}
}

选择最后一个元素作为基准值代码实现

代码实现

public void quickSort(int[] array, int left, int right) {if (left < right) {int pivot = array[right];int i = left - 1;for (int j = left; j < right; j++) {if (array[j] < pivot) {i++;int temp = array[i];array[i] = array[j];array[j] = temp;}}int pivotIndex = i + 1;int temp = array[pivotIndex];array[pivotIndex] = array[right];array[right] = temp;quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex + 1, right);}
}

选择中值作为基准值代码实现

代码实现

public static void quickSort(int[] array, int start, int end) {if (start >= end) {return;}int left = start;int right = end;int mid = (left + right) / 2;int pivot = array[mid];while (left <= right) {while (left <= right && array[left] < pivot) {left++;}while (left <= right && array[right] > pivot) {right--;}if (left <= right) {int temp = array[left];array[left] = array[right];array[right] = temp;left++;right--;}}quickSort(array, start, right);quickSort(array, left, end);
}

快速排序复杂度分析

时间复杂度:

平均情况下:O(n log n)。在平均情况下,快速排序通常具有优秀的性能。每次分割都将数组分为两部分,每部分的大小约为原数组的一半。因此,在进行 log n 次递归后,每个子数组都会被完全排序,总的时间复杂度是 O(n log n)。

最坏情况下:O(n^2)。最坏情况发生在选择基准值不平衡的情况下,导致每次分割只能减少一个元素。例如,如果数组已经有序或接近有序,且始终选择第一个元素作为基准值,那么就会出现最坏情况。为了避免最坏情况,可以使用随机选择基准值或者三数取中法等策略。

最好情况下:O(n )。最好情况发生在数组有序

空间复杂度

快速排序是一种原地排序算法,不需要额外的内存空间,因此其空间复杂度是 O(1)。

稳定性

快速排序是不稳定的排序算法,即相等元素的相对顺序可能在排序后改变。

相关文章:

算法通关村-----快速排序的原理和实现

快速排序介绍 快速排序是一种经典高效的排序方法&#xff0c;是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列&#xff0c;最终将各个小的有序序列合并成一个大的有序序列。 快速排序的实现原理 选择一个基准值&#xff0c;将小于基准值的元素放…...

百度抓取香港服务器抓取超时是什么情况?

​ 网络延迟导致抓取超时 网络延迟是指从发送请求到接收响应之间的时间延迟。如果网络延迟过高&#xff0c;服务器可能无法及时响应请求&#xff0c;导致超时。在香港服务器上抓取数据时&#xff0c;如果网络延迟过高&#xff0c;可能会出现抓取超时的情况。 服务器负载过高可能…...

Springboot上传文件

上传文件示例代码&#xff1a; ApiOperation("上传文件") PostMapping(value "/uploadFile", consumes MediaType.MULTIPART_FORM_DATA_VALUE) public ApiResult<String> uploadFile(RequestPart("file") MultipartFile file) { //调用七…...

kafka教程

kafka教程 Kafka是一个分布式、分区的、多副本的、多订阅者&#xff0c;基于zookeeper协调的分布式日志系统&#xff0c;其主要特点为&#xff1a; 以时间复杂度为O(1)的方式提供消息持久化能力&#xff0c;即使对TB级以上数据也能保证常数时间的访问性能高吞吐率。即使在非常…...

JVM的故事—— 内存分配策略

内存分配策略 文章目录 内存分配策略一、对象优先在Eden分配二、大对象直接进入老年代三、长期存活的对象将进入老年代四、动态对象年龄判定五、空间分配担保 一、对象优先在Eden分配 堆内存有新生代和老年代&#xff0c;新生代中有一个Eden区和一个Survivor区(from space或者…...

21.CSS的动态圆形进度条

效果 源码 <!doctype html> <html><head><meta charset="utf-8"><title>Animated Circular Progress | CSS Only</title><link rel="stylesheet" href="style.css"></head><body><di…...

Linux_VMware_虚拟机磁盘扩容

来源文章 &#xff1a;VMware教学-虚拟机扩容篇_vmware虚拟机扩容_系统免驱动的博客-CSDN博客 由于项目逐步的完善&#xff0c;需要搭建的中间件&#xff0c;软件越来越多&#xff0c;导致以前虚拟机配置20G的内存不够用了&#xff0c;又不想重新创建新的虚拟机&#xff0c;退…...

中欧财富:分布式数据库的应用历程和 TiDB 7.1 新特性探索

原文来源&#xff1a; https://tidb.net/blog/ccbaeda2 作者&#xff1a;张政俊&#xff0c; 中欧财富数据库负责人 导读 中欧财富是中欧基金控股的销售子公司&#xff0c;旗下 APP 实现业内基金品种全覆盖&#xff0c;提供基金交易、大数据选基、智慧定投、理财师咨询等…...

树莓 LUMA-OLED.EXAMPLE使用

详细介绍在文件目录下的README.rst中 第一步 $ sudo usermod -a -G i2c,spi,gpio pi //好像没什么用 $ sudo apt install python3-dev python3-pip python3-numpy libfreetype6-dev libjpeg-dev build-essential //安装依赖包&#xff0c;树莓派中好像已经有了 $ sudo a…...

C#,《小白学程序》第十一课:双向链表(Linked-List)其二,链表的插入与删除的方法(函数)与代码

1 文本格式 /// <summary> /// 改进的车站信息类 class /// 增加了 链表 需要的两个属性 Last Next /// </summary> public class StationAdvanced { /// <summary> /// 编号 /// </summary> public int Id { get; set; } 0; ///…...

java IDEA文件路径分层级

如下图这样 在设置里找到Compact Middle Packages&#xff0c;去掉勾选就行了...

Spring AOP+Redis实现接口访问限制

目录 一、需求二、实现思路三、代码实现3.1 导入依赖3.2 配置redis3.3 自定义注解3.4 定义切面类3.5 自定义异常类3.6 全局异常处理器 一、需求 在我们程序中&#xff0c;有时候需要对一些接口做访问控制&#xff0c;使程序更稳定&#xff0c;最常用的一种是通过ip限制&#x…...

互联网后端技术大全!

互联网后端技术大全&#xff01; 一. 系统开发 高内聚/低耦合 高内聚 高内聚指一个软件模块是由相关性很强的代码组成&#xff0c;只负责一项任务&#xff0c;也就是常说的单一责任原则。模块的内聚反映模块内部联系的紧密程度。 低耦合 模块之间联系越紧密&#xff0c;其…...

Android SDK 上手指南||第九章 Manifest文件

第九章 Manifest文件 到目前为止&#xff0c;我们已经熟悉了Android项目中的各个组成部分&#xff0c;包括其资源。在今天的文章中&#xff0c;我们将以项目Manifest文件作为核心内容。 对于一个项目来说&#xff0c;Manifest既可以很简单、也可以很复杂&#xff0c;其具体情…...

CVE-2023-3450:锐捷 RG-BCR860 命令执行漏洞复现

锐捷 RG-BCR860 命令执行漏洞(CVE-2023-3450)复现 0x01 前言 本次测试仅供学习使用&#xff0c;如若非法他用&#xff0c;与本文作者无关&#xff0c;需自行负责&#xff01;&#xff01;&#xff01; 0x02 漏洞描述 Ruijie Networks RG-BCR860是中国锐捷网络&#xff08;R…...

【ES】elasticsearch8.3.3

这里仅实践操作并根据实际问题进行记录笔记。 运行 ES8 我们需要在自己的电脑上安装好 Docker Desktop。接着我们运行如下的命令&#xff1a;出现两个异常&#xff0c;一个是需要使用winpty因为我使用win的docker desktop&#xff0c;另外一个问题是docker启动elasticsearchE…...

2023年下半年广州/深圳软考(中/高级)认证报名,当然弘博创新

软考是全国计算机技术与软件专业技术资格&#xff08;水平&#xff09;考试&#xff08;简称软考&#xff09;项目&#xff0c;是由国家人力资源和社会保障部、工业和信息化部共同组织的国家级考试&#xff0c;既属于国家职业资格考试&#xff0c;又是职称资格考试。 系统集成…...

2017. 网格游戏;2397. 被列覆盖的最多行数;2202. K 次操作后最大化顶端元素

2017. 网格游戏 核心思想&#xff1a;前缀和枚举。读完题后可以发现&#xff0c;第一个机器人走的路线就像一条分割线&#xff0c;第二个机器人只能获得上面白色部分或者下面白色部分的最大值。这个最大值怎么求&#xff0c;我们可以通过前缀和来求&#xff0c;然后通过枚举转…...

专访远航汽车远勤山:踏踏实实做好产品 直面挑战乘风远航

8月25日&#xff0c;第二十六届成都国际汽车展览会在中国西部国际博览城隆重开幕。车展举办期间&#xff0c;远航汽车董事长远勤山先生、产品研发总监王震先生向媒体分享了远航汽车品牌发展、产品研发、技术创新以及市场布局等内容。 “通过我们的付出和努力&#xff0c;让我们…...

Redis基本了解

Redis 基于内存进⾏存储&#xff0c;⽀持 key-value 的存储形式&#xff0c;底层是⽤ C 语⾔编写的。 基于 key-value 形式的数据字典&#xff0c;结构⾮常简单&#xff0c;没有数据表的概念&#xff0c;直接⽤键值对的形式完成数据的管理&#xff0c;Redis ⽀持 5 种数据类型…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

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

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

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

虚拟机网络不通的问题(这里以win10的问题为主,模式NAT)

当我们网关配置好了&#xff0c;DNS也配置好了&#xff0c;最后在虚拟机里还是无法访问百度的网址。 第一种情况&#xff1a; 我们先考虑一下&#xff0c;网关的IP是否和虚拟机编辑器里的IP一样不&#xff0c;如果不一样需要更改一下&#xff0c;因为我们访问百度需要从物理机…...