快速排序(Java)
基本思想
快速排序Quicksort)是对冒泡排序的一种改进。 基本思想是分治的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序算法的平均时间复杂度是 O(nlogn)
快速排序法示意图:

代码实现
思路:**左右双指针移动 **
例(从小到大排序下面的数组元素)

-
选择最右侧数值作为基准(pivot),并将该位置作为坑;左指针(left)指向最左侧数字,右指针(right)指向最右侧数字

-
左指针向右移动。当左指针与右指针相遇(指向同一数字)时停下来,或者左指针指向数字大于pivot时也停下来,将该值填入坑中,将坑改为此位置

-
右指针向左移动。左指针与右指针相遇时停下来,或者右指针指向数字小于pivot时也停下来,将该值填入坑中,将坑改为此位置

-
循环2、3步直至两指针相遇。如果此时左指针与右指针相遇,此时该位置为坑,将pivot填入该坑中,这样pivot的位置就找好了。

-
递归(以上步骤)基准左、右两旁的数列,直至数列不可再分则完成排序
备注:
- 递归的出口必须仔细考虑清楚,否则就会陷入无穷循环从而使栈溢出;
- 这里如果pivot 选在左侧,就要先从右侧开始遍历,反之则先从左侧开始
- 记得考虑到数值相同的情况
代码落地
public static void quickSort(int[] arr,int startIndex, int endIndex) {if (startIndex >= endIndex) {return;}int left = startIndex, right = endIndex, pivot = arr[endIndex];while (left < right) {while (left < right && arr[left] <= pivot) {left++;}arr[right] = arr[left];while (left < right && arr[right] >= pivot) {right--;}arr[left] = arr[right];}arr[left] = pivot;quickSort(arr, startIndex, left - 1);quickSort(arr, left + 1, endIndex);
}
参考文章
快速排序法(详解)
五分钟学会一个高难度算法:快速排序
排序算法之快速排序(Java实现)
相关文章:
快速排序(Java)
基本思想 快速排序Quicksort)是对冒泡排序的一种改进。 基本思想是分治的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排…...
在ffmpeg中,如何把h264转换为rgb格式
在ffmpeg中,网络视频流h264为什么默认的转为YUV而不是其他格式 文章中介绍了,h264解码的时候是直接解码为yuv的,如果在使用的过程中 需要用到rgb的格式,我们该如何来转换这种格式呢? 在上面的文章中,我们已…...
【重磅】Cookies、headers、Session规律总结,搞定卡点
【重磅】Cookies规律总结,搞定卡点 登录后开始正式获取数据阶段: 不使用session: 放在请求头headers中 当如是:headers = {“user-agent”: “Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/104.0.0.0 Safari/537.36”,“Coo…...
【雷达原理】雷达杂波抑制方法
目录 一、杂波及其特点 1.1 什么是杂波? 1.2 杂波的频谱特性 二、动目标显示(MTI)技术 2.1 对消原理 2.2 数字对消器设计 三、MATLAB仿真 3.1 对消效果验证 3.2 代码 一、杂波及其特点 1.1 什么是杂波? 杂波是相对目标回波而言的,…...
Python-敲木鱼升级版(真手动版敲木鱼)
演示效果 需要安装的第三方库: pip install pygame # 加载音乐 pip install pillow # 加载图片 pip install mediapipe # 判断手势的模型 pip install opencv # 模型要用来处理图形 建议有独显和摄像头的可以尝试! 想着升级一下玩法,只有真敲…...
Websocket @ServerEndpoint不能注入@Autowired
在websocket中使用ServerEndpoint无法注入Autowired、Value 问题分析 Spring管理采用单例模式(singleton),而 WebSocket 是多对象的,即每个客户端对应后台的一个 WebSocket 对象,也可以理解成 new 了一个 WebSocket&…...
Unity热更新
1,热更新的概念与作用 app更新通常分为两类,一种是整包更新(换包),一种是热更新(不换包,通过网络下载,动态更新资源等)。 整包更新,是指在需要更新时&#x…...
如何用维格云搭建和一键训练你的钧瓷AI机器人?
大禹智库 第69期(总第400期) 2023年11月4日 如何用维格云搭建和一键训练你的钧瓷AI机器人? 钧瓷私有数据聊天机器人是一种能够根据预设的数据集进行智能对话的机器人。通过维格云,我们可以轻松地搭建自己的钧瓷私有数据聊天机器人。本文将以钧道机器人为例,详细介绍如何…...
整理的一些Java细节问题
1. 为什么要有无参构造? 在 Java 中,如果一个类没有显式定义构造方法,编译器会自动生成一个默认的无参构造方法(也称为默认构造方法)。无参构造方法是一个没有任何参数的构造方法。 无参构造方法的存在有几个重要原因…...
初识AUTOSAR网络管理
文章目录 目的模式时间参数T_REPEAT_MESSAGET_NM_TIMEOUTT_WAIT_BUS_SLEEPT_START_Tx_AppFrameT_NM_ImmediateCycleTimeT_NM_MessageCycleN_ImmediateNM_TIMEST_START_NM_TXT_WakeUp跳转状态NM_1NM_2NM_3NM_4NM_5NM_6NM_7...
Flink SQL Hive Connector使用场景
目录 1.介绍 2.使用 2.1注册HiveCatalog 2.2Hive Read 2.2.1流读关键配置 2.2.2示例...
【Docker】联合探讨Docker:容器化技术的革命性应用
前言 Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的Linux或Windows操作系统的机器上,也可以实现虚拟化,容器是完全使用沙箱机制,相互之间不会有任何接口。 📕作者简介:热…...
dirhunt使用手册,中文版
“dirhunt” 的命令行工具的帮助信息,用于目录扫描和网站内容分析。以下是这个命令的使用方法和示例: 命令格式: dirhunt [OPTIONS] [URLS]… [URLS]…:一个或多个域名或 URL,可以加载来自文件的 URL,使用…...
【从0到1设计一个网关】如何设计一个稳定的网关?
文章目录 高可用分析软件架构心跳检测自动恢复熔断降级接口重试隔离压测和预案多机房灾备以及双活数据中心异常处理机制重试主备服务自动切换动态剔除或恢复异常机器超时时间的考虑服务设计这篇文章并没有具体的业务实现,而只是对于如何设计一个高可用,稳定的网关列举出了一些…...
chromedp库编写程序
步骤1:首先,我们需要导入chromedp库,以便使用它来下载网页内容。 import chromedp 步骤2:然后,我们需要创建一个函数,该函数接受一个URL作为参数,并使用chromedp库下载该URL的内容。 func do…...
pngquant failed to build, make sure that libpng-dev is installed 问题
第一个参考方案失败 :npm install -g windows-build-tools4.0.0 安装失败,提示 依赖不在支持 第二个方案,降低node 版本 失败 第三种方案,成功 先执行,下面两行代码,再按照依赖 npm install imagemin-pn…...
进程控制(二):进程等待
文章目录 进程控制(二)进程等待wait函数waitpid函数wait/waitpid获取子进程状态码的过程进程等待相关的宏 总结 进程控制(二) 延续对于上文进程结束,我们继续对于进程控制进行学习,本文我们主要是对于进程…...
SWAT-MODFLOW地表水与地下水耦合模型的建模及应用
目录 第一讲 模型原理与层次结构 第二讲 QGIS软件 第三讲 基于QSWATMOD的SWAT-MODFLOW模拟 第四讲 QSWAT模型介绍与建模 第五讲 基于QGIS的数据制备 第六讲 基于CUP的SWAT参数率定 第七讲 MODFLOW模型讲解 第八讲 结果分析 更多应用 耦合模型被应用到很多科学和工程领…...
使用navicat操纵数据库
<1>连接数据库 打开Navicat,点击“连接”,选择“MySQL”,这边是本机安装的mysql,主机为localhost,输入root密码。 使用Navicat创建数据库并导入SQL文件 SQL查询 普通SQL查询 USE demo; SELECT * FROM t_emp;SELECT emp…...
websocket入门
一,什么是websocket WebSocket是HTML5下一种新的协议(websocket协议本质上是一个基于tcp的协议)它实现了浏览器与服务器全双工通信,能更好的节省服务器资源和带宽并达到实时通讯的目的Websocket是一个持久化的协议。 WebSocket有…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
