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

插入排序算法详解

快速排序(Quick Sort)是计算机科学与技术领域中非常经典的一种排序算法,由C. A. R. Hoare在1960年提出。它应用分治思想进行排序,通过对数据进行分区操作,并递归地对分区后的子序列进行排序,从而达到整个序列有序的目的。

基本思想

快速排序的核心思想是在待排序序列中选择一个基准值(pivot),然后将小于基准值的元素放在基准值的左边,大于基准值的元素放在基准值的右边,这样就找到了基准值在数组中的正确位置。之后,再分别对基准值左右两边的子序列进行同样的操作,直到整个序列有序。

排序流程

快速排序算法通过多次比较和交换来实现排序,其排序流程大致如下:

  1. 选择基准值:在待排序序列中选取一个元素作为基准值。
  2. 分区操作:通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
  3. 递归排序:对基准值左右两边的子序列递归地执行上述分区操作,直到子序列的长度为1或0,即已经有序。

排序步骤

以数组为例,快速排序的详细步骤可以归纳为:

  1. 设置两个指针:通常设置两个指针i和j,分别指向序列的起始位置和末尾位置。
  2. 选择基准值:可以选择序列的第一个元素作为基准值,也可以采用其他策略选择基准值。
  3. 分区操作
    • 从后往前搜索(j--),找到第一个小于基准值的元素A[j],将其与A[i]交换。
    • 从前往后搜索(i++),找到第一个大于基准值的元素A[i],将其与A[j]交换。
    • 重复上述步骤,直到i和j相遇,此时基准值就位于其最终位置。
  4. 递归排序:对基准值左边的子序列和右边的子序列分别进行快速排序。

性能分析

  • 时间复杂度:快速排序的平均时间复杂度为O(n log n),但在最坏情况下(如输入序列已经有序或接近有序),时间复杂度会退化到O(n^2)。这通常是由于基准值选择不当导致的。
  • 空间复杂度:快速排序的空间复杂度主要取决于递归的深度。在最好的情况下,递归深度为logn,空间复杂度为O(logn)。但在最坏情况下,递归深度可能达到n,空间复杂度为O(n)。然而,由于快速排序是原地排序(in-place sort),除了递归所需的栈空间外,不需要额外的存储空间,因此可以认为其空间复杂度是O(logn)(不考虑递归栈)。

注意事项

  • 快速排序不是一种稳定的排序算法,即相同的元素在排序后可能会改变它们之间的相对位置。
  • 快速排序的性能受到基准值选择策略的影响,因此在实际应用中需要选择合适的基准值选择策略以提高排序效率。

随机值

在快速排序中,选择基准值(pivot)的策略对算法的性能有着显著的影响。传统的快速排序实现可能会选择序列的第一个、最后一个或中间元素作为基准值,但这些策略在某些情况下(如输入序列已经部分或完全有序)可能导致算法性能退化到O(n^2)。

为了避免这种情况,一种常用的改进方法是随机选择基准值。通过随机选择基准值,可以大大减少算法陷入最坏情况的可能性,从而提高算法的平均性能。

随机选择基准值的步骤

  1. 生成随机数:首先,生成一个随机数randIdx,该随机数的范围是0到n-1(其中n是序列的长度)。

  2. 选择基准值:然后,将randIdx对应的元素选为基准值。这通常涉及到将基准值元素与序列的某个位置(如第一个或最后一个位置)的元素进行交换,以便于后续的分区操作。

  3. 进行分区:使用选定的基准值对序列进行分区操作,将小于基准值的元素放在基准值的左边,大于基准值的元素放在基准值的右边。

  4. 递归排序:对基准值左边和右边的子序列递归地执行上述过程,直到子序列的长度为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;}
};

相关文章:

插入排序算法详解

快速排序&#xff08;Quick Sort&#xff09;是计算机科学与技术领域中非常经典的一种排序算法&#xff0c;由C. A. R. Hoare在1960年提出。它应用分治思想进行排序&#xff0c;通过对数据进行分区操作&#xff0c;并递归地对分区后的子序列进行排序&#xff0c;从而达到整个序…...

parallel 详细解析 Java 8 Stream API 中的 parallel 方法

详解Java Stream的并行处理&#xff08;Parallel&#xff09; Java 8 引入了Stream API&#xff0c;提供了一种便捷而高效的方式来处理集合数据。Stream API使得对数据集合的操作变得更为简洁和易读。 其中&#xff0c;并行流&#xff08;parallelStream&#xff09;是Stream …...

不同业务场景下通过mars3d实现绕点旋转效果

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

重塑水利未来:智慧水利解决方案的探索与实践,从物联网、大数据到人工智能,科技如何赋能水利行业,实现智慧化管理与决策

本文关键词&#xff1a;智慧水利、智慧水利工程、智慧水利发展前景、智慧水利技术、智慧水利信息化系统、智慧水利解决方案、数字水利和智慧水利、数字水利工程、数字水利建设、数字水利概念、人水和协、智慧水库、智慧水库管理平台、智慧水库建设方案、智慧水库解决方案、智慧…...

IO、进程、线程03

第一题&#xff1a;预习 opendir 和 readdir函数 opendir 和 readdir 是两个在C语言&#xff08;特别是使用POSIX标准的系统&#xff0c;如Linux和UNIX&#xff09;中用于目录遍历的函数。这两个函数属于标准的C库中的目录操作部分&#xff0c;通常与<dirent.h>头文件一…...

算法力扣刷题记录 五十二【617.合并二叉树】

前言 二叉树篇&#xff0c;继续。 记录 五十二【617.合并二叉树】 一、题目阅读 给你两棵二叉树&#xff1a; root1 和 root2 。 想象一下&#xff0c;当你将其中一棵覆盖到另一棵之上时&#xff0c;两棵树上的一些节点将会重叠&#xff08;而另一些不会&#xff09;。你需要…...

Java中的ArrayList和LinkedList有什么区别?

Java中的ArrayList和LinkedList是两种常用的集合实现类&#xff0c;它们都属于Java集合框架的一部分&#xff0c;但它们在内部实现、性能特点、使用场景等方面存在明显的区别。以下是对这两种集合的详细比较&#xff1a; 1. 数据结构差异 ArrayList&#xff1a;ArrayList是动…...

Linux C++ 058-设计模式之解释器模式

Linux C 058-设计模式之解释器模式 本节关键字&#xff1a;Linux、C、设计模式、解释器模式 相关库函数&#xff1a; 概念 解释器模式&#xff08;Interpreter Pattern&#xff09;提供了评估语言的语法或表达式的方式&#xff0c;它属于行为型模式。 解释器模式用于构建一…...

MDK5没有DeviceName

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

在LabVIEW中实现图像矫正

在LabVIEW中实现图像矫正&#xff0c;特别是将倾斜的笔记本图像&#xff08;如左图&#xff09;校正为正视图像&#xff08;如右图&#xff09;&#xff0c;通常需要以下几个步骤&#xff1a; 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 日&#xff0c;AutoMQ 携手 GreptimeDB“新能源汽车数据基础设施” 主题 meetup 在上海圆满落幕。本次论坛多角度探讨如何通过创新的数据管理和存储架构&#xff0c;提升汽车系统的性能、安全性和可靠性&#xff0c;从而驱动行业的持续发展和创新&#xff0c;涵盖 Auto…...

格式工厂转换视频分辨率

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

ReAct 大模型提示框架

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

JavaEE:Lombok工具包的使用以及EditStarter插件的安装

Lombok是一个Java工具库&#xff0c;通过添加注解的方式&#xff0c;简化Java的开发。 目录 1、引入依赖 2、使用 3、原理解释 4、更多使用 5、更快捷的引入依赖 1、引入依赖 <dependency><groupId>org.projectlombok</groupId><artifactId>lomb…...

基于纹理和统计图像特征集成的计算机辅助乳腺癌检测

诊断通常使用组织病理学切片&#xff0c;可以确定组织是否处于导管原位癌(DCIS)阶段&#xff0c;其中癌细胞尚未扩散到周围乳腺组织&#xff0c;或浸润性导管癌(IDC)阶段&#xff0c;其中细胞已渗透到邻近组织。对于医生来说&#xff0c;检测IDC非常耗时且具有挑战性。因此&…...

Java基础 - 简介和配置环境变量

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

水域救援装备的详细简介_鼎跃安全

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

二、BIO、NIO、直接内存与零拷贝

一、网络通信编程基础 1、Socket Socket是应用层与TCP/IP协议族通信的中间软件抽象层&#xff0c;是一组接口&#xff0c;由操作系统提供&#xff1b; Socket将复杂的TCP/IP协议处理和通信缓存管理都隐藏在接口后面&#xff0c;对用户来说就是使用简单的接口进行网络应用编程…...

生成式AI的发展方向:Chat vs Agent

一、整体介绍 生成式AI作为人工智能领域的重要分支&#xff0c;近年来取得了显著进展&#xff0c;并在多个领域展现出巨大潜力。其核心在于通过机器学习和深度学习算法&#xff0c;从大量数据中学习规律和特征&#xff0c;进而生成具有创新性和多样性的文本、图像、音频和视频…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

相机从app启动流程

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

10-Oracle 23 ai Vector Search 概述和参数

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

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

TCP/IP 网络编程 | 服务端 客户端的封装

设计模式 文章目录 设计模式一、socket.h 接口&#xff08;interface&#xff09;二、socket.cpp 实现&#xff08;implementation&#xff09;三、server.cpp 使用封装&#xff08;main 函数&#xff09;四、client.cpp 使用封装&#xff08;main 函数&#xff09;五、退出方法…...