算法通关村-----快速排序的原理和实现
快速排序介绍
快速排序是一种经典高效的排序方法,是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列,最终将各个小的有序序列合并成一个大的有序序列。
快速排序的实现原理
选择一个基准值,将小于基准值的元素放在基准值左侧,大于基准值的元素放在基准值右侧,基准值放在中间。基准值可以选择待排序列的第一个元素,最后一个元素,中间元素,也可以选择三者的中位数提高快排效率。一轮快速排序后,基准值已经有序,之后对基准值两侧的数据分别进行快排,这是一个递归的过程,最终整个序列有序。整个过程类似于树的前序遍历,每一轮的过程使用双指针,所以快排本质上是树的前序遍历+双指针。
快速排序的具体实现
基准值选择不同,代码实现不同,但本质上都是树的前序遍历+双指针
选择第一个元素作为基准值代码实现
代码实现
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)。
稳定性
快速排序是不稳定的排序算法,即相等元素的相对顺序可能在排序后改变。
相关文章:
算法通关村-----快速排序的原理和实现
快速排序介绍 快速排序是一种经典高效的排序方法,是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列,最终将各个小的有序序列合并成一个大的有序序列。 快速排序的实现原理 选择一个基准值,将小于基准值的元素放…...
百度抓取香港服务器抓取超时是什么情况?
网络延迟导致抓取超时 网络延迟是指从发送请求到接收响应之间的时间延迟。如果网络延迟过高,服务器可能无法及时响应请求,导致超时。在香港服务器上抓取数据时,如果网络延迟过高,可能会出现抓取超时的情况。 服务器负载过高可能…...
Springboot上传文件
上传文件示例代码: ApiOperation("上传文件") PostMapping(value "/uploadFile", consumes MediaType.MULTIPART_FORM_DATA_VALUE) public ApiResult<String> uploadFile(RequestPart("file") MultipartFile file) { //调用七…...
kafka教程
kafka教程 Kafka是一个分布式、分区的、多副本的、多订阅者,基于zookeeper协调的分布式日志系统,其主要特点为: 以时间复杂度为O(1)的方式提供消息持久化能力,即使对TB级以上数据也能保证常数时间的访问性能高吞吐率。即使在非常…...
JVM的故事—— 内存分配策略
内存分配策略 文章目录 内存分配策略一、对象优先在Eden分配二、大对象直接进入老年代三、长期存活的对象将进入老年代四、动态对象年龄判定五、空间分配担保 一、对象优先在Eden分配 堆内存有新生代和老年代,新生代中有一个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_虚拟机磁盘扩容
来源文章 :VMware教学-虚拟机扩容篇_vmware虚拟机扩容_系统免驱动的博客-CSDN博客 由于项目逐步的完善,需要搭建的中间件,软件越来越多,导致以前虚拟机配置20G的内存不够用了,又不想重新创建新的虚拟机,退…...
中欧财富:分布式数据库的应用历程和 TiDB 7.1 新特性探索
原文来源: https://tidb.net/blog/ccbaeda2 作者:张政俊, 中欧财富数据库负责人 导读 中欧财富是中欧基金控股的销售子公司,旗下 APP 实现业内基金品种全覆盖,提供基金交易、大数据选基、智慧定投、理财师咨询等…...
树莓 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 //安装依赖包,树莓派中好像已经有了 $ 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,去掉勾选就行了...
Spring AOP+Redis实现接口访问限制
目录 一、需求二、实现思路三、代码实现3.1 导入依赖3.2 配置redis3.3 自定义注解3.4 定义切面类3.5 自定义异常类3.6 全局异常处理器 一、需求 在我们程序中,有时候需要对一些接口做访问控制,使程序更稳定,最常用的一种是通过ip限制&#x…...
互联网后端技术大全!
互联网后端技术大全! 一. 系统开发 高内聚/低耦合 高内聚 高内聚指一个软件模块是由相关性很强的代码组成,只负责一项任务,也就是常说的单一责任原则。模块的内聚反映模块内部联系的紧密程度。 低耦合 模块之间联系越紧密,其…...
Android SDK 上手指南||第九章 Manifest文件
第九章 Manifest文件 到目前为止,我们已经熟悉了Android项目中的各个组成部分,包括其资源。在今天的文章中,我们将以项目Manifest文件作为核心内容。 对于一个项目来说,Manifest既可以很简单、也可以很复杂,其具体情…...
CVE-2023-3450:锐捷 RG-BCR860 命令执行漏洞复现
锐捷 RG-BCR860 命令执行漏洞(CVE-2023-3450)复现 0x01 前言 本次测试仅供学习使用,如若非法他用,与本文作者无关,需自行负责!!! 0x02 漏洞描述 Ruijie Networks RG-BCR860是中国锐捷网络(R…...
【ES】elasticsearch8.3.3
这里仅实践操作并根据实际问题进行记录笔记。 运行 ES8 我们需要在自己的电脑上安装好 Docker Desktop。接着我们运行如下的命令:出现两个异常,一个是需要使用winpty因为我使用win的docker desktop,另外一个问题是docker启动elasticsearchE…...
2023年下半年广州/深圳软考(中/高级)认证报名,当然弘博创新
软考是全国计算机技术与软件专业技术资格(水平)考试(简称软考)项目,是由国家人力资源和社会保障部、工业和信息化部共同组织的国家级考试,既属于国家职业资格考试,又是职称资格考试。 系统集成…...
2017. 网格游戏;2397. 被列覆盖的最多行数;2202. K 次操作后最大化顶端元素
2017. 网格游戏 核心思想:前缀和枚举。读完题后可以发现,第一个机器人走的路线就像一条分割线,第二个机器人只能获得上面白色部分或者下面白色部分的最大值。这个最大值怎么求,我们可以通过前缀和来求,然后通过枚举转…...
专访远航汽车远勤山:踏踏实实做好产品 直面挑战乘风远航
8月25日,第二十六届成都国际汽车展览会在中国西部国际博览城隆重开幕。车展举办期间,远航汽车董事长远勤山先生、产品研发总监王震先生向媒体分享了远航汽车品牌发展、产品研发、技术创新以及市场布局等内容。 “通过我们的付出和努力,让我们…...
Redis基本了解
Redis 基于内存进⾏存储,⽀持 key-value 的存储形式,底层是⽤ C 语⾔编写的。 基于 key-value 形式的数据字典,结构⾮常简单,没有数据表的概念,直接⽤键值对的形式完成数据的管理,Redis ⽀持 5 种数据类型…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...
