【十大排序算法】快速排序
在乱序的世界中,快速排序如同一位智慧的园丁,
以轻盈的手法,将无序的花朵们重新安排,
在每一次比较中,沐浴着理性的阳光,
终使它们在有序的花园里,开出绚烂的芬芳。
文章目录
- 一、快速排序
- 二、发展历史
- 三、处理流程
- 四、算法实现
- 五、快速排序的特性
- 六、小结
- 推荐阅读
一、快速排序
快速排序是一种高效的排序算法,它采用了分治的策略。它的基本思想是选择一个基准值,将数组分为两个子数组,一个子数组中的所有元素都小于基准值,另一个子数组中的所有元素都大于基准值,然后对这两个子数组递归地进行排序。
具体来说,快速排序的步骤如下:
- 选择一个基准值(通常是数组的第一个元素、最后一个元素或者中间元素)。
- 将数组分为两个子数组,一个子数组中的所有元素都小于基准值,另一个子数组中的所有元素都大于基准值。
- 对这两个子数组递归地进行排序。
- 将排好序的子数组合并起来,即得到有序数组。
快速排序的关键在于分割操作,通过这个操作,它可以将一个大问题分解成两个规模较小的子问题,然后分别解决,最终达到整体有序的目的。
二、发展历史
快速排序是由英国计算机科学家 Tony Hoare
在 1960 1960 1960 年代提出的。Hoare 最初将这一算法称为 “分区交换排序”,后来更广泛地称为快速排序。他的灵感来自于合并排序和插入排序。
- 早期思想: Hoare 注意到合并排序在实践中性能良好,但需要额外内存空间;而插入排序则内存消耗较少,但在大规模数据下性能不佳。他希望能够结合两者的优点,创造出一种既能够节省空间又能够在平均情况下具有良好性能的排序算法。
- Hoare 分区法: Hoare 提出了一种称为 Hoare 分区法的分区策略,这成为了快速排序的核心部分。这个方法从数组中选择一个基准值,将数组分成两个部分,左边的部分包含比基准值小的元素,右边的部分包含比基准值大的元素。然后,递归地对这两个部分进行排序。
- 论文发表: Hoare 在 1961 1961 1961 年发表了关于快速排序的论文,论文中描述了这一算法的基本原理和实现方法。此后,他不断改进和优化这一算法,使得快速排序成为了一种非常高效的排序算法。
- 持续优化: 随着计算机科学的发展,许多学者对快速排序进行了进一步的优化和改进。例如,采用随机化的方式选择基准值,以防止最坏情况的发生;使用三数取中法来选择基准值,以提高算法的稳定性和性能等。
- 现代应用: 至今,快速排序仍然是一种非常流行和高效的排序算法,被广泛应用于各种编程语言和实际应用中。其简洁而优雅的设计理念以及优秀的性能使得它成为了排序算法中的经典之作。
三、处理流程
场景假设:我们需要将下列无序序列使用快速排序按从小到大进行排序。
快速排序的流程如下:
- 在原序列中选取第一个元素 3 3 3 作为 Pivot 哨兵
- 将序列中小于 Pivot 的元素,放在 Pivot 的左边,大于 Pivot 的元素放在 Pivot 的右边
- 递归处理 Pivot 左边的序列和右边的序列
- 当子序列为长度 1 1 1 时终止
四、算法实现
// 快速排序入口
void quickSort(int[] arr, int low, int high) {if (low < high) {// 对数组进行分区操作int pivot = partition(arr, low, high);// 递归排序左半部分quickSort(arr, low, pivot - 1);// 递归排序右半部分quickSort(arr, pivot + 1, high);}
}// 分区操作
int partition(int[] arr, int low, int high) {// 选择最后一个元素作为 pivotint pivot = arr[high];int i = low - 1; // 指向小于 pivot 的区域的边界// 遍历数组,将小于 pivot 的元素放到左侧for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;// 交换元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将 pivot 放到正确位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;// 返回 pivot的位置return i + 1;
}public static void main(String[] args) {int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};// 调用快速排序算法quickSort(arr, 0, arr.length - 1);// 输出排序后的数组System.out.print("Sorted array: ");for (int num : arr) {System.out.print(num + " ");}
}
算法时间复杂度分析:
情况 | 时间复杂度 | 计算公式 | 公式解释 |
---|---|---|---|
最好情况 | O ( n l o g n ) O(nlogn) O(nlogn) | T ( n ) = 2 T ( n 2 ) + n T(n) = 2T(\frac{n}{2}) + n T(n)=2T(2n)+n | 在最优情况下,每次划分都能将数组均匀地分成两部分。因此,我们有两个大小为 n 2 \frac{n}{2} 2n 的子问题,所以有 2 T ( n 2 ) 2T(\frac{n}{2}) 2T(2n)。然后,我们需要 n n n 的时间来进行划分操作。所以,总的时间复杂度就是 2 T ( n 2 ) + n 2T(\frac{n}{2}) + n 2T(2n)+n |
平均情况 | O ( n l o g n ) O(nlogn) O(nlogn) | T ( n ) = T ( n 2 ) + T ( n 2 ) + n T(n) = T(\frac{n}{2}) + T(\frac{n}{2}) + n T(n)=T(2n)+T(2n)+n | 在平均情况下,我们假设每次划分都能将数组均匀地分成两部分。因此,我们有两个大小为 n 2 \frac{n}{2} 2n 的子问题,所以有 T ( n 2 ) + T ( n 2 ) T(\frac{n}{2}) + T(\frac{n}{2}) T(2n)+T(2n)。然后,我们需要 n n n 的时间来进行划分操作。所以,总的时间复杂度就是 T ( n 2 ) + T ( n 2 ) + n T(\frac{n}{2}) + T(\frac{n}{2}) + n T(2n)+T(2n)+n |
最坏情况 | O ( n 2 ) O(n^2) O(n2) | T ( n ) = T ( n − 1 ) + n T(n) = T(n - 1) + n T(n)=T(n−1)+n | 在最坏情况下,每次划分只能将数组划分为一份有 n − 1 n - 1 n−1 个元素,另一份有 0 0 0 个元素。因此,我们有一个大小为 n − 1 n - 1 n−1 子问题,所以有 T ( n − 1 ) T(n - 1) T(n−1)。然后,我们需要 n n n 的时间来进行划分操作。所以,总的时间复杂度就是 T ( n − 1 ) + n T(n - 1) + n T(n−1)+n |
五、快速排序的特性
快速排序具有以下特性:
- 稳定性: 在一般情况下,快速排序是
不稳定的
,即相同元素在排序后可能会改变相对位置。 - 原地性: 快速排序是一种原地排序算法,不需要额外的辅助空间,只需要使用原始数组进行排序。
- 适应性: 快速排序适用于各种数据类型,并且对部分有序的数据排序效果良好。
- 高效性: 快速排序在平均情况下具有 O ( n l o g n ) O(nlogn) O(nlogn) 的时间复杂度,使其成为处理大规模数据的理想选择。
六、小结
快速排序是一种非常重要且高效的排序算法,适用于各种数据类型和应用场景。其原地性、高效性以及简单直观的实现使得它成为了排序算法中的经典之作。
推荐阅读
- Spring 三级缓存
- 深入了解 MyBatis 插件:定制化你的持久层框架
- Zookeeper 注册中心:单机部署
- 【JavaScript】探索 JavaScript 中的解构赋值
- 深入理解 JavaScript 中的 Promise、async 和 await
相关文章:

【十大排序算法】快速排序
在乱序的世界中,快速排序如同一位智慧的园丁, 以轻盈的手法,将无序的花朵们重新安排, 在每一次比较中,沐浴着理性的阳光, 终使它们在有序的花园里,开出绚烂的芬芳。 文章目录 一、快速排序二、…...
linux系统ubuntu中在命令行中打开图形界面的文件夹
在命令行中打开当前路径,以文件管理器的形式打开: 命令 # 打开文件管理器 当前的路径 nautilus .nautilus 是一个与 GNOME 桌面环境集成的文件管理器的命令行启动程序。在 Linux 系统中,特别是使用 GNOME 作为桌面环境时,用户经…...

【C++11数据结构与算法】C++ 栈
C 栈(stack) 文章目录 C 栈(stack)栈的基本介绍栈的算法运用单调栈实战题LC例题:[321. 拼接最大数](https://leetcode.cn/problems/create-maximum-number/)LC例题:[316. 去除重复字母](https://leetcode.cn/problems/remove-duplicate-letters/) 栈的基…...

pdf文件如何防篡改内容
PDF文件防篡改内容的方法有多种,以下是一些常见且有效的方法,它们可以帮助确保PDF文件的完整性和真实性: 加密PDF文档: 原理:通过设置密码来保护PDF文档,防止未经授权的访问和修改。注意事项:密…...

QT 音乐播放器【二】 歌词同步+滚动+特效
文章目录 效果图概述代码解析歌词歌词同步歌词特效 总结 效果图 概述 先整体说明一下这个效果的实现,你所看到的歌词都是QGraphicsObject,在QGraphicsView上绘制(paint)出来的。也就是说每一句歌词都是一个图元(item)。 为什么用QGraphicsView框架&…...

关于怎么用Cubemx生成的USBHID设备实现读取一体的鼠标键盘设备(改进版)
主要最近做了一个要用STM32实现读取鼠标键盘一体的那种USB设备,STM32的界面上要和电脑一样的能通过这个USB接口实现鼠标移动,键盘的按键。然后我就很自然的去参考了正点原子的例程,可是找了一圈,发现正点原子好像用的库函数&#…...

Soildworks学习笔记(二)
放样凸台基体: 自动生成连接两个物体两个面的基体: 2.旋转切除: 3.剪切实体: 4.转换实体引用: 将实体的轮廓线转换至当前草图使其成为当前草图的图元,主要用于在同一平面或另一个坐标中制作草图实体或其尺寸的副本。 …...
Linux配置uwsgi环境
Linux配置uwsgi环境 1.进入虚拟环境 source /envs/django_-shop-system/bin/activate2.安装uwsgi pip install uwsgi3.基于uwsgi运行项目 – 基于配置文件 在项目目录下创建配置文件 #socket 0.0.0.0:8005 http 0.0.0.0:8005 # http120.55.47.111:8005 chdir/opt/www/djang…...

Nagios的安装和使用
*实验* *nagios安装和使用* Nagios 是一个监视系统运行状态和网络信息的监视系统。Nagios 能监视所指定的本地或远程主机以及服务,同时提供异常通知功能等. Nagios 可运行在 Linux/Unix 平台之上,同时提供一个可选的基于浏览器的 WEB 界面以方便系统管…...

Numba 的 CUDA 示例(4/4):原子和互斥
本教程为 Numba CUDA 示例 第 4 部分。 本系列第 4 部分总结了使用 Python 从头开始学习 CUDA 编程的旅程 介绍 在本系列的前三部分(第 1 部分,第 2 部分,第 3 部分)中,我们介绍了 CUDA 开发的大部分基础知识…...

【机器学习】机器学习引领AI:重塑人类社会的新纪元
📝个人主页🌹:Eternity._ 🌹🌹期待您的关注 🌹🌹 ❀机器学习引领AI 📒1. 引言📕2. 人工智能(AI)🌈人工智能的发展🌞应用领…...
【制作面包game】
编写一个制作面包的游戏代码涉及到游戏设计、编程和用户界面设计等多个方面。这里我可以提供一个简化版本的Python代码示例,用于创建一个基本的面包制作游戏。这个游戏将会有一个简单的用户界面,玩家可以通过输入命令来制作面包。 游戏的基本流程如下&a…...

Django更改超级用户密码
Django更改超级用户密码 1、打开shell 在工程文件目录下敲入: python manage.py shell再在python交互界面输入: from django.contrib.auth.models import User user User.objects.get(username root) user.set_password(123456) user.save()其中ro…...

ROS基础学习-ROS通信机制进阶
ROS通信机制进阶 目录 0.简介1.常用API1.1 节点初始化函数1.1.1 C++1.1.2 Python1.2 话题与服务相关函数1.2.1 对象获取相关1.2.1.1 C++1.2.1.2 Python1.2.2 订阅对象相关1.2.2.1 C++1.2.2.2 Python1.2.3 服务对象相关函数1.2.3.1 C++1.2.3.2 Python1.2.4 客户端对象相关1.2.4.…...
【Vue3】shallowReactive() and shallowReadonly()
历史小剧场 所谓历史,就是过去的事,它的残酷之处在于:无论你哀嚎,悲伤,痛苦,落寞,追悔,它都无法改变。 一具有名的尸体躺在无数无名的尸体上,这就是所谓的霸业。---- 《明…...

【javaEE初阶】
🌈🌈🌈关于java ⚡⚡⚡java的由来 我们这篇文章主要是来介绍javaEE,一般称为java企业版,实际上java的历史可以追溯到上个世纪90年代,当时主要的语言主流的还是C语言和C,但是在那个时期嵌入式初…...

深度学习 - 梯度下降优化方法
梯度下降的基本概念 梯度下降(Gradient Descent)是一种用于优化机器学习模型参数的算法,其目的是最小化损失函数,从而提高模型的预测精度。梯度下降的核心思想是通过迭代地调整参数,沿着损失函数下降的方向前进&#…...

Steam下载游戏很慢?一个设置解决!
博主今天重装系统后,用steam下载发现巨慢 500MB,都要下载半小时。 平时下载软件,一般1分钟就搞定了,于是大致就知道,设置应该出问题了 于是修改了,如下设置之后,速度翻了10倍。 如下&#x…...
51单片机采用定时器T1的方式1的中断计数方式,外接开关K4按4次后,8只LED闪烁不停
1、功能描述 采用定时器T1的方式1的中断计数方式,外接开关K4按4次后,8只LED闪烁不停 2、实验原理 定时器原理:8051的定时器可以用于计数外部事件或执行内部定时操作。在本程序中,定时器1被设置为模式2,即8位自动重装载定时器模式…...

windows系统 flutter 开发环境配置
1、管理员运行powershell,安装:Chocolatey 工具,粘贴复制运行下列脚本: Chocolatey 官方安装文档 Set-ExecutionPolicy Bypass -Scope Process -Force; [System.Net.ServicePointManager]::SecurityProtocol [System.Net.ServicePointManage…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

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

selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...

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

高抗扰度汽车光耦合器的特性
晶台光电推出的125℃光耦合器系列产品(包括KL357NU、KL3H7U和KL817U),专为高温环境下的汽车应用设计,具备以下核心优势和技术特点: 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计,确保在…...