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

排序算法-快速排序

属性

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元 素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有 元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

        . 1.快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序

          2. 时间复杂度:O(N*logN)

代码及注释(递归写法)

public static void quickSort(int[]arr){quick1(arr,0,arr.length-1);}private static void quick(int[]arr,int begin,int end){//出递归if(begin>=end){return;}//由于参考值的取值要尽量取数据的中间值,所以我们可以拿begin,end和mid下标的中间值来作为参考值//获得了中间值的下标tmpIndexint tmpIndex=threeMid(arr,begin,end);//将中间值交换到第一个位置作为参考值swap(arr,begin,tmpIndex);//进行数据的划分,将小于参考值的数据放到左边,大于参考值的数据放到右边//得到划分好数据后,参考值最终放到的位置(参考值排序后的下标)int rid=parttion1(arr,begin,end);//以同样的方式划分参考值左边和右边的数据quick(arr,begin,rid-1);quick(arr,rid+1,end);}//进行begin-end范围内数据的划分,将小于参考值的数据放到左边,大于参考值的数据放到右边private static int parttion1(int[]arr,int begin,int end){//用挖坑法进行划分int tmp=arr[begin];while (begin<end){//现在begin下标相当于已经没有数据了,是一个坑,要通过end下标找到一个比参考值小的值放到这个坑中while (begin<end&&arr[end]>=tmp){end--;}//跳出了上面的循环说明找到了一个比参考值小的数据//将数据放到坑中arr[begin]=arr[end];//现在end下标相当于已经没有数据了,是一个坑,要通过begin下标找到一个比参考值大的值放到这个坑中while (begin<end&&arr[begin]<=tmp){begin++;}//跳出了上面的循环说明找到了一个比参考值大的数据//将数据放到坑中arr[end]=arr[begin];}//当begin和end指向一个下标时便退出了循环,而他们指向的这个下标是一个坑(没有数据)//将参考值放到这个坑中arr[begin]=tmp;//返回参考值所在的下标,方便去划分参考值左边和右边的数据return begin;}//在array数组中找到下标begin,mid,end的中间值private static int threeMid(int[] array,int begin,int end){int mid=(begin+end)/2;if(array[begin]>array[end]){if(array[end]>array[mid]){return end;}else if(array[mid]>array[begin]){return begin;}else {return mid;}}else {if (array[mid]>array[end]){return end;} else if (array[begin]>array[end]) {return begin;}else {return mid;}}}private static void swap(int[] array,int m,int n){int tmp=array[m];array[m]=array[n];array[n]=tmp;}

代码及注释(非递归写法)

        其实非递归写法的思路和递归相同,只是非递归要自己创建一个栈来模拟出递归的效果而已

 //非递归实现快速排序public static void quickSortNoRrcur(int[] array) {//当排序的数目小于一定范围时直接用插入排序if(array.length<5){InsertSort insertSort=new InsertSort();insertSort.insertSort(array);return;}Stack<Integer> stack=new Stack<>();int start=0;int end=array.length-1;//三数取中int midIndex=threeMid(array, start, end);//把三个数中位于中间的值放到第一位swap(array,start,midIndex);//挖坑法将比array[begin]小的放左边,大的放右边int rid=parttion(array, start, end);//判断是否满足入栈条件if(rid>start+1){stack.push(start);stack.push(rid-1);}if(rid<end-1){stack.push(rid+1);stack.push(end);}while (!stack.empty()){end=stack.pop();start=stack.pop();//当排序的数目小于一定范围时直接用插入排序if(end-start+1<5){InsertSort insertSort=new InsertSort();insertSort.insertSort(array);return;}//三数取中midIndex=threeMid(array, start, end);//把三个数中位于中间的值放到第一位swap(array,start,midIndex);//挖坑法将比array[begin]小的放左边,大的放右边rid=parttion(array, start, end);//判断是否满足入栈条件if(rid>start+1){stack.push(start);stack.push(rid-1);}if(rid<end-1){stack.push(rid+1);stack.push(end);}}}private static int threeMid(int[] array,int begin,int end){int mid=(begin+end)/2;if(array[begin]>array[end]){if(array[end]>array[mid]){return end;}else if(array[mid]>array[begin]){return begin;}else {return mid;}}else {if (array[mid]>array[end]){return end;} else if (array[begin]>array[end]) {return begin;}else {return mid;}}}private static void swap(int[] array,int m,int n){int tmp=array[m];array[m]=array[n];array[n]=tmp;}

相关文章:

排序算法-快速排序

属性 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法&#xff0c;其基本思想为&#xff1a;任取待排序元素序列中的某元 素作为基准值&#xff0c;按照该排序码将待排序集合分割成两子序列&#xff0c;左子序列中所有元素均小于基准值&#xff0c;右子序列中所有 …...

【Spring容器的启动过程】

Spring容器的启动过程 Spring 在初始化过程中有二个非常重要的步骤&#xff0c;容器的初始化与刷新。 初始化流程 如果想生成 bean 对象&#xff0c;那么就需要一个 beanFactory 工厂&#xff08;DefaultListableBeanFactory&#xff09;如果想让加了特定注解&#xff08;如 …...

普通二本+转专业学计算机是什么感受

目录 自我介绍转入前为什么转专业为什么转入机械专业 转入后转入后感受确定自学计算机自学计算机的时间分配 自我介绍 作者现在是大二,由于当时高考考砸了,分数在重本线左右,为了去一个稍微好一点的学校,于是填报了化学工程与工艺(并不是说这专业不好,只是填报化工更容易进这个…...

力扣1、两数之和

转到力扣 题目 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是&#xff0c;数组中同一个元素在答案里不能重复出现。 你可…...

一百七十三、Flume——Flume写入HDFS后的诸多小文件问题

一、目的 在用Flume采集Kafka中的数据写入HDFS后&#xff0c;发现写入HDFS的不是每天一个文件&#xff0c;而是一个文件夹&#xff0c;里面有很多小文件&#xff0c;浪费namenode的宝贵资源 二、Flume的配置文件优化&#xff08;参考了其他博文&#xff09; &#xff08;一&a…...

Android.mk中C++使用

参考&#xff1a; https://gerrit.twrp.me/c/android_bootable_recovery//4366/1/Android.mk ifeq ($(BOARD_USES_RECOVERY_AS_BOOT), true) LOCAL_CFLAGS -DBOARD_USES_RECOVERY_AS_BOOT endif ifeq ($(BOARD_BUILD_SYSTEM_ROOT_IMAGE), true) LOCAL_CFLAGS -DBOA…...

K8S:Pod概念、分类及相关的策略

文章目录 一.pod相关概念&#xff11;.Pod基础概念&#xff12;.Kubrenetes集群中Pod两种使用方式&#xff13;.pause容器的Pod中的所有容器共享的资源&#xff14;.kubernetes中的pause容器主要为每个容器提供功能&#xff1a;&#xff15;.Kubernetes设计这样的Pod概念和特殊…...

【Java杂谈】#1 【MCA JAVA后端架构师】

文章目录 巧用弱引用 解决 TreadLocal内存泄漏问题P5&#xff0c;P6&#xff0c;P7Spring 巧用弱引用 解决 TreadLocal内存泄漏问题 < Treadlocal > 本地调用框架使用&#xff08;Spring&#xff09; IOC&#xff0c;AOP注解transactional&#xff0c;自动支持事务处理…...

Vue3路由

文章目录 Vue3路由1. 载入vue-router 库2. 实例2.1 Vue.js vue-router 实现单页应用2.2 router-link创建链接2.3 router-view显示与url对应组件2.4 <router-link> 相关属性 Vue3路由 1. 载入vue-router 库 Vue.js 路由需要载入vue-router 库 安装直接下载地址&#xf…...

Android Studio的笔记--aidl实现和调用

android AIDL接口使用 aidl实现新建aidl实现工程build.gradleproguard-rules.pro增加aidl文件 增加aidl实现aidl实现服务打开aidl服务 aidl使用新建aidl使用工程增加aidl文件使用aidl方法 相关回显 aidl实现 新建aidl实现工程 新建一个工程。工程名testaidl。包名com.lxh.tes…...

大模型从入门到应用——LangChain:代理(Agents)-[工具包(Toolkit)]

分类目录&#xff1a;《大模型从入门到应用》总目录 工具包是工具的集合&#xff0c;这些工具被设计成一起用于特定的任务&#xff0c;并且具有方便的加载方法。常见的工具包如下&#xff1a; CSV代理JiraJSON代理OpenAPI代理自然语言APIPandas数据框架代理PlayWright浏览器工…...

VR全景算不算好的创业项目?有哪些特性?

现在是全民创业的时代&#xff0c;大家都在找创业项目&#xff0c;那么什么是好的创业项目呢&#xff1f;有人会问VR全景算不算创业好项目呢&#xff1f;一般情况下好的创业项目&#xff0c;发展前景和市场消费群体都是比较大的&#xff0c;市场需求大才能满足多数消费者的需求…...

Spring系列文章:Spring集成Log4j2⽇志框架、整合JUnit

一、集成Log4j2⽇志框架 从Spring5之后&#xff0c;Spring框架⽀持集成的⽇志框架是Log4j2.如何启⽤⽇志框架&#xff1a; 第⼀步&#xff1a;引⼊Log4j2的依赖 <!--log4j2的依赖--> <dependency><groupId>org.apache.logging.log4j</groupId><a…...

flink的网络缓冲区

背景 在flink的taskmanager进行数据交互的过程中&#xff0c;网络缓冲区是一个可以提升网络交换速度的设计&#xff0c;此外&#xff0c;flink还通过网络缓冲区实现其基于信用值credit的流量控制&#xff0c;以便尽可能的处理数据倾斜问题 网络缓冲区 在flink中每个taskmana…...

产品经理学习笔记

产品文档之BRD、MRD和PRD - 知乎BRD、MRD和PRD一起被认为是从市场到产品需要形成的标准规范文档&#xff1a; 1、BRD&#xff08;Business Requirement Document&#xff09;&#xff0c;商业需求文档&#xff0c;是一份产品商业论证报告&#xff0c;基于商业目标或价值所描述的…...

【深入理解Linux锁机制】七、互斥体

系列文章: 我的圈子:高级工程师聚集地 【深入理解Linux锁机制】一、内核锁的由来 【深入理解Linux锁机制】二、中断屏蔽 【深入理解Linux锁机制】三、原子操作 【深入理解Linux锁机制】四、自旋锁 【深入理解Linux锁机制】五、衍生自旋锁 【深入理解Linux锁机制】六、信…...

UGUI画布加载优化

在Unity中&#xff0c;UGUI画布的加载优化可以通过以下几种方式来实现&#xff1a; 1. 合理使用画布渲染模式&#xff1a;UGUI画布有三种渲染模式&#xff0c;分别是Screen Space - Overlay、Screen Space - Camera和World Space。在使用时&#xff0c;应根据场景需求选择最适…...

SEC的下一步目标是什么?过时的证券法与加密货币行业,哪个会被先淘汰?

加密货币已经“不合规”了&#xff0c;尤其是其“商业模式”&#xff0c;至少美国证券交易委员会(SEC)主席Gary Gensler这样认为。由于这种观点在美国监管机构中普遍存在&#xff0c;因此涉及加密的执法行动达到历史最高水平也不足为奇。 在短短几年内&#xff0c;我们目睹了所…...

Kafka3.0.0版本——消费者(独立消费者消费某一个主题数据案例__订阅主题)

目录 一、独立消费者消费某一个主题数据案例1.1、案例需求1.2、案例代码1.3、测试 一、独立消费者消费某一个主题数据案例 1.1、案例需求 创建一个独立消费者&#xff0c;消费firstTopic主题中数据&#xff0c;所下图所示&#xff1a; 注意&#xff1a;在消费者 API 代码中必…...

笔记本多拓展出一个屏幕

一、首先要知道&#xff0c;自己的电脑有没有Type-c接口&#xff0c;支持不支持VGA 推荐&#xff1a; 自己不清楚&#xff0c;问客服&#xff0c;勤问。 二、显示屏与笔记本相连&#xff0c;通过VGA 三、连接好了&#xff0c;需要去配置 网址&#xff1a;凑合着看&#xff…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...