插入排序算法详解
快速排序(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作为人工智能领域的重要分支,近年来取得了显著进展,并在多个领域展现出巨大潜力。其核心在于通过机器学习和深度学习算法,从大量数据中学习规律和特征,进而生成具有创新性和多样性的文本、图像、音频和视频…...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...

EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...