快速排序的描述以及两种实现方案
一、快速排序描述
- 每一轮排序选择一个基准点(pivot)进行分区
1.1. 让小于基准点的元素的进入一个分区,大于基准点的元素的进入另一个分区
1.2. 当分区完成时,基准点元素的位置就是其最终位置 - 在子分区内重复以上过程,直至子分区元素个数少于等于 1,这体现的是分而治之的思想 (divide-and-conquer)
- 从以上描述可以看出,一个关键在于分区算法,常见的有洛穆托分区方案、双边循环分区方案、霍尔分区方案。
二、单边循环快排(lomuto 洛穆托分区方案)
- 选择最右元素作为基准点元素
- j 指针负责找到比基准点小的元素,一旦找到则与 i 进行交换
- i 指针维护小于基准点元素的边界,也是每次交换的目标索引
- 最后基准点与 i 交换,i 即为分区位置
public static void quick(int[] a, int l, int h) {if (l >= h) {return;}// p 索引值int p = partition(a, l, h); // 左边分区的范围确定quick(a, l, p - 1); // 右边分区的范围确定quick(a, p + 1, h);
}private static int partition(int[] a, int l, int h) {// 基准点元素int pv = a[h]; int i = l;for (int j = l; j < h; j++) {if (a[j] < pv) {if (i != j) {swap(a, i, j);}i++;}}if (i != h) {swap(a, h, i);}System.out.println(Arrays.toString(a) + " i=" + i);// 返回值代表了基准点元素所在的正确索引,用它确定下一轮分区的边界return i;
}
三、双边循环快排(不完全等价于 hoare 霍尔分区方案)
- 选择最左元素作为基准点元素
- j 指针负责从右向左找比基准点小的元素,i 指针负责从左向右找比基准点大的元素,一旦找到二者交换,直至 i,j 相交
- 最后基准点与 i(此时 i 与 j 相等)交换,i 即为分区位置
要点:
1、基准点在左边,并且要先 j 后 i
2、while( i < j && a[j] > pv ) j–
3、while ( i < j && a[i] <= pv ) i++
private static void quick(int[] a, int l, int h) {if (l >= h) {return;}int p = partition(a, l, h);quick(a, l, p - 1);quick(a, p + 1, h);
}private static int partition(int[] a, int l, int h) {int pv = a[l];int i = l;int j = h;while (i < j) {// j 从右找小的while (i < j && a[j] > pv) {j--;}// i 从左找大的while (i < j && a[i] <= pv) {i++;}swap(a, i, j);}swap(a, l, j);System.out.println(Arrays.toString(a) + " j=" + j);return j;
}
四、快排特点
- 平均时间复杂度是 O(nlog2n)O(nlog_2n )O(nlog2n),最坏时间复杂度 O(n2)O(n^2)O(n2)
- 数据量较大时,优势非常明显
- 属于不稳定排序
相关文章:
快速排序的描述以及两种实现方案
一、快速排序描述 每一轮排序选择一个基准点(pivot)进行分区 1.1. 让小于基准点的元素的进入一个分区,大于基准点的元素的进入另一个分区 1.2. 当分区完成时,基准点元素的位置就是其最终位置在子分区内重复以上过程,直…...
算力引领 数“聚”韶关——第二届中国韶关大数据创新创业大赛圆满收官
为进一步促进数字经济领域创新创业发展,推动国家数据中心集群建设,构建大数据领域资源专业平台,促进大湾区大数据科技成果和创新创业人才转化落地,为韶关大数据领域创新型产业集群的打造、大数据科技成果和创新创业人才的转化落地…...
MySQL 记录锁+间隙锁可以防止删除操作而导致的幻读吗?
文章目录什么是幻读?实验验证加锁分析总结什么是幻读? 首先来看看 MySQL 文档是怎么定义幻读(Phantom Read)的: The so-called phantom problem occurs within a transaction when the same query produces different sets of r…...
【分库分表】企业级分库分表实战方案与详解(MySQL专栏启动)
📫作者简介:小明java问道之路,2022年度博客之星全国TOP3,专注于后端、中间件、计算机底层、架构设计演进与稳定性建设优化,文章内容兼具广度、深度、大厂技术方案,对待技术喜欢推理加验证,就职于…...
(考研湖科大教书匠计算机网络)第五章传输层-第五节:TCP拥塞控制
获取pdf:密码7281专栏目录首页:【专栏必读】考研湖科大教书匠计算机网络笔记导航 文章目录一:拥塞控制概述二:拥塞控制四大算法(1)慢开始和拥塞避免A:慢启动(slow start)…...
13.使用自动创建线程池的风险,要自己创建为好
自动创建线程池就是直接调用 Executors去new默认的那几个线程池,但是会出现一定的风险,线程池里面会用到队列,也会跟线程池自身有关,所以要从队列和线程池两个方面去解析。 1.了解线程池的队列 线程池的内部结构主要由四部分组成…...
【项目设计】—— 负载均衡式在线OJ平台
目录 一、项目的相关背景 二、所用技术栈和开发环境 三、项目的宏观结构 四、compile_server模块设计 1. 编译服务(compiler模块) 2. 运行服务(runner模块) 3. 编译并运行服务(compile_run模块) 4…...
Docker学习笔记
1:docker安装步骤Linux 2:docker安装步骤Windows 3:docker官方文档 4:docker官方远程仓库 docker常用命令 1: docker images----查看docker中安装的镜像 2: docker pull nginx------在docker中安装Nginx镜…...
【爬虫理论实战】详解常见头部反爬技巧与验证方式 | 有 Python 代码实现
以下是常见头部反爬技巧与验证方式的大纲: User-Agent 字段的伪装方式,Referer 字段的伪装方式,Cookie 字段的伪装方式。 文章目录1. ⛳️ 头部反爬技巧1.1. User-Agent 字段&User-Agent 的作用1.2. 常见 User-Agent 的特征1.3. User-Age…...
基于SpringBoot+Vue的鲜花商场管理系统
【辰兮要努力】:hello你好我是辰兮,很高兴你能来阅读,昵称是希望自己能不断精进,向着优秀程序员前行! 博客来源于项目以及编程中遇到的问题总结,偶尔会有读书分享,我会陆续更新Java前端、后台、…...
华为OD机试 - 静态扫描最优成本(JS)
静态扫描最优成本 题目 静态扫描快速识别源代码的缺陷,静态扫描的结果以扫描报告作为输出: 文件扫描的成本和文件大小相关,如果文件大小为 N ,则扫描成本为 N 个金币扫描报告的缓存成本和文件大小无关,每缓存一个报告需要 M 个金币扫描报告缓存后,后继再碰到该文件则不…...
多层感知机
多层感知机理论部分 本文系统的讲解多层感知机的pytorch复现,以及详细的代码解释。 部分文字和代码来自《动手学深度学习》!! 目录多层感知机理论部分隐藏层多层感知机数学逻辑激活函数1. ReLU函数2. sigmoid函数3. tanh函数多层感知机的从零…...
python在windows调用svn-pysvn
作为EBS开发人员,开发工具用的多,部署代码类型多,管理程序麻烦,操作繁琐,一直是我最讨厌的事情。部署一次程序要使用好几个工具,改来改去,上传下载,实在难受。 扣了一下python&#…...
office365 word 另存为 pdf 的注意事项和典型设置
0. 操作环境介绍 Office 版本:Office 365 版本 不同版本的操作可能有所不同 1. 基本操作 – 另存为 pdf 【文件】 --> 【另存为】,选择适当的文件路径、文件名保存类型选择【PDF】点击【保存】 1. 导出的pdf包含目录标签 word中,可使用…...
Spring IoC容器之常见常用注解以及注解编程模型简介
一、全文概览 本篇文章主要学习记录Spring中的核心注解,罗列常见常用的注解以及Spring中的注解编程模型介绍 二、核心注解 1、Spring模式注解 常用注解场景描述Spring起始支持版本Component通用组件模式注解,是所有组件类型注解的元注解Spring 2.5Repo…...
超详细讲解文件函数
超详细讲解文件函数!!!!字符输入/输出函数fgetcfputc文本行输入/输出函数fgetsfputs格式化输入/输出函数fscanffprintf二进制输入/输出函数freadfwrite打开/关闭文件函数fopenfclose字符输入/输出函数 fgetc fgetc函数可以从指定…...
【挣值分析】
名称解释 拼写解释PV计划费用,预估预算EV挣值,实际预估预算AC实际费用,实际花费CV成本偏差 (EV - AC)SV进度偏差(EV - PV)CPI成本绩效指数 (EV / AC)SPI进度绩效指数 &a…...
Python3-基础语法
Python3 基础语法 编码 默认情况下,Python 3 源码文件以 UTF-8 编码,所有字符串都是 unicode 字符串。 当然你也可以为源码文件指定不同的编码: # -*- coding: cp-1252 -*-上述定义允许在源文件中使用 Windows-1252 字符集中的字符编码&…...
【计算机网络】数据链路层(下)
文章目录媒体接入控制媒体接入控制-静态划分信道随机接入 CSMACD协议随机接入 CSMACA协议MAC地址MAC地址作用MAC地址格式MAC地址种类MAC地址的发送顺序单播MAC地址广播MAC地址多播MAC地址随机MAC地址IP地址区分网络编号IP地址与MAC地址的封装位置转发过程中IP地址与MAC地址的变…...
系统分析师考试大纲
系统分析师考试大纲 1.考试目标 通过本考试的合格人员应熟悉应用领域的业务,能分析用户的需求和约束条件,写出信息系统需求规格说明书,制订项目开发计划,协调信息系统开发与运行所涉及的各类人员;能指导制…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...
高效的后台管理系统——可进行二次开发
随着互联网技术的迅猛发展,企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心,成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统,它不仅支持跨平台应用,还能提供丰富…...
