插入排序算法详解
快速排序(Quick Sort)是计算机科学与技术领域中非常经典的一种排序算法,由C. A. R. Hoare在1960年提出。它应用分治思想进行排序,通过对数据进行分区操作,并递归地对分区后的子序列进行排序,从而达到整个序列有序的目的。
基本思想
快速排序的核心思想是在待排序序列中选择一个基准值(pivot),然后将小于基准值的元素放在基准值的左边,大于基准值的元素放在基准值的右边,这样就找到了基准值在数组中的正确位置。之后,再分别对基准值左右两边的子序列进行同样的操作,直到整个序列有序。
排序流程
快速排序算法通过多次比较和交换来实现排序,其排序流程大致如下:
- 选择基准值:在待排序序列中选取一个元素作为基准值。
- 分区操作:通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
- 递归排序:对基准值左右两边的子序列递归地执行上述分区操作,直到子序列的长度为1或0,即已经有序。
排序步骤
以数组为例,快速排序的详细步骤可以归纳为:
- 设置两个指针:通常设置两个指针i和j,分别指向序列的起始位置和末尾位置。
- 选择基准值:可以选择序列的第一个元素作为基准值,也可以采用其他策略选择基准值。
- 分区操作:
- 从后往前搜索(j--),找到第一个小于基准值的元素A[j],将其与A[i]交换。
- 从前往后搜索(i++),找到第一个大于基准值的元素A[i],将其与A[j]交换。
- 重复上述步骤,直到i和j相遇,此时基准值就位于其最终位置。
- 递归排序:对基准值左边的子序列和右边的子序列分别进行快速排序。
性能分析
- 时间复杂度:快速排序的平均时间复杂度为O(n log n),但在最坏情况下(如输入序列已经有序或接近有序),时间复杂度会退化到O(n^2)。这通常是由于基准值选择不当导致的。
- 空间复杂度:快速排序的空间复杂度主要取决于递归的深度。在最好的情况下,递归深度为logn,空间复杂度为O(logn)。但在最坏情况下,递归深度可能达到n,空间复杂度为O(n)。然而,由于快速排序是原地排序(in-place sort),除了递归所需的栈空间外,不需要额外的存储空间,因此可以认为其空间复杂度是O(logn)(不考虑递归栈)。
注意事项
- 快速排序不是一种稳定的排序算法,即相同的元素在排序后可能会改变它们之间的相对位置。
- 快速排序的性能受到基准值选择策略的影响,因此在实际应用中需要选择合适的基准值选择策略以提高排序效率。
随机值
在快速排序中,选择基准值(pivot)的策略对算法的性能有着显著的影响。传统的快速排序实现可能会选择序列的第一个、最后一个或中间元素作为基准值,但这些策略在某些情况下(如输入序列已经部分或完全有序)可能导致算法性能退化到O(n^2)。
为了避免这种情况,一种常用的改进方法是随机选择基准值。通过随机选择基准值,可以大大减少算法陷入最坏情况的可能性,从而提高算法的平均性能。
随机选择基准值的步骤
-
生成随机数:首先,生成一个随机数
randIdx
,该随机数的范围是0到n-1
(其中n
是序列的长度)。 -
选择基准值:然后,将
randIdx
对应的元素选为基准值。这通常涉及到将基准值元素与序列的某个位置(如第一个或最后一个位置)的元素进行交换,以便于后续的分区操作。 -
进行分区:使用选定的基准值对序列进行分区操作,将小于基准值的元素放在基准值的左边,大于基准值的元素放在基准值的右边。
-
递归排序:对基准值左边和右边的子序列递归地执行上述过程,直到子序列的长度为0或1。
优点
-
减少最坏情况的发生:随机选择基准值可以显著降低算法陷入最坏情况(即每次分区都只得到一个空子序列)的可能性。
-
提高平均性能:通过随机化,算法的平均性能更加稳定,不易受到输入数据的影响。
注意事项
-
随机数的生成:在生成随机数时,需要确保随机数生成器的质量,以避免产生可预测的序列。
-
实现复杂度:虽然随机选择基准值可以提高性能,但它也增加了实现的复杂度。特别是在多线程或并行快速排序的实现中,需要更加小心地处理随机数的生成和基准值的选择。
-
内存和性能权衡:在某些情况下,为了生成随机数和进行交换操作,可能会引入额外的内存访问和计算开销。然而,这些开销通常远小于因避免最坏情况而获得的性能提升。
912. 排序数组
给你一个整数数组 nums
,请你将该数组升序排列。
示例 1:
输入:nums = [5,2,3,1] 输出:[1,2,3,5]
示例2:
输入:nums = [5,1,1,2,0,0] 输出:[0,0,1,1,2,5]
提示:
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
若令第一个值为基准元素,提交会显示不通过(超时)
class Solution {
public:void quicksort( vector<int>& nums ,int i,int j){if(i<j){ int l=i,r=j;int plt=nums[l];while(l<r){while (l < r && nums[r] >= plt) r--;while (l < r && nums[l] <= plt) l++;if(l<r){swap(nums[l],nums[r]);}}swap(nums[l],nums[i]);quicksort(nums,i,r-1);quicksort(nums,l+1,j);}}vector<int> sortArray(vector<int>& nums) {int i=0;int j=nums.size()-1;quicksort(nums,i,j);return nums;}
};
基准值采用随机值,可以通过
class Solution {
public:void quicksort( vector<int>& nums ,int i,int j){if(i<j){ int l=i,r=j;int x = rand() % (r - l + 1) + l; // 基于随机的原则swap(nums[l], nums[x]);int plt=nums[l];while(l<r){while (l < r && nums[r] >= plt) r--;while (l < r && nums[l] <= plt) l++;if(l<r){swap(nums[l],nums[r]);}}swap(nums[l],nums[i]);quicksort(nums,i,r-1);quicksort(nums,l+1,j);}}vector<int> sortArray(vector<int>& nums) {int i=0;int j=nums.size()-1;quicksort(nums,i,j);return nums;}
};
相关文章:
插入排序算法详解
快速排序(Quick Sort)是计算机科学与技术领域中非常经典的一种排序算法,由C. A. R. Hoare在1960年提出。它应用分治思想进行排序,通过对数据进行分区操作,并递归地对分区后的子序列进行排序,从而达到整个序…...
parallel 详细解析 Java 8 Stream API 中的 parallel 方法
详解Java Stream的并行处理(Parallel) Java 8 引入了Stream API,提供了一种便捷而高效的方式来处理集合数据。Stream API使得对数据集合的操作变得更为简洁和易读。 其中,并行流(parallelStream)是Stream …...

不同业务场景下通过mars3d实现绕点旋转效果
1.鼠标单击地图某一处就对该点进行绕点旋转效果 相关代码: 1.相关绕点旋转的初始化代码: const rotatePoint new mars3d.thing.RotatePoint({direction: false, // 方向 true逆时针,false顺时针time: 50 // 给定飞行一周所需时间(单位 秒)&…...

重塑水利未来:智慧水利解决方案的探索与实践,从物联网、大数据到人工智能,科技如何赋能水利行业,实现智慧化管理与决策
本文关键词:智慧水利、智慧水利工程、智慧水利发展前景、智慧水利技术、智慧水利信息化系统、智慧水利解决方案、数字水利和智慧水利、数字水利工程、数字水利建设、数字水利概念、人水和协、智慧水库、智慧水库管理平台、智慧水库建设方案、智慧水库解决方案、智慧…...

IO、进程、线程03
第一题:预习 opendir 和 readdir函数 opendir 和 readdir 是两个在C语言(特别是使用POSIX标准的系统,如Linux和UNIX)中用于目录遍历的函数。这两个函数属于标准的C库中的目录操作部分,通常与<dirent.h>头文件一…...

算法力扣刷题记录 五十二【617.合并二叉树】
前言 二叉树篇,继续。 记录 五十二【617.合并二叉树】 一、题目阅读 给你两棵二叉树: root1 和 root2 。 想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要…...
Java中的ArrayList和LinkedList有什么区别?
Java中的ArrayList和LinkedList是两种常用的集合实现类,它们都属于Java集合框架的一部分,但它们在内部实现、性能特点、使用场景等方面存在明显的区别。以下是对这两种集合的详细比较: 1. 数据结构差异 ArrayList:ArrayList是动…...
Linux C++ 058-设计模式之解释器模式
Linux C 058-设计模式之解释器模式 本节关键字:Linux、C、设计模式、解释器模式 相关库函数: 概念 解释器模式(Interpreter Pattern)提供了评估语言的语法或表达式的方式,它属于行为型模式。 解释器模式用于构建一…...

MDK5没有DeviceName
遇到的问题是Jlink驱动问题 不是引脚接反 使用国产GD单片机不同的工程,有的有Device Name,有的没有Device Name(下图是弄好的情况,有Device Name) 硬件链接,和设备都没有问题:无法仿真,无法下…...

在LabVIEW中实现图像矫正
在LabVIEW中实现图像矫正,特别是将倾斜的笔记本图像(如左图)校正为正视图像(如右图),通常需要以下几个步骤: 1. 获取图像 使用图像采集设备或加载图像文件来获取图像数据。 2. 图像预处理 对…...
Apache httpd-vhosts.conf 配置详解(附Demo)
目录 前言1. 基本配置2. http和https3. 重定向和代理配置4. 实战前言 Nginx的相关配置推荐阅读:Nginx将https重定向为http进行访问的配置(附Demo) 1. 基本配置 httpd-vhosts.conf 是 Apache HTTP Server 配置虚拟主机(Virtual Hosts)的文件 虚拟主机允许在一台服务器上…...

活动回顾 | AutoMQ 联合 GreptimeDB 共同探讨新能源汽车数据基础设施
7 月 13 日,AutoMQ 携手 GreptimeDB“新能源汽车数据基础设施” 主题 meetup 在上海圆满落幕。本次论坛多角度探讨如何通过创新的数据管理和存储架构,提升汽车系统的性能、安全性和可靠性,从而驱动行业的持续发展和创新,涵盖 Auto…...

格式工厂转换视频分辨率
1、下载和安装 http://www.pcfreetime.com/formatfactory/CN/index.html 2、打开视频 3、设置分辨率等参数 也可以选择保持原分辨率 4、执行导出 5、打开输出所在位置...

ReAct 大模型提示框架
你可能不熟悉 ReAct,这是一个旨在增强语言模型 (LLM) 决策能力的尖端框架。 通过使用新的观察结果更新 LLM 的上下文窗口并提示其重新评估信息,ReAct 促进了类似于人类思维过程的推理水平,超越了诸如思维链提示之类的旧技术。 在本文中&…...

JavaEE:Lombok工具包的使用以及EditStarter插件的安装
Lombok是一个Java工具库,通过添加注解的方式,简化Java的开发。 目录 1、引入依赖 2、使用 3、原理解释 4、更多使用 5、更快捷的引入依赖 1、引入依赖 <dependency><groupId>org.projectlombok</groupId><artifactId>lomb…...

基于纹理和统计图像特征集成的计算机辅助乳腺癌检测
诊断通常使用组织病理学切片,可以确定组织是否处于导管原位癌(DCIS)阶段,其中癌细胞尚未扩散到周围乳腺组织,或浸润性导管癌(IDC)阶段,其中细胞已渗透到邻近组织。对于医生来说,检测IDC非常耗时且具有挑战性。因此&…...

Java基础 - 简介和配置环境变量
目录 一. 简介 二. 开发环境配置 下载JDK 配置环境变量 Java_Home配置, Path 配置 CLASSPATH 配置 三. 编辑器选择 1.JetBrains 2. Eclipse 3.vscode 下载vscode 安装 vscode插件 四. 总结 一. 简介 Java 是由 Sun Microsystems 公司(后被 Oracle 收…...

水域救援装备的详细简介_鼎跃安全
水域救援行动需要救援人员配备全面、专业的装备,以应对各种复杂的水域环境和救援任务。水域救援套装应运而生,它集合了水域救援所需的各类关键装备,为救援人员提供全方位的保护和辅助,确保数援行动的高效与安全。 水域救援头盔&am…...

二、BIO、NIO、直接内存与零拷贝
一、网络通信编程基础 1、Socket Socket是应用层与TCP/IP协议族通信的中间软件抽象层,是一组接口,由操作系统提供; Socket将复杂的TCP/IP协议处理和通信缓存管理都隐藏在接口后面,对用户来说就是使用简单的接口进行网络应用编程…...
生成式AI的发展方向:Chat vs Agent
一、整体介绍 生成式AI作为人工智能领域的重要分支,近年来取得了显著进展,并在多个领域展现出巨大潜力。其核心在于通过机器学习和深度学习算法,从大量数据中学习规律和特征,进而生成具有创新性和多样性的文本、图像、音频和视频…...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

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

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...

如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...
面试高频问题
文章目录 🚀 消息队列核心技术揭秘:从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"?性能背后的秘密1.1 顺序写入与零拷贝:性能的双引擎1.2 分区并行:数据的"八车道高速公路"1.3 页缓存与批量处理…...
TCP/IP 网络编程 | 服务端 客户端的封装
设计模式 文章目录 设计模式一、socket.h 接口(interface)二、socket.cpp 实现(implementation)三、server.cpp 使用封装(main 函数)四、client.cpp 使用封装(main 函数)五、退出方法…...