快速排序(重点)
前言
快排是一种比较重要的排序算法,他的思想有时候会作用到个别算法提上,公司招聘的笔试上有时候也有他的过程推导题,所以搞懂快排势在必行!!!
快速排序
基本思想: 根据基准,将数据分成两个部分,一部分小于基准,另一部分大于基准,然后在通过分治是思想,将每个部分在进行上述操作,最终合并结果
 时间复杂度: 最好情况O(nlogn),最坏情况O(n^2);
 排序稳定性: 不稳定;
现在主流上,快排有两种实现方式,一种是单边循环,一种是双边循环,我个人认为双边循环比较容易理解记忆,而且效率更高一点,所以我还是推荐学习后者即可。
详细介绍(双边)
- 选择最左元素作为基准点元素
- j指针负责从右向左找比基准点小的元素,i指针负责从左向右找比基准点大的元素 (),一旦找到二者交换,直至i,j相交
- 最后基准点与i(此时i与i相等)交换,i即为分区位置
图示:
 
 准备工作: i、j指针分别执行数组首尾,而我们的基准pv选择首
 i的任务: 从左往右找比基准大的值
 j的任务: 从右往左找比基准小的值
 交换: 当 i 和 j 的任务都完成后,就将二者的值进行swap,
 停止: 当左右指针相遇的时候,停止并且,pv指针的值和i指针进行交换
 结果: 这个时候就做到了以基准为分界线,左右两边被分成了两个部分的目的,记录pv当前所在位置
因为上面只是一轮的比较,为了完全排序,我们还需要对两个部分的数据进行递归
快速排序代码实现:
public class QuickSort {public static void main(String[] args) {int[] arr = new int[]{5, 8, 6, 1, 12, 13, 14};quickSort(arr, 0, arr.length - 1);}private static void quickSort(int[] arr, int l, int r) {// 大于:说明后面两个部分都已经排好了// 等于:同一个数之间没有排序意义if (l >= r) {return;}int pv = partition(arr, l, r);quickSort(arr, l, pv - 1);quickSort(arr, pv + 1, r);}// 对于将头设置为pv的情况,我们必须先找右再找左,否则会出现错误// 举个例子(反例):// pv指向头的情况下,我们先往左寻找,那么i和j相遇的地点一定是在j的位置上(i<j,i就会比j多走一步),// 在j的位置的值是比pv的值大的,当将 i 和 pv 进行交换的时候,就会将大的值置换到基准的左边从而导致排序出现问题//// 那么反过来,我们先找的j,由于i<j,那么j就会多走一步,在i的位置上相遇,而i位置上的值又是比pv小的,// 所以二者交换pv两边符合一小一大的排序规则。//// 如果说,你实在是要先走左边,那么你的基准指针pv应该自信数组末尾!!!private static int partition(int[] arr, int l, int r) {int pv = arr[l];int i = l;int j = r;// 当l == r就会退出while (i < j) {// 从右往左找大while (i < j && arr[j] > pv) {j--;}// 从左往右找小// 遇到相等就继续往右走while (i < j && arr[i] <= pv) {i++;}// 当i和j都在一个位置的时候没有交换的意义if(i != j){swap(arr, i, j);}}// 循环出来后交换i和pv的值swap(arr, l, j);return i;}private static void swap(int[] arr, int i, int j) {int temp = arr[j];arr[j] = arr[i];arr[i] = temp;}
}排序结果:
[1, 5, 6, 8, 12]
部分细节说明,已经写在代码中,请详细阅读
相关文章:
 
快速排序(重点)
前言 快排是一种比较重要的排序算法,他的思想有时候会作用到个别算法提上,公司招聘的笔试上有时候也有他的过程推导题,所以搞懂快排势在必行!!! 快速排序 基本思想: 根据基准,将数…...
python高级内置函数介绍及应用举例
目录 1. 概述2. 举例 1. 概述 Python中有许多高级内置函数,它们提供了丰富的功能和便利性,可以大大简化代码并提高效率。以下是一些常用的高级内置函数: map(): 用于将一个函数应用于一个可迭代对象的所有项,返回一…...
 
人体呼吸存在传感器成品,毫米波雷达探测感知技术,引领智能家居新潮流
随着科技的不断进步和人们生活质量的提高,智能化家居逐渐成为一种时尚和生活方式。 人体存在传感器作为智能家居中的重要组成部分,能够实时监测环境中人体是否存在,为智能家居系统提供更加精准的控制和联动。 在这个充满创新的时代…...
 
软件设计模式(三):责任链模式
前言 前面荔枝梳理了有关单例模式、策略模式的相关知识,这篇文章荔枝将沿用之前的写法根据示例demo来体会这种责任链设计模式,希望对有需要的小伙伴有帮助吧哈哈哈哈哈哈~~~ 文章目录 前言 责任链模式 1 简单场景 2 责任链模式理解 3 Java下servl…...
 
开发者的商业智慧:产品立项策划你知道多少?
文章目录 想法的萌芽🌟初步评估产品可行性🍊分析核心功能和特点以及竞争对手📝大健康监测📝时尚新科技产品📝准确性📝多功能📝品牌口碑📝数据分析与个性化建议📝社交互动…...
 
Linux 6.6 初步支持AMD 新一代 Zen 5 处理器
AMD 下一代 Zen 5 CPU 现已开始为 Linux 6.6 支持提交相关代码,最新补丁包括提供温度监控和 EDAC 报告等。 最新的 Linux 6.6 代码中已经加入了包括支持硬件监视器温度监控和 EDAC 报告的补丁。此外,新版本还加入了 x86 / misc 补丁,Phoronix…...
 
第五章 Linux常用应用软件
第五章 Linux常用应用软件  Ubuntu包含了日常所需的常用程序,集成了跨平台的办公套件LibreOffice和Mozila Firefox浏览器等。还提供了文本处理工具、图片处理工具等。 1.LibreOffice  LibreOffice免费开源,遵照GPL分发源代码,与OpenOf…...
 
连接云-边-端,构建火山引擎边缘云网技术体系
近日,火山引擎边缘云网络产品研发负责人韩伟在LiveVideoStack Con 2023上海站围绕边缘云海量分布式节点和上百T的网络规模,结合边缘云快速发展期间遇到的各种问题和挑战,分享了火山引擎边缘云网的全球基础设施,融合开放的云网技术…...
 
系统架构设计师(第二版)学习笔记----系统架构设计师概述
【原文链接】系统架构设计师(第二版)学习笔记----系统架构设计师概述 文章目录 一、架构设计师的定义、职责和任务1.1 架构设计师的定义1.2 架构设计师的任务 二、架构设计师应具备的专业素质2.1 架构设计师应具备的专业知识2.2 架构设计师的知识结构2.3…...
 
自动化测试:Selenium中的时间等待
在 Selenium 中,时间等待指在测试用例中等待某个操作完成或某个事件发生的时间。Selenium 中提供了多种方式来进行时间等待,包括使用 ExpectedConditions 中的 presence_of_element_located 和 visibility_of_element_located 方法等待元素可见或不可见&…...
vim 替换命令 “:s“
vim 替换命令 ":s" 1. 替换光标所在行的第一个匹配串2. 替换光标所在行全部匹配项3. 替换两行之间每行的第一个匹配项4. 替换两行之间的全部匹配项5. 替换整个文件中的每个匹配串6. 查找整个文件中的每个匹配串并询问是否替换 1. 替换光标所在行的第一个匹配串 命令…...
 
【golang】调度系列之m
调度系列 调度系列之goroutine 上一篇中介绍了goroutine,最本质的一句话就是goroutine是用户态的任务。我们通常说的goroutine运行其实严格来说并不准确,因为任务只能被执行。那么goroutine是被谁执行呢?是被m执行。 在GMP的架构中ÿ…...
可持久化线段树
可持久化线段树 模板 在某一指定版本的单点查,单点修。 开 m m m 棵线段树,每次修改复制后单点修。时间复杂度 O ( m ( n log  n ) ) O(m(n\log n)) O(m(nlogn)),空间复杂度 O ( n m ) O(nm) O(nm),不如暴力。 每次修改…...
运行 Node.js 与浏览器 JavaScript
浏览器和 Node.js 都使用 JavaScript 软件语言 - 但字面上的运行时环境是不同的。 Node.js(又名服务器端 JavaScript)与客户端 JavaScript 有许多相似之处。它也有很多差异。 尽管两者都使用 JavaScript 作为软件语言,但我们可以重点关注一些关键差异,这些差异使两者之间…...
File类操作
1. 练习一 在当前模块下的 text 文件夹中创建一个 io.txt 文件 import java.io.File; import java.io.IOException;public class Practice1 {public static void main(String[] args) {File file new File("D:\\kaifamiao");File file1 new File(file, "tex…...
 
C# 实现电子签名
本项目基于Emgu.CV(C#下OpenCv的封装)开发的,编译器最新版Vs2022,编译环境x86 直接看效果图 1.主页面 2.我们先看手写的方式: 点击确认就到主界面,如下 : 点击自动适配-,再点击生成…...
 
小米6/6X/米8/米9手机刷入鸿蒙HarmonyOS.4.0系统-刷机包下载-遥遥领先
小米手机除了解锁root权限,刷GSI和第三方ROM也是米粉的一大爱好,这不,在华为发布了HarmonyOS.4.0系统后不久,我们小米用户也成功将自己的手机干山了HarmonyOS.4.0系统。虽然干上去HarmonyOS.4.0系统目前BUG非常多,根本…...
 
集合框架和泛型二
一、Set接口 1. Set接口概述 java.util.Set 不包含重复元素的集合、不能保证存储的顺序、只允许有一个 null。 public interface Set<E> extends Collection<E>抽象方法,都是继承自 java.util.Collection 接口。 Set 集合的实现类有很多,…...
thinkphp6 入门教程合集(更新中)
thinkphp6 入门(1)--安装、路由规则、多应用模式 thinkphp6 入门(1)--安装、路由规则、多应用模式_软件工程小施同学的博客-CSDN博客 thinkphp6 入门(2)--视图、渲染html页面、赋值 thinkphp6 入门&#…...
 
openGauss学习笔记-65 openGauss 数据库管理-创建和管理数据库
文章目录 openGauss学习笔记-65 openGauss 数据库管理-创建和管理数据库65.1 前提条件65.2 背景信息65.3 注意事项65.4 操作步骤65.4.1 创建数据库65.4.2 查看数据库65.4.3 修改数据库65.4.4 删除数据库 openGauss学习笔记-65 openGauss 数据库管理-创建和管理数据库 65.1 前提…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
 
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
 
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
 
PH热榜 | 2025-06-08
1. Thiings 标语:一套超过1900个免费AI生成的3D图标集合 介绍:Thiings是一个不断扩展的免费AI生成3D图标库,目前已有超过1900个图标。你可以按照主题浏览,生成自己的图标,或者下载整个图标集。所有图标都可以在个人或…...
LeetCode 0386.字典序排数:细心总结条件
【LetMeFly】386.字典序排数:细心总结条件 力扣题目链接:https://leetcode.cn/problems/lexicographical-numbers/ 给你一个整数 n ,按字典序返回范围 [1, n] 内所有整数。 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。…...
 
代理服务器-LVS的3种模式与调度算法
作者介绍:简历上没有一个精通的运维工程师。请点击上方的蓝色《运维小路》关注我,下面的思维导图也是预计更新的内容和当前进度(不定时更新)。 我们上一章介绍了Web服务器,其中以Nginx为主,本章我们来讲解几个代理软件:…...
