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

快速排序的描述以及两种实现方案

一、快速排序描述

  1. 每一轮排序选择一个基准点(pivot)进行分区
    1.1. 让小于基准点的元素的进入一个分区,大于基准点的元素的进入另一个分区
    1.2. 当分区完成时,基准点元素的位置就是其最终位置
  2. 在子分区内重复以上过程,直至子分区元素个数少于等于 1,这体现的是分而治之的思想 (divide-and-conquer)
  3. 从以上描述可以看出,一个关键在于分区算法,常见的有洛穆托分区方案、双边循环分区方案、霍尔分区方案。

二、单边循环快排(lomuto 洛穆托分区方案)

  1. 选择最右元素作为基准点元素
  2. j 指针负责找到比基准点小的元素,一旦找到则与 i 进行交换
  3. i 指针维护小于基准点元素的边界,也是每次交换的目标索引
  4. 最后基准点与 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 霍尔分区方案)

  1. 选择最左元素作为基准点元素
  2. j 指针负责从右向左找比基准点小的元素,i 指针负责从左向右找比基准点大的元素,一旦找到二者交换,直至 i,j 相交
  3. 最后基准点与 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;
}

四、快排特点

  1. 平均时间复杂度是 O(nlog2⁡n)O(nlog_2⁡n )O(nlog2n),最坏时间复杂度 O(n2)O(n^2)O(n2)
  2. 数据量较大时,优势非常明显
  3. 属于不稳定排序

相关文章:

快速排序的描述以及两种实现方案

一、快速排序描述 每一轮排序选择一个基准点&#xff08;pivot&#xff09;进行分区 1.1. 让小于基准点的元素的进入一个分区&#xff0c;大于基准点的元素的进入另一个分区 1.2. 当分区完成时&#xff0c;基准点元素的位置就是其最终位置在子分区内重复以上过程&#xff0c;直…...

算力引领 数“聚”韶关——第二届中国韶关大数据创新创业大赛圆满收官

为进一步促进数字经济领域创新创业发展&#xff0c;推动国家数据中心集群建设&#xff0c;构建大数据领域资源专业平台&#xff0c;促进大湾区大数据科技成果和创新创业人才转化落地&#xff0c;为韶关大数据领域创新型产业集群的打造、大数据科技成果和创新创业人才的转化落地…...

MySQL 记录锁+间隙锁可以防止删除操作而导致的幻读吗?

文章目录什么是幻读&#xff1f;实验验证加锁分析总结什么是幻读&#xff1f; 首先来看看 MySQL 文档是怎么定义幻读&#xff08;Phantom Read&#xff09;的: The so-called phantom problem occurs within a transaction when the same query produces different sets of r…...

【分库分表】企业级分库分表实战方案与详解(MySQL专栏启动)

&#x1f4eb;作者简介&#xff1a;小明java问道之路&#xff0c;2022年度博客之星全国TOP3&#xff0c;专注于后端、中间件、计算机底层、架构设计演进与稳定性建设优化&#xff0c;文章内容兼具广度、深度、大厂技术方案&#xff0c;对待技术喜欢推理加验证&#xff0c;就职于…...

(考研湖科大教书匠计算机网络)第五章传输层-第五节:TCP拥塞控制

获取pdf&#xff1a;密码7281专栏目录首页&#xff1a;【专栏必读】考研湖科大教书匠计算机网络笔记导航 文章目录一&#xff1a;拥塞控制概述二&#xff1a;拥塞控制四大算法&#xff08;1&#xff09;慢开始和拥塞避免A&#xff1a;慢启动&#xff08;slow start&#xff09;…...

13.使用自动创建线程池的风险,要自己创建为好

自动创建线程池就是直接调用 Executors去new默认的那几个线程池&#xff0c;但是会出现一定的风险&#xff0c;线程池里面会用到队列&#xff0c;也会跟线程池自身有关&#xff0c;所以要从队列和线程池两个方面去解析。 1.了解线程池的队列 线程池的内部结构主要由四部分组成…...

【项目设计】—— 负载均衡式在线OJ平台

目录 一、项目的相关背景 二、所用技术栈和开发环境 三、项目的宏观结构 四、compile_server模块设计 1. 编译服务&#xff08;compiler模块&#xff09; 2. 运行服务&#xff08;runner模块&#xff09; 3. 编译并运行服务&#xff08;compile_run模块&#xff09; 4…...

Docker学习笔记

1&#xff1a;docker安装步骤Linux 2&#xff1a;docker安装步骤Windows 3&#xff1a;docker官方文档 4&#xff1a;docker官方远程仓库 docker常用命令 1&#xff1a; docker images----查看docker中安装的镜像 2&#xff1a; docker pull nginx------在docker中安装Nginx镜…...

【爬虫理论实战】详解常见头部反爬技巧与验证方式 | 有 Python 代码实现

以下是常见头部反爬技巧与验证方式的大纲&#xff1a; User-Agent 字段的伪装方式&#xff0c;Referer 字段的伪装方式&#xff0c;Cookie 字段的伪装方式。 文章目录1. ⛳️ 头部反爬技巧1.1. User-Agent 字段&User-Agent 的作用1.2. 常见 User-Agent 的特征1.3. User-Age…...

基于SpringBoot+Vue的鲜花商场管理系统

【辰兮要努力】&#xff1a;hello你好我是辰兮&#xff0c;很高兴你能来阅读&#xff0c;昵称是希望自己能不断精进&#xff0c;向着优秀程序员前行&#xff01; 博客来源于项目以及编程中遇到的问题总结&#xff0c;偶尔会有读书分享&#xff0c;我会陆续更新Java前端、后台、…...

华为OD机试 - 静态扫描最优成本(JS)

静态扫描最优成本 题目 静态扫描快速识别源代码的缺陷,静态扫描的结果以扫描报告作为输出: 文件扫描的成本和文件大小相关,如果文件大小为 N ,则扫描成本为 N 个金币扫描报告的缓存成本和文件大小无关,每缓存一个报告需要 M 个金币扫描报告缓存后,后继再碰到该文件则不…...

多层感知机

多层感知机理论部分 本文系统的讲解多层感知机的pytorch复现&#xff0c;以及详细的代码解释。 部分文字和代码来自《动手学深度学习》&#xff01;&#xff01; 目录多层感知机理论部分隐藏层多层感知机数学逻辑激活函数1. ReLU函数2. sigmoid函数3. tanh函数多层感知机的从零…...

python在windows调用svn-pysvn

作为EBS开发人员&#xff0c;开发工具用的多&#xff0c;部署代码类型多&#xff0c;管理程序麻烦&#xff0c;操作繁琐&#xff0c;一直是我最讨厌的事情。部署一次程序要使用好几个工具&#xff0c;改来改去&#xff0c;上传下载&#xff0c;实在难受。 扣了一下python&#…...

office365 word 另存为 pdf 的注意事项和典型设置

0. 操作环境介绍 Office 版本&#xff1a;Office 365 版本 不同版本的操作可能有所不同 1. 基本操作 – 另存为 pdf 【文件】 --> 【另存为】&#xff0c;选择适当的文件路径、文件名保存类型选择【PDF】点击【保存】 1. 导出的pdf包含目录标签 word中&#xff0c;可使用…...

Spring IoC容器之常见常用注解以及注解编程模型简介

一、全文概览 本篇文章主要学习记录Spring中的核心注解&#xff0c;罗列常见常用的注解以及Spring中的注解编程模型介绍 二、核心注解 1、Spring模式注解 常用注解场景描述Spring起始支持版本Component通用组件模式注解&#xff0c;是所有组件类型注解的元注解Spring 2.5Repo…...

超详细讲解文件函数

超详细讲解文件函数&#xff01;&#xff01;&#xff01;&#xff01;字符输入/输出函数fgetcfputc文本行输入/输出函数fgetsfputs格式化输入/输出函数fscanffprintf二进制输入/输出函数freadfwrite打开/关闭文件函数fopenfclose字符输入/输出函数 fgetc fgetc函数可以从指定…...

【挣值分析】

名称解释 拼写解释PV计划费用&#xff0c;预估预算EV挣值&#xff0c;实际预估预算AC实际费用&#xff0c;实际花费CV成本偏差 &#xff08;EV - AC&#xff09;SV进度偏差&#xff08;EV - PV&#xff09;CPI成本绩效指数 &#xff08;EV / AC&#xff09;SPI进度绩效指数 &a…...

Python3-基础语法

Python3 基础语法 编码 默认情况下&#xff0c;Python 3 源码文件以 UTF-8 编码&#xff0c;所有字符串都是 unicode 字符串。 当然你也可以为源码文件指定不同的编码&#xff1a; # -*- coding: cp-1252 -*-上述定义允许在源文件中使用 Windows-1252 字符集中的字符编码&…...

【计算机网络】数据链路层(下)

文章目录媒体接入控制媒体接入控制-静态划分信道随机接入 CSMACD协议随机接入 CSMACA协议MAC地址MAC地址作用MAC地址格式MAC地址种类MAC地址的发送顺序单播MAC地址广播MAC地址多播MAC地址随机MAC地址IP地址区分网络编号IP地址与MAC地址的封装位置转发过程中IP地址与MAC地址的变…...

系统分析师考试大纲

系统分析师考试大纲 1&#xff0e;考试目标 通过本考试的合格人员应熟悉应用领域的业务&#xff0c;能分析用户的需求和约束条件&#xff0c;写出信息系统需求规格说明书&#xff0c;制订项目开发计划&#xff0c;协调信息系统开发与运行所涉及的各类人员&#xff1b;能指导制…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...