class 023 随机快速排序
这篇文章是看了“左程云”老师在b站上的讲解之后写的, 自己感觉已经能理解了, 所以就将整个过程写下来了。
这个是“左程云”老师个人空间的b站的链接, 数据结构与算法讲的很好很好, 希望大家可以多多支持左程云老师, 真心推荐.
https://space.bilibili.com/8888480?spm_id_from=333.999.0.0
1. 快速排序过程详解
1.1 逻辑解释
- 先设置一个数组
arr[] = [ ], 下标是:0 ~ (n - 1)
, - 然后
0 ~ (n - 1)
位置随机选择一个数字:p
, - 那么就按
p
为分界线, 将<= p
的数字放在左边, 将> p
的数字放在右边, - 然后将
p
这个数字放在左边范围的最右侧位置, (当然可能有很多个p
, 但是我们不关心, 只是放一个) - 此时这个
p
数字算是排好序了. 在整个数组位置上就已经不用变了. - 然后从这个已经排好序的数字
p
的左边和右边位置调用递归过程排序就行了. (就是重复上面的过程), 每次都能将一个数字排好序.
1.2 代码实例
这个过程和上面的逻辑实现是一样的, 直接看就能看懂, 这里我就直接说明几个需要注意的点.
l >= r
:若是l == r
说明只有一个数字, 不用排序, 若是l > r
说明数组不存在.Math.random()
方法的使用:这个Math.random()
方法返回[0, 1)
之间任意的一个浮点数, 我感觉说到这里已经能说明问题了, 这个应该是谁都要掌握的, 要是不知道, 就直接随便看一下讲解就行了. 真没有什么好讲的.
public static int[] sortArray(int[] nums) { if (nums.length > 1) { quickSort1(nums, 0, nums.length - 1); } return nums;
} // 随机快速排序经典版(不推荐)
public static void quickSort1(int[] arr, int l, int r) { if (l >= r) { return; } // 随机这一下,常数时间比较大 // 但只有这一下随机,才能在概率上把快速排序的时间复杂度收敛到O(n * logn) int x = arr[l + (int) (Math.random() * (r - l + 1))]; int mid = partition1(arr, l, r, x); quickSort1(arr, l, mid - 1); quickSort1(arr, mid + 1, r);
} // 已知arr[l....r]范围上一定有x这个值
// 划分数组 <=x放左边,>x放右边,并且确保划分完成后<=x区域的最后一个数字是x
public static int partition1(int[] arr, int l, int r, int x) { // a : arr[l....a-1]范围是<=x的区域 // xi : 记录在<=x的区域上任何一个x的位置,哪一个都可以 int a = l, xi = 0; for (int i = l; i <= r; i++) { if (arr[i] <= x) { swap(arr, a, i); if (arr[a] == x) { xi = a; } a++; } } swap(arr, xi, a - 1); return a - 1;
} public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
2. partition
函数详解
这段代码会有两个分支, 就是 <= x 和 > x
, 所以最开始, 设置 i
对传递进来的数组范围上进行遍历,
- 若是
i
遍历到的数字<= x
, 就让arr[a] 和 arr[i]
进行互换(这一步是到了i
遍历的数字> x
的时候进行交换, 为以后做铺垫), 然后将a++, i++
. 此时<= x
范围的的数字扩大了. - 若是
i
遍历到的数字> x
, 就让a不变, i++
, - 通过上述过程,
i
遍历完数组的数字之后, 可以实现将所有<= x
的数字放在数组的左侧, 将所有> x
的数字放在数组的右侧. - 然后将
x
数字归位到a - 1
位置. 因为这样才能保证x
数字在数组中已经是排好序了. - 最后返回
a - 1
下标.
其中的 a, xi
变量, 左程云老师都在代码的注释中说明好了, 就不画蛇添足了.
// 已知arr[l....r]范围上一定有x这个值
// 划分数组 <=x放左边,>x放右边,并且确保划分完成后<=x区域的最后一个数字是x
public static int partition1(int[] arr, int l, int r, int x) { // a : arr[l....a-1]范围是<=x的区域 // xi : 记录在<=x的区域上任何一个x的位置,哪一个都可以 int a = l, xi = 0; for (int i = l; i <= r; i++) { if (arr[i] <= x) { swap(arr, a, i); if (arr[a] == x) { xi = a; } a++; } } swap(arr, xi, a - 1); return a - 1;
}
3. Partition
函数优化
3.1 优化逻辑
在经典的 Partition
函数中, 只是将所有的位置分成了两个区域, 一次只能是调整好一个数字, 但是有可能在一个数组中, 可能有很多个相同的数字, 比如在随机选择之后, 我们选择了 x
, 但是这个 x
在这个数组中, 有很多个, 那我们干脆可以将所有与 x
相等的数字都排好序, 所以对应的:可以将这个数组分为三个区域:左边是 < x
的区域, 中间是 == x
的区域, 右边是 > x
的区域, 这样就有可能一次将数组中的多个数字排好序.
3.2 代码实例
讲解:我们随机选择的一个数字:x
, 还是和原来一样, 设置一个 i
遍历数组中的所有数字, 将传进来的数组的最左边设置为 l
, 最右边设置为:r
, 分为三种情况.
- 若是
< x
, 则交换a 和 i
, 然后将a++, i++
. - 若是
== x
, 则只是i++
. - 若是
> x
, 则交换b 和 i
, 然后将b--, i 不变
. - 按照上述步骤, 可以将数组分为三个部分.
这个的时间复杂度为:O(n)
, 因为只是用 i
遍历了整个数组.
需要注意的是:这个函数是有返回值的, 只是用全局变量进行等效果的替换了. 使用的方式和意义及其注意点左程云老师都在注释里说明白了.
// 随机快速排序改进版(推荐)
public static void quickSort2(int[] arr, int l, int r) { if (l >= r) { return; } // 随机这一下,常数时间比较大 // 但只有这一下随机,才能在概率上把快速排序的时间复杂度收敛到O(n * logn) int x = arr[l + (int) (Math.random() * (r - l + 1))]; partition2(arr, l, r, x); // 为了防止底层的递归过程覆盖全局变量 // 这里用临时变量记录first、last int left = first; int right = last; quickSort2(arr, l, left - 1); quickSort2(arr, right + 1, r);
} // 荷兰国旗问题
public static int first, last; // 已知arr[l....r]范围上一定有x这个值
// 划分数组 <x放左边,==x放中间,>x放右边
// 把全局变量first, last,更新成==x区域的左右边界
public static void partition2(int[] arr, int l, int r, int x) { first = l; last = r; int i = l; while (i <= last) { if (arr[i] == x) { i++; } else if (arr[i] < x) { swap(arr, first++, i++); } else { swap(arr, i, last--); } }
}
4. 时间复杂度分析
这个随机行为的时间复杂度需要用期望来估计, 这个已经在前面的时间复杂度章节中说明过了.
4.1 最差情况
最慢的情况是:arr[] = [1, 2, 3, 4, 5, 6, 7]
, 若是选择了一个最右侧的数字 7
, 那就要将左边所有的数字遍历一遍, 将 7
放到正确位置之后, 选择 6
, 继续进行遍历, 最后都排好序了, 这个的时间复杂度是:O(n^2)
.
空间复杂度是:O(n)
, 因为按照最差情况, 递归过程压的层数是 n 层
.
4.2 最优情况
最优情况是随机选择之后的数字在整个数组的最中间位置(按数值大小). 所以递归过程是两个相同的子过程 (近似看成), 然后 Partition
过程的时间复杂度是:O(n)
, 所以根据 master 公式
,
时间复杂度 == 2 * T(N/2) + O(n) == O(n * log(n))
.
空间复杂度:因为此时是最优的情况, 所以对应的递归过程也是一个最好的情况, 递归到最底层之后, 返回, 然后进行另一个递归过程, 此时占用的空间是原来最底层的函数使用过的, 是重复利用了的空间, 所以假设数组长度是:n
, 所以这个就是一个二分的过程, 空间复杂度:O(log(n))
.
当然也有可能是一般情况, 有可能还是比较靠近两侧, 或者是比较靠近中间, 但不是最优情况, 也不是最差情况.
所以根据期望, 最后的时间复杂度是:O(n * log(n))
, 空间辅助度是:O(log(n))
. 而且这个不是最好情况的时间复杂度和空间复杂度, 这是数学家们根据所有的情况统计之后, 进行严密的论证之后的答案, 是可以和最好的情况相等, 但是不是最好情况直接用的.
注意:这个证明过程很复杂, 不用掌握也不影响后续的学习.
相关文章:

class 023 随机快速排序
这篇文章是看了“左程云”老师在b站上的讲解之后写的, 自己感觉已经能理解了, 所以就将整个过程写下来了。 这个是“左程云”老师个人空间的b站的链接, 数据结构与算法讲的很好很好, 希望大家可以多多支持左程云老师, 真心推荐. https://space.bilibili.com/8888480?spm_id_f…...

如何理解矩阵的复数特征值和特征向量?
实数特征值的直观含义非常好理解,它就是在对应的特征向量方向上的纯拉伸/压缩。 而复数特征值,我们可以把它放在复数域中理解。但是这里给出一个不那么简洁、但是更加直观的理解方式:把它放在实空间中。那么复数特征值表现的就是旋转等比放大…...

怎么查看网站是否被谷歌收录,查看网站是否被搜索引擎收录5个方法与步骤
要查看网站是否被谷歌(Google)或其他搜索引擎收录,是网站管理和SEO(搜索引擎优化)中的一个重要环节。以下是查看网站是否被搜索引擎收录5个方法与步骤,帮助您确认网站是否被搜索引擎成功索引: …...
Java工具--stream流
Java工具--stream流 过滤(filter)统计求最大最小和均值求和(sum)过滤后,对数据进行统计 遍历(map)规约(reduce)排序(sorted)去重(dist…...

什么是 JWT?它是如何工作的?
松哥最近辅导了几个小伙伴秋招,有小伙伴在面小红书时遇到这个问题,这个问题想回答全面还是有些挑战,松哥结合之前的一篇旧文和大伙一起来聊聊。 一 无状态登录 1.1 什么是有状态 有状态服务,即服务端需要记录每次会话的客户端信…...

微信小程序使用picker,数组怎么设置默认值
默认先显示请选择XXX。然后点击弹出选择列表。如果默认value是0的话,他就直接默认显示数组的第一个了。<picker mode"selector" :value"planIndex" :range"planStatus" range-key"label" change"bindPlanChange&qu…...
Springboot生成树工具类,可通过 id/code 编码生成 2.0版本
优化工具类中,查询父级时便利多次的问题 import org.apache.commons.collections4.CollectionUtils; import org.apache.commons.lang3.mutable.MutableLong; import org.springframework.lang.NonNull; import org.springframework.lang.Nullable; import org.spri…...

17、CPU缓存架构详解高性能内存队列Disruptor实战
1.CPU缓存架构详解 1.1 CPU高速缓存概念 CPU缓存即高速缓冲存储器,是位于CPU与主内存间的一种容量较小但速度很高的存储器。CPU高速缓存可以分为一级缓存,二级缓存,部分高端CPU还具有三级缓存,每一级缓存中所储存的全部数据都是…...

算法训练营打卡Day18
目录 二叉搜索树的最小绝对差二叉搜索树中的众数二叉树的最近公共祖先额外练手题目 题目1、二叉搜索树的最小绝对差 力扣题目链接(opens new window) 给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。 示例: 思…...

【leetcode】169.多数元素
boyer-moore算法最简单理解方法: 假设你在投票选人 如果你和候选人(利益)相同,你就会给他投一票(count1),如果不同,你就会踩他一下(count-1)当候选人票数为0&…...

MyBatis<foreach>标签的用法与实践
foreach标签简介 实践 demo1 简单的一个批量更新,这里传入了一个List类型的集合作为参数,拼接到 in 的后面 ,来实现一个简单的批量更新 <update id"updateVislxble" parameterType"java.util.List">update model…...
R语言Shiny包新手教程
R语言Shiny包新手教程 1. 简介 Shiny 是一个 R 包,用于创建交互式网页应用。它非常适合展示数据分析结果和可视化效果。 2. 环境准备 安装R和RStudio 确保你的计算机上安装了 R 和 RStudio。你可以从 CRAN 下载 R,或从 RStudio 官网 下载 RStudio。…...
[大象快讯]:PostgreSQL 17 重磅发布!
家人们,数据库界的大新闻来了!📣 PostgreSQL 17 正式发布,全球开发者社区的心血结晶,带来了一系列令人兴奋的新特性和性能提升。 发版通告全文如下 PostgreSQL 全球开发小组今天(2024-09-26)宣布…...

CHI trans--Home节点发起的操作
总目录: CHI协议简读汇总-CSDN博客https://blog.csdn.net/zhangshangjie1/article/details/131877216 Home节点能够发起的操作,包含如下几类: Home to Subordinate Read transactionsHome to Subordinate Write transactionsHome to Subor…...

Rust和Go谁会更胜一筹
在国内,我认为Go语言会成为未来的主流,因为国内程序员号称码农,比较适合搬砖,而Rust对心智要求太高了,不适合搬砖。 就个人经验来看,Go语言简单,下限低,没有什么心智成本,…...
记HttpURLConnection下载图片
目录 一、示例代码1 二、示例代码2 一、示例代码1 import java.io.*; import java.net.HttpURLConnection; import java.net.URL;public class Test {/*** 下载图片*/public void getNetImg() {InputStream inStream null;FileOutputStream fOutStream null;try {// URL 统…...

物联网实训室建设的必要性
物联网实训室建设的必要性 一、物联网发展的背景 物联网(IoT)是指通过信息传感设备,按照约定的协议,将任何物品与互联网连接起来,进行信息交换和通信,以实现智能化识别、定位、跟踪、监控和管理的一种网络…...

初识C语言(四)
目录 前言 十一、常见关键字(补充) (1)register —寄存器 (2)typedef类型重命名 (3)static静态的 1、修饰局部变量 2、修饰全局变量 3、修饰函数 十二、#define定义常量和宏…...

产品架构图:从概念到实践
在当今快速发展的科技时代,产品架构图已成为产品经理和设计师不可或缺的工具。它不仅帮助我们理解复杂的产品体系,还能指导我们进行有效的产品设计和开发。本文将深入探讨产品架构图的概念、重要性以及绘制方法。 整个内容框架分为三个部分,…...

smartctl 命令:查看硬盘健康状态
一、命令简介 smartctl 命令用于获取硬盘的 SMART 信息。 介绍硬盘SMART 硬盘的 SMART (Self-Monitoring, Analysis, and Reporting Technology) 技术用于监控硬盘的健康状态,并能提供一些潜在故障的预警信息。通过查看 SMART 数据,用户可以了解硬…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...