算法通关村-----快速排序的原理和实现
快速排序介绍
快速排序是一种经典高效的排序方法,是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列,最终将各个小的有序序列合并成一个大的有序序列。
快速排序的实现原理
选择一个基准值,将小于基准值的元素放在基准值左侧,大于基准值的元素放在基准值右侧,基准值放在中间。基准值可以选择待排序列的第一个元素,最后一个元素,中间元素,也可以选择三者的中位数提高快排效率。一轮快速排序后,基准值已经有序,之后对基准值两侧的数据分别进行快排,这是一个递归的过程,最终整个序列有序。整个过程类似于树的前序遍历,每一轮的过程使用双指针,所以快排本质上是树的前序遍历+双指针。
快速排序的具体实现
基准值选择不同,代码实现不同,但本质上都是树的前序遍历+双指针
选择第一个元素作为基准值代码实现
代码实现
public void quickSort(int[] array, int left, int right) {if (left < right) {int pivot = array[left];int i = right + 1;for (int j = right; j > left; j--) {if (array[j] > pivot) {i--;int temp = array[i];array[i] = array[j];array[j] = temp;}}int pivotIndex = i - 1;int temp = array[pivotIndex];array[pivotIndex] = array[left];array[left] = temp;quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex + 1, right);}
}
选择最后一个元素作为基准值代码实现
代码实现
public void quickSort(int[] array, int left, int right) {if (left < right) {int pivot = array[right];int i = left - 1;for (int j = left; j < right; j++) {if (array[j] < pivot) {i++;int temp = array[i];array[i] = array[j];array[j] = temp;}}int pivotIndex = i + 1;int temp = array[pivotIndex];array[pivotIndex] = array[right];array[right] = temp;quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex + 1, right);}
}
选择中值作为基准值代码实现
代码实现
public static void quickSort(int[] array, int start, int end) {if (start >= end) {return;}int left = start;int right = end;int mid = (left + right) / 2;int pivot = array[mid];while (left <= right) {while (left <= right && array[left] < pivot) {left++;}while (left <= right && array[right] > pivot) {right--;}if (left <= right) {int temp = array[left];array[left] = array[right];array[right] = temp;left++;right--;}}quickSort(array, start, right);quickSort(array, left, end);
}
快速排序复杂度分析
时间复杂度:
平均情况下:O(n log n)。在平均情况下,快速排序通常具有优秀的性能。每次分割都将数组分为两部分,每部分的大小约为原数组的一半。因此,在进行 log n 次递归后,每个子数组都会被完全排序,总的时间复杂度是 O(n log n)。
最坏情况下:O(n^2)。最坏情况发生在选择基准值不平衡的情况下,导致每次分割只能减少一个元素。例如,如果数组已经有序或接近有序,且始终选择第一个元素作为基准值,那么就会出现最坏情况。为了避免最坏情况,可以使用随机选择基准值或者三数取中法等策略。
最好情况下:O(n )。最好情况发生在数组有序
空间复杂度
快速排序是一种原地排序算法,不需要额外的内存空间,因此其空间复杂度是 O(1)。
稳定性
快速排序是不稳定的排序算法,即相等元素的相对顺序可能在排序后改变。
相关文章:
算法通关村-----快速排序的原理和实现
快速排序介绍 快速排序是一种经典高效的排序方法,是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列,最终将各个小的有序序列合并成一个大的有序序列。 快速排序的实现原理 选择一个基准值,将小于基准值的元素放…...

百度抓取香港服务器抓取超时是什么情况?
网络延迟导致抓取超时 网络延迟是指从发送请求到接收响应之间的时间延迟。如果网络延迟过高,服务器可能无法及时响应请求,导致超时。在香港服务器上抓取数据时,如果网络延迟过高,可能会出现抓取超时的情况。 服务器负载过高可能…...

Springboot上传文件
上传文件示例代码: ApiOperation("上传文件") PostMapping(value "/uploadFile", consumes MediaType.MULTIPART_FORM_DATA_VALUE) public ApiResult<String> uploadFile(RequestPart("file") MultipartFile file) { //调用七…...
kafka教程
kafka教程 Kafka是一个分布式、分区的、多副本的、多订阅者,基于zookeeper协调的分布式日志系统,其主要特点为: 以时间复杂度为O(1)的方式提供消息持久化能力,即使对TB级以上数据也能保证常数时间的访问性能高吞吐率。即使在非常…...
JVM的故事—— 内存分配策略
内存分配策略 文章目录 内存分配策略一、对象优先在Eden分配二、大对象直接进入老年代三、长期存活的对象将进入老年代四、动态对象年龄判定五、空间分配担保 一、对象优先在Eden分配 堆内存有新生代和老年代,新生代中有一个Eden区和一个Survivor区(from space或者…...

21.CSS的动态圆形进度条
效果 源码 <!doctype html> <html><head><meta charset="utf-8"><title>Animated Circular Progress | CSS Only</title><link rel="stylesheet" href="style.css"></head><body><di…...

Linux_VMware_虚拟机磁盘扩容
来源文章 :VMware教学-虚拟机扩容篇_vmware虚拟机扩容_系统免驱动的博客-CSDN博客 由于项目逐步的完善,需要搭建的中间件,软件越来越多,导致以前虚拟机配置20G的内存不够用了,又不想重新创建新的虚拟机,退…...

中欧财富:分布式数据库的应用历程和 TiDB 7.1 新特性探索
原文来源: https://tidb.net/blog/ccbaeda2 作者:张政俊, 中欧财富数据库负责人 导读 中欧财富是中欧基金控股的销售子公司,旗下 APP 实现业内基金品种全覆盖,提供基金交易、大数据选基、智慧定投、理财师咨询等…...

树莓 LUMA-OLED.EXAMPLE使用
详细介绍在文件目录下的README.rst中 第一步 $ sudo usermod -a -G i2c,spi,gpio pi //好像没什么用 $ sudo apt install python3-dev python3-pip python3-numpy libfreetype6-dev libjpeg-dev build-essential //安装依赖包,树莓派中好像已经有了 $ sudo a…...

C#,《小白学程序》第十一课:双向链表(Linked-List)其二,链表的插入与删除的方法(函数)与代码
1 文本格式 /// <summary> /// 改进的车站信息类 class /// 增加了 链表 需要的两个属性 Last Next /// </summary> public class StationAdvanced { /// <summary> /// 编号 /// </summary> public int Id { get; set; } 0; ///…...

java IDEA文件路径分层级
如下图这样 在设置里找到Compact Middle Packages,去掉勾选就行了...
Spring AOP+Redis实现接口访问限制
目录 一、需求二、实现思路三、代码实现3.1 导入依赖3.2 配置redis3.3 自定义注解3.4 定义切面类3.5 自定义异常类3.6 全局异常处理器 一、需求 在我们程序中,有时候需要对一些接口做访问控制,使程序更稳定,最常用的一种是通过ip限制&#x…...
互联网后端技术大全!
互联网后端技术大全! 一. 系统开发 高内聚/低耦合 高内聚 高内聚指一个软件模块是由相关性很强的代码组成,只负责一项任务,也就是常说的单一责任原则。模块的内聚反映模块内部联系的紧密程度。 低耦合 模块之间联系越紧密,其…...

Android SDK 上手指南||第九章 Manifest文件
第九章 Manifest文件 到目前为止,我们已经熟悉了Android项目中的各个组成部分,包括其资源。在今天的文章中,我们将以项目Manifest文件作为核心内容。 对于一个项目来说,Manifest既可以很简单、也可以很复杂,其具体情…...

CVE-2023-3450:锐捷 RG-BCR860 命令执行漏洞复现
锐捷 RG-BCR860 命令执行漏洞(CVE-2023-3450)复现 0x01 前言 本次测试仅供学习使用,如若非法他用,与本文作者无关,需自行负责!!! 0x02 漏洞描述 Ruijie Networks RG-BCR860是中国锐捷网络(R…...

【ES】elasticsearch8.3.3
这里仅实践操作并根据实际问题进行记录笔记。 运行 ES8 我们需要在自己的电脑上安装好 Docker Desktop。接着我们运行如下的命令:出现两个异常,一个是需要使用winpty因为我使用win的docker desktop,另外一个问题是docker启动elasticsearchE…...

2023年下半年广州/深圳软考(中/高级)认证报名,当然弘博创新
软考是全国计算机技术与软件专业技术资格(水平)考试(简称软考)项目,是由国家人力资源和社会保障部、工业和信息化部共同组织的国家级考试,既属于国家职业资格考试,又是职称资格考试。 系统集成…...

2017. 网格游戏;2397. 被列覆盖的最多行数;2202. K 次操作后最大化顶端元素
2017. 网格游戏 核心思想:前缀和枚举。读完题后可以发现,第一个机器人走的路线就像一条分割线,第二个机器人只能获得上面白色部分或者下面白色部分的最大值。这个最大值怎么求,我们可以通过前缀和来求,然后通过枚举转…...

专访远航汽车远勤山:踏踏实实做好产品 直面挑战乘风远航
8月25日,第二十六届成都国际汽车展览会在中国西部国际博览城隆重开幕。车展举办期间,远航汽车董事长远勤山先生、产品研发总监王震先生向媒体分享了远航汽车品牌发展、产品研发、技术创新以及市场布局等内容。 “通过我们的付出和努力,让我们…...

Redis基本了解
Redis 基于内存进⾏存储,⽀持 key-value 的存储形式,底层是⽤ C 语⾔编写的。 基于 key-value 形式的数据字典,结构⾮常简单,没有数据表的概念,直接⽤键值对的形式完成数据的管理,Redis ⽀持 5 种数据类型…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...

初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...

【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...

Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...