当前位置: 首页 > 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的数据保存在宿主机本…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

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

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

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...