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

排序算法之-快速

算法原理

丛待排序的数列中选择一个基准值,通过遍历数列,将数列分成两个子数列:小于基准值数列、大于基准值数列,准确来说还有个子数列:等于基准值即:
在这里插入图片描述

算法图解

  1. 选出基准元素pivot(可以选择最左侧元素),设置两个指针(Java中可看成是数组索引)left和right,left指向数列最左边的元素,right指向最右侧元素
  2. 进行第一次遍历,先丛right指针开始,让其指向的元素和pivot作比较,大于或等于则指针向左移动一个位置,小于则停止移动,等待left指针移动
  3. 轮到left指针移动,同样先让left指向的元素和pivot做比较,小于或等于则指针向右移动,大于则停止移动
  4. 此时left和right都停止移动,判断left和right是否在同一个位置,否则交换位置元素。
  5. 继续丛2开始,直至left和right相交,将pivot值与left指向的元素进行交换,第一次遍历结束,获得分区指针left。
  6. 再将两个子数列按照1到6的步骤继续执行,直至所有子数列排序完成。
    在这里插入图片描述

算法实现

public class QuickSort {public void sort(int []arr){doSort(arr,0,arr.length-1);}public void doSort(int []arr,int left,int right){if(left >= right){return;}int partitionIndex = partition(arr, left, right);doSort(arr,left,partitionIndex-1);doSort(arr,partitionIndex+1,right);}/*** 右指针先往左移动* @param arr* @param left* @param right* @return*/public int partition(int []arr,int left,int right) {int startIndex = left;int pivot = arr[startIndex];while (left < right) {while (left < right && arr[right] >= pivot) {right--;}while (left < right && arr[left] <= pivot) {left++;}if (left < right) {swap(arr, left, right);}}swap(arr, startIndex, left);return left;}private void swap(int arr[],int i,int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}

测试

  public static void main(String[] args) {int arr[] = {9, 7, 1991, 27, -1, -10, 0,10,9,8,-1,27,-1, 2, 65, -100};new QuickSort().sort(arr);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + "\t");}}

结果

在这里插入图片描述

分区实现2

  /*** 左指针先往右移动* @param arr* @param left* @param right* @return*/public int partition(int []arr,int left,int right){int startIndex = left;int pivot = arr[startIndex];while (left < right) {while (left < right && arr[left] <= pivot) {left++;}while (left < right&&arr[right] >= pivot){right --;}if(left < right){swap(arr,left,right);}}if(arr[left] >= pivot){swap(arr,startIndex,left-1);return left-1;}swap(arr,startIndex,left);return left;}

相关文章:

排序算法之-快速

算法原理 丛待排序的数列中选择一个基准值&#xff0c;通过遍历数列&#xff0c;将数列分成两个子数列&#xff1a;小于基准值数列、大于基准值数列&#xff0c;准确来说还有个子数列&#xff1a;等于基准值即&#xff1a; 算法图解 选出基准元素pivot&#xff08;可以选择…...

[vim]Python编写插件学习笔记2 - 分离

0 环境 Windows 11 22H2gVim82 (D:/ProgramFiles/Vim)Python311 (D:/ProgramFiles/Python311)Vundle v0.10.2 阅读本文前&#xff0c;需要先了解前文: 《[vim]Python 编写插件学习笔记1 - 开始》 1 Python 与 vimscript 分离 前文编写 vim 插件的方式&#xff0c;是将 Pyt…...

【已解决】ModuleNotFoundError: No module named ‘kornia‘

问题描述 Traceback (most recent call last): File "main.py", line 47, in <module> import data_augmentation File "/media/visionx/monica/project/stable_signature/hidden/data_augmentation.py", line 15, in <module> im…...

预览PDF并显示当前页数

这里写目录标题 步骤实例实例效果图 步骤 1.安装依赖 npm install --save vue-pdf2.在需要的页面&#xff0c;引入插件 import pdf from vue-pdf3.使用 单页pdf可以直接使用 <pdf :src"获取到的pdf地址"></pdf>多页pdf通过循环实现 html标签部分 &l…...

阿里云优惠券介绍、作用、领取入口及使用教程

阿里云是阿里巴巴集团倾力打造的云计算品牌&#xff0c;提供丰富多样的云计算产品及服务&#xff0c;为了吸引用户&#xff0c;阿里云经常推出各种优惠活动&#xff0c;其中就包括阿里云优惠券的发放。本文将为大家详细介绍阿里云优惠券的作用、领取入口以及使用教程。 一、阿里…...

Shell编程--流程控制

目录 1.条件结构1.1.文件测试(字符串)1.2.字符串比较1.3.数字条件比较1.4.文件条件判断 2.if多条件判断3.case语句 1.条件结构 测试&#xff1a;test 条件 条件为真返回 0&#xff0c;条件为假返回 1 语法&#xff1a;[ 条件 ] test 条件能够理解以下类型的表达式 1.1.…...

设计模式-模板方法模式(Template Method)

设计模式-模板方法模式&#xff08;Template Method&#xff09; 一、模板方法模式概述1.1 什么是模板方法模式1.2 简单实现模板方法模式1.3 使用模板方法模式的注意事项 二、模板方法模式的用途三、模板方法模式实现方式3.1 抽象类中定义模板方法&#xff0c;子类实现具体方法…...

远程登录Linux方法(Linux平台相互远程;Windows远程登录Linux、远程编码、文件传输;无法远程登录的问题解决;c程序的编译)

在实际使用Linux系统过程中我们不可避免的需要远程登录Linux&#xff0c;这是因为未来大家使用Linux服务器的时候你所对应的那台Linux服务器不一定提供界面(服务器可能在外地)。本篇将会介绍远程登录Linux的方法。 文章目录 1. SSH介绍2. Linux平台相互远程及文件传输2.1 Linux…...

macOS 13.6 及后续系统安装 Asahi Linux 将破坏引导

导读Asahi Linux 是一个致力于为 Apple Silicon 设备带来 Linux 支持的项目&#xff0c;日前有用户反馈称&#xff0c;若在相关设备上安装了 macOS 13.6-14&#xff0c;再安装 Asahi Linux &#xff0c;就会导致系统引导失败&#xff0c;出现“黑屏”情况。 目前 Asahi Linux 项…...

Python武器库开发-flask篇之flask框架的安装(二十一)

Flask介绍 Flask是一个基于Python开发并且依赖jinja2模板和Werkzeug WSGI服务的一个微型框架&#xff0c;对于Werkzeug本质是Socket服务端&#xff0c;其用于接收http请求并对请求进行预处理&#xff0c;然后触发Flask框架&#xff0c;开发人员基于Flask框架提供的功能对请求进…...

【CASS精品教程】打开cass提示base.dcl未找到文件的解决办法

打开cass 7.1时提示base.dcl未找到文件的解决办法。 文章目录 一、问题描述二、解决办法 一、问题描述 系统上安装了cad2006cass7.1&#xff0c;cass软件可以正常打开&#xff0c;但是在使用屏幕菜单绘制地图时&#xff0c;选择一个工具&#xff0c;提示base.dcl未找到文件&am…...

[vim]Python编写插件学习笔记3 - 命令行参数

0 环境 Windows 11 22H2gVim82 (D:/ProgramFiles/Vim)Python311 (D:/ProgramFiles/Python311)Vundle v0.10.2 阅读本文前&#xff0c;需要先了解前文&#xff1a; 《[vim]Python 编写插件学习笔记1 - 开始》 《[vim]Python 编写插件学习笔记2 - 分离》 1 前提说明 由于本…...

【仙逆】王林400年晋升元婴,复仇藤化元杀尽藤姓,高老畏罪自裁

Hello,小伙伴们&#xff0c;我是小郑继续为大家深度解析国漫资讯。 深度爆料仙逆第10集剧情解析&#xff0c;高启明&#xff0c;缥缈宗的元婴初期老祖&#xff0c;一生潜心研究推演之术&#xff0c;洞察先机&#xff0c;乃是宗门之人的精神支柱。藤化元曾为寻找王林父母所在之…...

云原生实战课大纲

1. 云原生是什么 原生应用&#xff08;java,pyrhon&#xff09; 上云的过程应用上云遇到的问题1.微服务的拆分 微服务的访问关系应用的架构云原生适合什么样的人去学具备什么样的前提条件云原生要学习什么docker k8s devlops server mesh jks k8s监控吧自己的微服务部署上…...

数据湖架构

数据湖架构介绍 数据湖&#xff08;Data Lake&#xff09;是一个存储大量结构化和非结构化数据的集中式数据存储库。 与传统的数据仓库不同&#xff0c;数据湖采用扁平化结构&#xff0c;将数据存储在原始形式下&#xff0c;不需要进行预处理或转化。这使得数据湖能够同时支持…...

Zabbix 5.0部署(centos7+server+MySQL+Apache)

环境 系统IPZABBIX版本主机名centos7192.168.231.2195.0zabbix-server 安装zabbix 我选择版本是zabbix-5.0 zabbix的官网是Zabbix :: The Enterprise-Class Open Source Network Monitoring Solution 安装Zabbix软件源 rpm -Uvh https://repo.zabbix.com/zabbix/5.0/rhel/7/…...

YOLO改进系列之注意力机制(CloAttention模型介绍)

CloAttention来自清华大学的团队提出的一篇论文CloFormer&#xff0c;作者从频域编码的角度认为现有的轻量级视觉Transformer中&#xff0c;大多数方法都只关注设计稀疏注意力&#xff0c;来有效地处理低频全局信息&#xff0c;而使用相对简单的方法处理高频局部信息。很少有方…...

openssl+AES开发实例(linux)

文章目录 一、AES介绍二、AES原理三、AES开发实例 一、AES介绍 AES&#xff08;Advanced Encryption Standard&#xff09;是一种对称密钥加密标准&#xff0c;它是一种对称加密算法&#xff0c;意味着相同的密钥用于加密和解密数据。AES 是 NIST&#xff08;美国国家标准与技…...

FreeRTOS源码阅读笔记3--queue.c

消息队列可以应用于发送不定长消息的场合&#xff0c;包括任务与任务间的消息交换&#xff0c;队列是 FreeRTOS 主要的任务间通讯方式&#xff0c;可以在任务与任务间、中断和任务间传送信息&#xff0c;发送到 队列的消息是通过拷贝方式实现的&#xff0c;这意味着队列存储…...

云原生Kubernetes系列 | 通过容器互联搭建wordpress博客系统

云原生Kubernetes系列 | 通过容器互联搭建wordpress博客系统 通过容器互联搭建一个wordpress博客系统。wordpress系统是需要连接到数据库上的,所以wordpress和mysql的镜像都是需要的。wordpress在创建过程中需要指定一些参数。创建mysql容器时需要把mysql的数据保存在宿主机本…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...