数据结构与算法——快速排序
快速排序
一、核心原理:分治策略
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 地址是分配给连接到网络的每台机器的唯一地址,用于定位机器并与其通信。相反,端口号用于…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
ThreadLocal 源码
ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物,因为每个访问一个线程局部变量的线程(通过其 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段,这些类希望将…...
