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

快速排序算法

news 来源：原创 2025/7/4 2:31:12

快速排序是一种非常高效的排序算法，采用分治策略来对一个数组进行排序。它由C. A. R. Hoare在1960年提出。快速排序的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分继续进行排序，以达到整个序列有序。

一、基本步骤

选择基准：从数列中挑出一个元素，称为“基准”（pivot）。
分区操作：重新排列数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归排序子序列：递归地将小于基准的子序列和大于基准的子序列进行快速排序。

二、Java示例代码

public class QuickSort {public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: ");printArray(arr);}// 快速排序函数public static void quickSort(int[] arr, int low, int high) {if (low < high) {// pi是分区操作后基准元素的位置int pi = partition(arr, low, high);// 递归地对基准左侧和右侧的子数组进行快速排序quickSort(arr, low, pi - 1);  // 左侧子数组quickSort(arr, pi + 1, high); // 右侧子数组}}// 分区函数private static int partition(int[] arr, int low, int high) {// 选择最右边的元素作为基准int pivot = arr[high];// i指向比基准小的最后一个元素int i = (low - 1); // 最初i位于low-1位置for (int j = low; j < high; j++) {// 如果当前元素小于或等于pivotif (arr[j] <= pivot) {i++;  // 增加i// 交换arr[i]和arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 交换arr[i+1]和arr[high]（或pivot）int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;  // 返回基准元素的新索引}// 打印数组public static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}
}

代码解析

主函数 (main 方法)：初始化一个整数数组，并调用 quickSort 函数来对其进行排序。之后打印排序后的数组。
快速排序方法 (quickSort)：接收一个数组以及要排序部分的起始和结束索引。如果起始索引小于结束索引，则执行以下操作：
- 调用 partition 方法获取新的基准元素位置。
- 对基准元素左边的部分递归调用 quickSort。
- 对基准元素右边的部分递归调用 quickSort。
分区方法 (partition)：此方法用于将数组分成两部分，并返回基准元素的位置。它使用了两个指针：i 和 j。其中 i 指向比基准值小的最后一个元素，而 j 则遍历整个数组。每当遇到一个小于或等于基准的元素时，就将 i 向右移动一位，并与 j 处的元素交换。最后，将基准元素放到正确的位置上。
打印数组 (printArray)：辅助函数，用于打印数组中的所有元素。

三、特点

1. 高效性

快速排序在平均情况下的时间复杂度为O(n log n)，这使得它成为一种非常高效的排序算法，尤其适用于大数据集。
在实际应用中，由于其内部循环可以很好地利用缓存，快速排序往往比其他O(n log n)的排序算法（如归并排序）表现得更好。

2. 原地排序

快速排序是一种原地排序算法，即除了递归所需的栈空间外，不需要额外的存储空间。这意味着它的空间复杂度通常为O(log n)，这是由于递归调用栈的深度。

3. 不稳定性

快速排序是不稳定的排序算法，即相等元素的相对顺序可能在排序后发生变化。这是因为当两个相等的元素被放在基准的两侧时，它们的原始顺序可能会被打乱。

4. 分治法

快速排序采用分治策略，通过选择一个基准元素将数组分成两个子数组，然后对这两个子数组分别进行递归排序。这种分而治之的方法使得快速排序能够有效地处理大规模数据集。

5. 最佳、最坏和平均情况

最佳情况下，每次划分都能均匀分割数组，时间复杂度为O(n log n)。
最坏情况下，如果每次选取的基准都是最小或最大元素，那么每次只能排除一个元素，此时时间复杂度退化为O(n^2)。
平均情况下，快速排序的时间复杂度也是O(n log n)。

6. 灵活性高

7. 易于实现

快速排序算法

快速排序是一种非常高效的排序算法，采用分治策略来对一个数组进行排序。它由C. A. R. Hoare在1960年提出。快速排序的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分…...

编程日记 2025/7/4 2:31:12

CSS定位

定位其中，绝对定位和固定定位会脱离文档流设置定位之后：可以使用四个方向值进行调整位置：left、top、right、bottom 相对定位温馨提示设置定位之后，相对定位和绝对定位他是相对于具有定位的父级元素进行位置调整&#xff0c…...

编程日记 2025/7/3 19:25:18

追加docker已运行容器添加或修改端口映射方法

docker run可以指定端口映射【】docker run -d -p 80:80 --name name 但是容器一旦生成，就没有一个命令可以直接修改。通常间接的办法是，保存镜像，再创建一个新的容器，在创建时指定新的端口映射。【】 docker stop A 【】 doc…...

编程日记 2025/7/1 19:47:06

53 基于单片机的8路抢答器加记分

目录一、主要功能二、硬件资源三、程序编程四、实现现象一、主要功能首先有三个按键　分别为开始　暂停　复位，然后八个选手按键，开机显示四条杠，然后按一号选手按键，数码管显示３０，这…...

编程日记 2025/7/2 22:10:40

ubuntu多版本安装gcc

1.ubuntu安装gcc 9.3.1 $ sudo apt update $ sudo apt install gcc-9 g-9 二、配置GCC版本安装完成后，需要使用update-alternatives命令来配置GCC版本。这个命令允许系统在多个安装的版本之间进行选择 1.添加GCC 9.3.1到update-alternatives管理 $ sudo update-a…...

编程日记 2025/7/3 17:42:06

异步处理优化：多线程线程池与消息队列的选择与应用

目录一、异步处理方式引入 （一）异步业务识别 （二）明确异步处理方式二、多线程线程池（Thread Pool） （一）工作原理 （二）直面优缺点和适用场景 1.需要快…...

编程日记 2025/7/4 2:22:33

音视频技术扫盲之预测编码的基本原理探究

预测编码是一种数据压缩技术，广泛应用于图像、视频和音频编码等领域。其基本原理是利用数据的相关性，通过对当前数据的预测和实际值与预测值之间的差值进行编码，从而实现数据压缩的目的。一、预测编码的基本概念预测编码主要包括预测器和…...

编程日记 2025/6/27 9:02:12

计算机毕业设计SpringCloud+大模型微服务高考志愿填报推荐系统高考大数据 SparkML机器学习深度学习人工智能 Python爬虫知识图谱

温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 作者简介：Java领…...

编程日记 2025/7/1 9:34:13

AIGC训练效率与模型优化的深入探讨

文章目录 1.AIGC概述2.AIGC模型训练效率的重要性3.模型优化的概念与目标4.模型优化策略4.1 学习率调节4.2 模型架构选择4.3 数据预处理与增强4.4 正则化技术4.5 量化与剪枝 5.代码示例6.结论人工智能领域的发展，人工智能生成内容（ AIGC）越来…...

编程日记 2025/7/1 4:10:51

《深入浅出HTTPS》读书笔记（13）：块密码算法之迭代模式（续）

CTR模式每次迭代运算的时候要生成一个密钥流（keystream）。各个密钥流之间是有关系的，最简单的方式就是密钥流不断递增，所以才叫作计数器模式。 ◎在处理迭代之前，先生成每个密钥流，有n个数据块&#xff0…...

编程日记 2025/7/3 17:49:42

定时任务删除MongoDB历史数据

前言 MongoDB数据过多，导致存储成本飙升，为了降低成本，需要将历史数据删除。删除逻辑添加配置文件控制删除逻辑 syncconfig:deleteMongoConfig:#同步状态，true同步，false不同步syncStatus: true#删除数据的时间&…...

编程日记 2025/7/2 9:26:47

Simulink的SIL软件在环测试

以基于模型的设计（MBD）的软件开发时，需要进行SIL（软件在环测试）。SIL测试就是在PC上验证模型是否与代码功能一致。在项目开展中，用在需要将控制器生成移植到硬件前，把控制器的模块生成代码&…...

编程日记 2025/7/1 23:40:17

你能穿过迷雾看清一切吗

很多事情的真相有谁知道？ 我和家里人被看不见的攻击攻击和操控，失控和无助状态被假鬼录制，然后安排某些不知道整个实际情况和真相的人去听，间接歪曲了整件事情。各种高科技配合和各种脑功能操控伤害是一般人想都想不到的&#…...

编程日记 2025/7/2 20:28:31

8 设计模式之简单工厂模式

设计模式是软件开发中的一套通用解决方案，而简单工厂模式则是最基础、最常用的一种创建型模式。在这篇博客中，我将为大家详细介绍简单工厂模式的概念、优缺点，以及通过一个饮料制作的案例，帮助大家更好地理解和应用这种模式。一、…...

编程日记 2025/6/29 2:20:19

一步一步写线程之十六线程的安全退出之一理论分析

一、多线程的开发多线程的开发，在实际场景中几乎是无法避开的。即使是前端看似没有使用线程，其实在底层的框架中也使用了线程进行了支撑。至少到现在，不管是协程还是其它什么新的编程方式，仍然无法撼动线程的主流地位。多线程的…...

编程日记 2025/7/1 16:00:44

《Learn Three.js》学习（4）材质

前言： 材质为scene中物体的皮肤，有着不同的特性和视觉效果。材质的共有属性： 基础属性： 融合属性： 融合决定了我们渲染的颜色如何与它们后面的颜色交互高级属性： 与WebGL内部有关简单材质&#xff1…...

编程日记 2025/6/29 23:15:20

【QNX+Android虚拟化方案】128 - QNX 侧触摸屏驱动解析

【QNX+Android虚拟化方案】128 - QNX 侧触摸屏驱动解析一、QNX 侧触摸屏配置基于原生纯净代码，自学总结纯技术分享，不会也不敢涉项目、不泄密、不传播代码文档！！！本文禁止转载分享！！！汇总链接：《【QNX+Android虚拟化方案】00 - 系列文章链接汇总》本文链接：《【…...

编程日记 2025/7/1 13:58:58

Oracle SCN与时间戳的映射关系

目录一、基本概述二、相关操作三、参考文档一、基本概述 Oracle 数据库中的 SYS.SMON_SCN_TIME 表是一个关键的内部表，主要用于记录过去时间段中SCN与具体的时间戳之间的映射关系。这种映射关系可以帮助用户将 SCN 值转换为可读性更强的时间戳，从而…...

编程日记 2025/7/3 12:31:42

量化交易系统开发-实时行情自动化交易-8.2.发明者FMZ平台

19年创业做过一年的量化交易但没有成功，作为交易系统的开发人员积累了一些经验，最近想重新研究交易系统，一边整理一边写出来一些思考供大家参考，也希望跟做量化的朋友有更多的交流和合作。接下来会对于发明者FMZ平台介绍。发明…...

编程日记 2025/6/27 20:56:45

1. 实现SRN （1）使用Numpy实现SRN import numpy as npinputs np.array([[1., 1.],[1., 1.],[2., 2.]]) # 初始化输入序列 print(inputs is , inputs)state_t np.zeros(2, ) # 初始化存储器 print(state_t is , state_t)w1, w2, w3, w4, w5, w6, w7, …...

编程日记 2025/6/27 20:16:55

关于otter监控告警使用

一、背景近期在使用otter完成单机房单向同步时，常常遇到channel假死的情况，导致Pipeline同步停止，系统表数据同步停止，影响生产环境用户数据查询相关的功能，虽然事后能够通过停channel后再启用channel重新启用…...

编程日记 2025/7/3 13:42:23

复合查询和内外连接

文章目录 1. 简单查询2. 多表查询2.1 显示雇员名、雇员工资以及所在部门的名字2.2 显示部门号为10的部门名，员工名和工资2.3 显示各个员工的姓名，工资，及工资级别 3. 自连接4. 子查询4.1 where后的子查询4.1.1 单行子查询4.1.2 多行子查询 (i…...

编程日记 2025/7/3 7:31:44

动态规划【C++优质版】

（本文未经作者书面允许，禁止以任何形式传播（包括但不限于转载，翻译……）如需引用请标注原作者） Intro： 动态规划是一种用于解决优化问题的算法策略。在 C 中，它主要用于处理那些具…...

编程日记 2025/7/3 13:19:58

柔性芯片：实现万物互联的催化剂

物联网 (IoT) 市场已经非常成熟，麦肯锡预测，物联网将再创高峰，到 2030 年将达到 12.5 万亿美元的估值。然而，万物互联 (IoE) 的愿景尚未实现，即由数十亿台智能互联设备组成，提供大规模洞察和效率。究竟是…...

编程日记 2025/6/30 14:50:33

【分布式】分布式事务

目录 1、事务的发展 2、本地事务 （1）如何保障原子性和持久性？ （2）如何保障隔离性？ 2、全局事务 （1）XA事务的两段式提交 （2）XA事务的三段式提交…...

编程日记 2025/7/1 22:38:54

nacos安装部署

nacos安装部署 1.安装nacos 1.安装nacos nacos的安装很简单下载后解压启动即可，但是在启动前请确保jdk环境正常； 1.首先我们要下载nacos安装包：可以到官网下载，注意我这里使用的是2.1.0版本； 2.下载完成后&#xff0…...

编程日记 2025/7/3 12:36:10

git 上传代码时报错

在上传代码时，显示无法上传 PS E:\JavaWeb\vue3-project> git push To https://gitee.com/evening-breeze-2003/vue3.git! [rejected] master -> master (non-fast-forward) error: failed to push some refs to https://gitee.com/evening-breeze-20…...

编程日记 2025/6/30 16:43:15

【C++】数字位数提取：从个位到十位的深入分析与理论拓展

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯第一题：提取个位数解法代码解法分析代码优化拓展思考：取模运算的普适性 💯第二题：提取十位数题目解读与思路分析方法一&…...

编程日记 2025/7/2 23:04:15

数据结构--二叉树的创建和遍历

目录引入定义性质二叉树的创建迭代法注意事项： 递归法注意事项： 二叉树的遍历深度优先广度优先先序遍历（前序遍历） 中序遍历后序遍历层序遍历查找树结构中是否存在某数值方法一： 方法…...

编程日记 2025/6/30 9:10:01

CEF127 编译指南 Linux篇 - 安装Git和Python(三)

1. 引言在前面的文章中，我们已经完成了基础开发工具的安装和配置。接下来，我们需要安装两个同样重要的工具：Git 和 Python。这两个工具在 CEF 的编译过程中扮演着关键角色。Git 负责管理和获取源代码，而 Python 则用于运行各种编…...

编程日记 2025/6/29 9:51:28

计算机网络的类型

目录按覆盖范围分类个人区域网（PAN） 局域网（LAN） 城域网（MAN） 4. 广域网（WAN） 按使用场景和性质分类公网（全球网络） 外网内网（私有网…...

编程日记 2025/7/1 21:22:30

Web入门(学习笔记)

Web入门文章目录 Web入门SpringSpringBootWeb入门HTTP协议HTTP-概述HTTP特点 HTTP-请求协议HTTP-请求数据格式 HTTP-响应协议响应状态码 HTTP-协议解析 Web服务器-TomcatWeb服务器简介基本使用Tomcat文件夹目录解析常见问题Tomcat部署项目入门程序解析**内嵌的Tomcat服务器**…...

编程日记 2025/6/30 5:31:22

mind+自定义库编写注意事项

在mind图形化命令编写中，main.ts 文件是通过图形化编程工具生成 C 代码，然后将生成的 C 代码上传到 Arduino Uno 上执行。这些由main.ts定义的图形化代码通过生成的代码，需要包含调用arduinoc/libraries文件夹的*.h和*.cpp文件&#…...

编程日记 2025/7/4 1:30:37

jQuery零基础入门速通（上）

大家好，我是小黄。在前端开发的世界里，jQuery以其简洁的语法和强大的功能，一直是许多开发者手中的利器。它不仅简化了HTML文档遍历和操作、事件处理、动画以及Ajax交互，还极大地提高了开发效率。本文将带你走进jQuery的世界&…...

编程日记 2025/6/30 6:04:01

计算机网络-Wireshark探索IPv4

使用工具 Wiresharkcurl(MacOS)traceroute: This lab uses “traceroute” to find the router level path from your computer to a remote Internet host. traceroute is a standard command-line utility for discovering the Internet paths that your computer uses. It i…...

编程日记 2025/7/2 11:30:41