Java算法—排序篇之快速排序(Quick sort)

快速排序(Quick sort)

核心思路:

  1. 从数列中挑出一个元素,一般都是左边第一个数字,称为 “基准数”;
  2. 创建两个指针,一个从前往后走,一个从后往前走。
  3. 先执行后面的指针,找出第一个比基准数小的数字
  4. 再执行前面的指针,找出第一个比基准数大的数字
  5. 交换两个指针指向的数字
  6. 直到两个指针相遇
  7. 将基准数跟指针指向位置的数字交换位置,称之为:基准数归位。
  8. 第一轮结束之后,基准数左边的数字都是比基准数小的,基准数右边的数字都是比基准数大的。
  9. 把基准数左边看做一个序列,把基准数右边看做一个序列,按照刚刚的规则递归排序

下面详细讲解,附有图形演示:

1. 从数列中挑出一个元素,一般都是左边第一个数字,称为 “基准数”;
在这里插入图片描述
在这里插入图片描述

2. 创建两个指针,一个从前往后走,一个从后往前走。
在这里插入图片描述

3. 先执行后面的指针,找出第一个比基准数小的数字
4. 再执行前面的指针,找出第一个比基准数大的数字

在这里插入图片描述
在这里插入图片描述

5. 交换两个指针指向的数字**
在这里插入图片描述
5.1交换后继续移动 start 和 end,继续查找start指向比基准数大的,end指向比基准数小的,然后交换…依次类推…
在这里插入图片描述
在这里插入图片描述

6. 直到两个指针相遇
在这里插入图片描述

7. 将基准数跟指针指向位置的数字交换位置,称之为:基准数归位。
在这里插入图片描述

9. 第一轮结束之后,基准数左边的数字都是比基准数小的,基准数右边的数字都是比基准数大的。
10. 把基准数左边看做一个序列,把基准数右边看做一个序列,按照刚刚的规则递归排序

在这里插入图片描述
代码实现:

public class QuickSortTest02 {public static void main(String[] args) {int[] arr = {6,1,2,7,9,3,4,5,10,8};System.out.println("排序前:");for (int i : arr) {System.out.print(i+" ");}System.out.println();// 调用方法进行排序quickSort(arr,0,arr.length-1);System.out.println("排序后:");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");}}//定义方法public static void quickSort(int[] arr,int i,int j){// 定义两个变量记录起始索引和结束索引int start = i;int end = j;if (start>end){// 递归出口return;}// 定义基准数为起始索引int baserNum = arr[i];while (start != end){// end从后往前,找基准数小的while (true){if(end <= start || arr[end]<baserNum){break;}end--;}// star 从前往后,找比基准数大的while (true){if(end <= start || arr[start] > baserNum){break;}start++;}// 此时,start指向了比基准数大的数,end指向了比基准数小的数// 然后将start指向的数和end指向的数交换int temp = arr[start];arr[start] = arr[end];arr[end] = temp;}// 当start和end指向同一个元素,则上面的循环结束//表示已经找到了基准数应存入的位置//然后 将这个范围中的第一个数和start(或者end)指向的元素进行交换//基准数归位int temp = arr[start];arr[start] = arr[i];arr[i] = temp;// 利用递归思想,重复上面步骤// 上述将基准数放到了该放的位置,即3 1 2 5 4 6 9 7 10 8//确定6左边的范围,重复刚刚所做的事情quickSort(arr,i,end-1);//确定6右边的范围,重复刚刚所做的事情quickSort(arr,start+1,j);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/410717.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

灵魂 20 问帮你彻底搞定Transformer

1.Transformer为何使用多头注意力机制&#xff1f;&#xff08;为什么不使用一个头&#xff09; 捕捉多种依赖关系&#xff1a; 多头注意力机制允许模型同时关注输入数据的不同部分和特征。每个“头”都能够学习输入序列的不同表示子空间&#xff0c;从而捕捉到不同类型的依赖关…

霸王茶姬小程序(8月优化版)任务脚本——带教程

文章目录 1.购买服务器地址2.部署教程3. 代码如下4. 如何联系我 1.购买服务器地址 服务器购买地址 https://t.aliyun.com/U/BTQ1HK 若失效&#xff0c;可用地址 https://www.aliyun.com/daily-act/ecs/ecs_trial_benefits?source5176.29345612&userCode49hts92d 2.部署…

Java基础(4)- IDEA

目录 一、Module 1.创建module 2.关闭modue 3.导入module 4.src灰色 二、Package 1.创建package 2.删除package 3.package取名规范 三、类 1.创建类 2.快捷语法 3.HelloWorld 四、IDEA基本设置说明 1.字体 2.提示的快捷键 五、常用快捷键 一、Module 1.创建mod…

SpringData-ElasticSearch入门

文章目录 1、创建demo工程2、application.properties3、Goods 实体类4、EsDemoApplicationTests 测试类5、pom.xml6、查看索引库7、查看单个索引&#xff08;数据库&#xff09;8、从goods索引中检索出符合特定搜索条件的文档&#xff08;或记录&#xff09; 1、创建demo工程 2…

ctfhub-web-SSRF通关攻略

一、内网访问 1.打开ctfhub给的环境地址 2.观察题目 发现让我们访问127.0.0.1下的flag.php 在地址栏后面有一个url参数 ?urlhttp://127.0.0.1/flag.php 提交即可 二、伪协议读取文件 1.打开ctfhub给的环境 2.观察题目 发现让我们读取flag.php文件 读取文件用到的协议是…

mathtype 公式编号 添加章节号 章节编号错乱 解决方法

1 怎么添加编号 左编号方法和右编号一样。 打开word软件,选择mathtype工具,点击右编号以后会打开mathtype软件界面,在mathtype软件界面中对于公式进行编写,编写完成后退出并且保存,就可以完成编号添加。 如果是对已有的公式进行编写的话,则通过ctrl+A进行全文选择,选择…

基于SpringBoot+Vue实现的高校心里辅导(咨询)管理系统设计与实现

本高校心理教育辅导系统的开发基于springboot框架&#xff0c;采用Java技术&#xff0c;同时使用MYSQL数据库对系统数据进行储存&#xff0c;充分保证系统数据的安全性和稳定性。系统根据高校心理教育辅导的需求开发功能模块&#xff0c;实现对信息数据的添加、删除、修改、查询…

前端项目部署到服务器上(nginx)

我这个之前已经部署过项目&#xff0c;所以要进行这个操作 docker imagedocker rm -f nginx //用于强制删除名为“nginx”的容器docker ps //用于列出当前正在运行的Docker容器docker volume -fdocker volume prune //用于删除所有未使用的Docker数据卷&#xff0c;‌释放存…

OpenCV绘图函数(2)绘制圆形函数circle()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 绘制一个圆。 cv::circle 函数用于绘制一个给定中心和半径的简单圆或填充圆。 函数原型 void cv::circle (InputOutputArray img,Point cen…

驱动:mknod-misc 杂项自动

一、杂项设备驱动 #include <linux/init.h> #include <linux/kernel.h> #include <linux/fs.h> #include <linux/module.h> #include <linux/device.h> #include <asm/io.h> #include <asm/string.h> #include <asm/uaccess.h>…

简易指南:迅速构建个性化RAG(Retrieval-Augmented Generation)应用

前面的章节&#xff0c;我们已经完成了可用的基于知识库回答的ai助手&#xff0c;尽管RAG容易上手&#xff0c;但是要真正掌握其精髓却颇有难度&#xff0c;实际上&#xff0c;建立一个的有效的RAG系统不仅仅是将文档放入向量数据库并叠加一个llm模型那么简单&#xff0c;这种方…

心觉:赚钱是修行最快的一种方式

Hi&#xff0c;我是心觉&#xff0c;与你一起玩转潜意识、脑波音乐和吸引力法则&#xff0c;轻松搞定人生挑战&#xff0c;实现心中梦想&#xff01; 挑战日更写作152/1000(完整记录在下面) 公门洞开纳百川 众心逐梦越千山 号召引领潜力绽 心觉潜意识无间 人生就是一场体…

【网络】P2P打洞原理

本文首发于 ❄️慕雪的寒舍 1. 引入 如果你折腾过NAS或者BT下载等等玩意&#xff0c;可能听说过“P2P打洞”这一技术名词。简单来说&#xff0c;P2P打洞可以让我们直接在外网访问内网的设备&#xff0c;从而让没有公网IP的家庭设备也能获得“公网直连”的速度。 比如绿联、极…

ES 根据条件删除文档

随着业务量的增多&#xff0c;es中数据越来越多&#xff0c;但有些数据其实后期并无业务用途&#xff0c;可直接做物理删除&#xff0c;程序里做兼容&#xff0c;但历史每个月的索引里的数据需要处理这部分冗余数据。 es提供_delete_by_query 根据查询条件进行删除的操作&…

呼入的电话通过http接口转接(mod_cti基于FreeSWITCH)

文章目录 前言联系我们配置流程1.呼入路由配置2.呼入安全配置3.配置生效规则4. 动作解析动作说明接口返回说明 5.创建拨号方案并启用 前言 呼叫流程&#xff1a;任意手机呼叫指定的号码&#xff0c;进入到中间件中&#xff0c;然后通过接口转接到对应的坐席分机中。接口作用&a…

警惕!血脂偏高,这些身体信号你不可不知!

在快节奏的现代生活中&#xff0c;高血脂&#xff0c;这个看似“沉默的杀手”&#xff0c;正悄然威胁着越来越多人的健康。它不像感冒发烧那样有明显的症状&#xff0c;却能在不知不觉中侵蚀血管&#xff0c;增加心血管疾病的风险。今天&#xff0c;我们就来揭开高血脂的神秘面…

探索最佳无代码低代码工具:加速 Web 应用开发

Web 应用无处不在。 从用户友好的在线表单到功能强大的企业级解决方案&#xff0c;Web 应用的多样性和复杂性不断增长。 随着低代码无代码技术的发展&#xff0c;构建一个 Web 应用的门槛正在大大降低。 对于刚踏入 Web 开发领域的人员来说&#xff0c;正确的低代码/无代码工…

【AI大模型】提示词(Prompt)全面解析

文章目录 前言前置准备&#xff08;非常重要&#xff09;一、Prompt 提示词介绍1.1 Prompt 的重要性 二、Prompt 提示词元素构成与实践2.1 关键字2.2 上下文2.3 格式要求2.4 实践示例 三、Prompt 提示词编写原理3.1 清晰性3.2 具体性3.3 适应性 四、Prompt 提示词编写常用的分隔…

游戏开发设计模式之装饰模式

目录 装饰模式在游戏开发中的具体应用案例是什么&#xff1f; 如何在Unity中实现装饰模式以动态扩展游戏对象的功能&#xff1f; 装饰模式与其他设计模式&#xff08;如适配器模式、代理模式&#xff09;相比&#xff0c;有哪些优势和劣势&#xff1f; 优势 劣势 与适配器…

错误使用 gretna_GUI_PreprocessInterface>RunBtn_Callback

&#x1f3c6;本文收录于《CSDN问答解惑-专业版》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收…