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

算法通关村-----快速排序的原理和实现

快速排序介绍

快速排序是一种经典高效的排序方法,是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列,最终将各个小的有序序列合并成一个大的有序序列。

快速排序的实现原理

选择一个基准值,将小于基准值的元素放在基准值左侧,大于基准值的元素放在基准值右侧,基准值放在中间。基准值可以选择待排序列的第一个元素,最后一个元素,中间元素,也可以选择三者的中位数提高快排效率。一轮快速排序后,基准值已经有序,之后对基准值两侧的数据分别进行快排,这是一个递归的过程,最终整个序列有序。整个过程类似于树的前序遍历,每一轮的过程使用双指针,所以快排本质上是树的前序遍历+双指针。

快速排序的具体实现

基准值选择不同,代码实现不同,但本质上都是树的前序遍历+双指针

选择第一个元素作为基准值代码实现

代码实现

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)。

稳定性

快速排序是不稳定的排序算法,即相等元素的相对顺序可能在排序后改变。

相关文章:

算法通关村-----快速排序的原理和实现

快速排序介绍 快速排序是一种经典高效的排序方法&#xff0c;是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列&#xff0c;最终将各个小的有序序列合并成一个大的有序序列。 快速排序的实现原理 选择一个基准值&#xff0c;将小于基准值的元素放…...

百度抓取香港服务器抓取超时是什么情况?

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

Springboot上传文件

上传文件示例代码&#xff1a; ApiOperation("上传文件") PostMapping(value "/uploadFile", consumes MediaType.MULTIPART_FORM_DATA_VALUE) public ApiResult<String> uploadFile(RequestPart("file") MultipartFile file) { //调用七…...

kafka教程

kafka教程 Kafka是一个分布式、分区的、多副本的、多订阅者&#xff0c;基于zookeeper协调的分布式日志系统&#xff0c;其主要特点为&#xff1a; 以时间复杂度为O(1)的方式提供消息持久化能力&#xff0c;即使对TB级以上数据也能保证常数时间的访问性能高吞吐率。即使在非常…...

JVM的故事—— 内存分配策略

内存分配策略 文章目录 内存分配策略一、对象优先在Eden分配二、大对象直接进入老年代三、长期存活的对象将进入老年代四、动态对象年龄判定五、空间分配担保 一、对象优先在Eden分配 堆内存有新生代和老年代&#xff0c;新生代中有一个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_虚拟机磁盘扩容

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

中欧财富:分布式数据库的应用历程和 TiDB 7.1 新特性探索

原文来源&#xff1a; https://tidb.net/blog/ccbaeda2 作者&#xff1a;张政俊&#xff0c; 中欧财富数据库负责人 导读 中欧财富是中欧基金控股的销售子公司&#xff0c;旗下 APP 实现业内基金品种全覆盖&#xff0c;提供基金交易、大数据选基、智慧定投、理财师咨询等…...

树莓 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 //安装依赖包&#xff0c;树莓派中好像已经有了 $ 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&#xff0c;去掉勾选就行了...

Spring AOP+Redis实现接口访问限制

目录 一、需求二、实现思路三、代码实现3.1 导入依赖3.2 配置redis3.3 自定义注解3.4 定义切面类3.5 自定义异常类3.6 全局异常处理器 一、需求 在我们程序中&#xff0c;有时候需要对一些接口做访问控制&#xff0c;使程序更稳定&#xff0c;最常用的一种是通过ip限制&#x…...

互联网后端技术大全!

互联网后端技术大全&#xff01; 一. 系统开发 高内聚/低耦合 高内聚 高内聚指一个软件模块是由相关性很强的代码组成&#xff0c;只负责一项任务&#xff0c;也就是常说的单一责任原则。模块的内聚反映模块内部联系的紧密程度。 低耦合 模块之间联系越紧密&#xff0c;其…...

Android SDK 上手指南||第九章 Manifest文件

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

CVE-2023-3450:锐捷 RG-BCR860 命令执行漏洞复现

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

【ES】elasticsearch8.3.3

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

2023年下半年广州/深圳软考(中/高级)认证报名,当然弘博创新

软考是全国计算机技术与软件专业技术资格&#xff08;水平&#xff09;考试&#xff08;简称软考&#xff09;项目&#xff0c;是由国家人力资源和社会保障部、工业和信息化部共同组织的国家级考试&#xff0c;既属于国家职业资格考试&#xff0c;又是职称资格考试。 系统集成…...

2017. 网格游戏;2397. 被列覆盖的最多行数;2202. K 次操作后最大化顶端元素

2017. 网格游戏 核心思想&#xff1a;前缀和枚举。读完题后可以发现&#xff0c;第一个机器人走的路线就像一条分割线&#xff0c;第二个机器人只能获得上面白色部分或者下面白色部分的最大值。这个最大值怎么求&#xff0c;我们可以通过前缀和来求&#xff0c;然后通过枚举转…...

专访远航汽车远勤山:踏踏实实做好产品 直面挑战乘风远航

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

Redis基本了解

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

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...