数据结构与算法——快速排序
快速排序
一、核心原理:分治策略
1、选一个基准元素,
2、两个指针往中间遍历,比基准值小的移到一边,比基准值大的移到另一边,
一轮遍历后,指针相交位置就是基准值应该放置的位置,同时数组也以基准值分成左右两部分;
3、对两边各自进行递归快排,直到整个数组有序;
二、算法稳定性:不稳定
随机选取基准值,相同的元素可能会分为不同的子数组中;
如:(5,3,2,5,1),基准值为左边第一个5,大于等于基准值的放左边,小于的放右边;
一轮排序后第二个5就在第一个5左边,两个5之间的顺序发生了变化,即不稳定;
三、时间复杂度:平均O(nlogn),最坏O(n^2)
平均O(nlogn):每次对半的划分数组递归排序;最大递归树深度为log(n+1);
最坏O(n^2):基准元素偏向边缘元素,基准元素两边数组大小相差很大,最大递归树深度为n;
四、空间复杂度:平均O(logn),最坏O(n);
由于递归过程需要使用栈空间来保存每一层递归调用的信息,空间复杂度主要考虑递归树的深度;
五、C#代码示例:
using System;public class Algorithm_QuickSort
{static void Main(string[] args){Console.WriteLine("快速排序");int[] array = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };QuickSort(array, 0, array.Length-1);for (int i = 0; i < array.Length; i++)Console.WriteLine(array[i] + "");while(true){}//保持控制台显示}static void QuickSort(int[] array,int left,int right){if (left >= right) return;//left为基准,开始此轮排序int target = array[left];int i = left;int j = right;while (i<j){//移动右指针while (i < j && array[j]> target) j--;if (i < j){array[i] = array[j];i++;}//移动左指针while (i < j && array[i]<target) i++;if (i < j){array[j] = array[i];j--;}}array[i] = target;//目标值放到目标位置,左边都小,右边的都大//对左右两边分别进行快速排序QuickSort(array, left, i - 1);QuickSort(array, i + 1, right);}
}
相关文章:
数据结构与算法——快速排序
快速排序 一、核心原理:分治策略 1、选一个基准元素, 2、两个指针往中间遍历,比基准值小的移到一边,比基准值大的移到另一边, 一轮遍历后,指针相交位置就是基准值应该放置的位置,同时数组也…...
Node.js技术原理分析系列——Node.js调试能力分析
本文由体验技术团队屈金雄原创。 Node.js 是一个开源的、跨平台的 JavaScript 运行时环境,它允许开发者在服务器端运行 JavaScript 代码。Node.js 是基于 Chrome V8引擎构建的,专为高性能、高并发的网络应用而设计,广泛应用于构建服务器端应…...
在Mac arm架构终端中运行 corepack enable yarn 命令,安装yarn
文章目录 1. 什么是 Corepack?2. 运行 corepack enable yarn 的作用3. 如何运行 corepack enable yarn4. 可能遇到的问题及解决方法问题 1:corepack 命令未找到问题 2:Yarn 未正确安装问题 3:权限问题 5. 验证 Yarn 是否启用成功6…...
蓝桥杯试题:计数问题
一、题目描述 试计算在区间 1 到 n的所有整数中,数字 x(0≤x≤9)x(0≤x≤9) 共出现了多少次? 例如,在 1 到 11 中,即在 1、2、3、4、5、6、7、8、9、10、11 中,数字 1 …...
数学建模与MATLAB实现:数据拟合全解析
引言 数据拟合是数学建模与实验分析中的核心任务,旨在通过数学模型逼近实际观测数据,揭示变量间的潜在规律。本文基于最小二乘法的理论框架,结合MATLAB代码实战,系统讲解线性拟合、非线性拟合的实现方法,并通过电阻温…...
C语言——排序(冒泡,选择,插入)
基本概念 排序是对数据进行处理的常见操作,即将数据按某字段规律排列。字段是数据节点的一个属性,比如学生信息中的学号、分数等,可针对这些字段进行排序。同时,排序算法有稳定性之分,若两个待排序字段一致的数据在排序…...
git如何下载指定版本
要使用Git下载指定版本,可以通过以下步骤进行操作: 1. 使用Git命令行下载指定版本: 1.1 首先,使用git clone命令克隆整个git库到本地。例如:git clone [库的URL]。这将下载最新的代码到本地。 1.2 进入克隆…...
数字电路-基础逻辑门实验
基础逻辑门是数字电路设计的核心元件,它们执行的是基本的逻辑运算。通过这些基本运算,可以构建出更为复杂的逻辑功能。常见的基础逻辑门包括与门(AND)、或门(OR)、非门(NOT)、异或门…...
新数据结构(9)——Java异常体系
异常的种类 程序本身通常无法主动捕获并处理错误(Error),因为这些错误通常表示系统级的严重问题,但程序可以捕获并处理异常(Excrption),而Error则被视为一种程序无法或不应尝试恢复的异常类型。…...
每日十题八股-补充材料-2025年2月15日
1.TCP是如何保证消息的顺序和可靠的? 写得超级好的文章 首先肯定是三次握手和四次挥手保证里通讯双方建立了正确有效的连接。 其次是校验和、序列号,ACK消息应答机制还有重传机制,保证了消息顺序和可靠。 同时配合拥塞机制和流量控制机制&am…...
使用 Python 爬虫获取微店快递费用 item_fee API 接口数据
在电商运营中,快递费用是影响商家利润和用户体验的重要因素之一。微店作为国内知名的电商平台,提供了丰富的 API 接口供开发者使用,其中也包括查询商品快递费用的接口。通过调用微店的 item_fee 接口,开发者可以获取指定商品的快递…...
通过用户名和密码登录服务器有哪些方法
通过用户名和密码登录到服务器的方式取决于你使用的工具和协议。以下是几种常见的方法: 1. 使用 SSH 登录到 Linux 服务器 你可以通过 SSH(Secure Shell)使用用户名和密码连接到远程服务器。通常,你会使用 ssh 命令来进行连接。…...
sort快排
当然可以!让我们通过类似的详细步骤来解释 快速排序(Quick Sort) 的原理和实现,就像之前解释 a &= (a - 1) 的原理一样。 快速排序(Quick Sort)原理 快速排序是一种高效的排序算法,其核心思想是分而治之。它通过选择一个“基准值”(pivot),将数组分为两部分: …...
用xml配置spring, bean标签有哪些属性?
用xml配置spring, bean标签有哪些属性? 在Spring框架中,使用XML配置文件时,<bean>标签用于定义一个Bean。以下是一些常用的<bean>标签属性: 1. class 描述:指定Bean的类名。示例:<bean id"myBe…...
纪念日倒数日项目的实现-【纪念时刻-时光集】
纪念日/倒数日项目的实现## 一个练手的小项目,uniappnodemysql七牛云。 在如今快节奏的生活里,大家都忙忙碌碌,那些具有特殊意义的日子一不小心就容易被遗忘。今天,想给各位分享一个“纪念日”项目。 【纪念时刻-时光集】 一…...
无人机不等同轴旋翼架构设计应用探究
“结果显示,对于不等组合,用户应将较小的螺旋桨置于上游以提高能效,但若追求最大推力,则两个相等的螺旋桨更为理想。” 在近期的研究《不等同轴旋翼性能特性探究》中,Max Miles和Stephen D. Prior博士深入探讨了不同螺…...
1-8 gitee码云的注册与使用
码云的网址:Gitee - 基于 Git 的代码托管和研发协作平台 这是一个国内的托管代码平台,速度要比国外的快 1.0 注册 如何注册码云? 查考文章:https://jingyan.baidu.com/article/425e69e6a8cad6ff14fc1615.html 2.0 使用 使用码云进…...
嵌入式硬件篇---OpenMV的硬件流和软件流
文章目录 前言一、硬件流控制(Hardware Flow Control)1. 基本原理RTSCTS 2. OpenMV中的实现• 硬件要求• 代码配置• 工作流程 二、软件流控制(Software Flow Control)1. 基本原理XONXOFF 2. OpenMV中的实现• 代码配置• 工作流…...
Word 里面嵌入DeepSeek
目录 一、问题描述 二、解决方法 三、代码 四、注意事项 五、总结 一、问题描述 如何在Word里面嵌入DeepSeek? 二、解决方法 1、新建文档,按 AltF11,进入VB界面。 2、选中文档,右键->插入->模块。 3、进入模块,粘入…...
聊聊 IP 地址和端口号的区别
在计算机网络中,两个基本概念对于理解设备如何通过网络进行通信至关重要。IP 地址和端口号是 TCP/IP 的典型特征,其定义如下:IP 地址是分配给连接到网络的每台机器的唯一地址,用于定位机器并与其通信。相反,端口号用于…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
