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

Java 快速排序

快速排序(Quicksort)是一种高效的排序算法,采用分治法(Divide and Conquer)的策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个子序列。以下是用Java实现的快速排序算法:

public class QuickSort {  // 主方法,用于测试快速排序  public static void main(String[] args) {  int[] array = {10, 7, 8, 9, 1, 5};  int n = array.length;  System.out.println("排序前的数组:");  printArray(array);  quickSort(array, 0, n-1);  System.out.println("排序后的数组:");  printArray(array);  }  // 快速排序方法  public static void quickSort(int[] array, int low, int high) {  if (low < high) {  // 找到分区点  int pi = partition(array, low, high);  // 递归地对左右子数组排序  quickSort(array, low, pi - 1);  quickSort(array, pi + 1, high);  }  }  // 分区方法  public static int partition(int[] array, int low, int high) {  int pivot = array[high];  // 选择最右边的元素作为枢轴  int i = (low - 1);  // i是较小元素的索引  for (int j = low; j < high; j++) {  // 如果当前元素小于或等于枢轴  if (array[j] <= pivot) {  i++;  // 交换array[i]和array[j]  int temp = array[i];  array[i] = array[j];  array[j] = temp;  }  }  // 交换array[i + 1]和array[high] (或枢轴)  int temp = array[i + 1];  array[i + 1] = array[high];  array[high] = temp;  return i + 1;  }  // 打印数组方法  public static void printArray(int[] array) {  int n = array.length;  for (int i = 0; i < n; ++i) {  System.out.print(array[i] + " ");  }  System.out.println();  }  
}

代码解释

  1. 主方法 (main):
    • 创建一个数组并输出排序前的数组。
    • 调用 quickSort 方法对数组进行排序。
    • 输出排序后的数组。
  2. 快速排序方法 (quickSort):
    • 如果 low 小于 high,则进行排序。
    • 调用 partition 方法获取分区点 pi
    • 递归地对分区点前后的子数组进行排序。
  3. 分区方法 (partition):
    • 选择数组的最后一个元素作为枢轴。
    • 初始化较小元素的索引 i
    • 遍历数组,如果当前元素小于或等于枢轴,则交换 array[i] 和 array[j]
    • 遍历完成后,将枢轴放到正确的位置(即 i + 1),并返回该位置。
  4. 打印数组方法 (printArray):
    • 遍历数组并打印每个元素。

注意事项

  • 枢轴的选择可以优化,例如随机选择枢轴或选择数组的中间元素作为枢轴,以减少最坏情况(例如已经有序的数组)下的性能下降。
  • 快速排序的空间复杂度主要是递归调用栈,最坏情况下为 O(n),但平均情况下较好。
  • 快速排序的时间复杂度平均情况下为 O(n log n),最坏情况下为 O(n^2)。

相关文章:

Java 快速排序

快速排序&#xff08;Quicksort&#xff09;是一种高效的排序算法&#xff0c;采用分治法&#xff08;Divide and Conquer&#xff09;的策略来把一个序列分为较小和较大的两个子序列&#xff0c;然后递归地排序两个子序列。以下是用Java实现的快速排序算法&#xff1a; publi…...

51单片机的智能衣柜【proteus仿真+程序+报告+原理图+演示视频】

1、主要功能 该系统由AT89C51/STC89C52单片机LCD1602显示模块光照传感器时钟模块温湿度传感器继电器按键、LED等模块构成。适用于智能衣柜、智能衣橱、紫外线定时消毒等相似项目。 可实现功能: 1、LCD1602实时显示北京时间、温湿度和开关门状态 2、时钟模块DS1302采集时间 …...

SAP_FI_表ACDOCA取代的表

在 SAP S/4HANA 系统中&#xff0c;ACDOCA&#xff08;通用分录表&#xff0c;Universal Journal&#xff09;引入了全新的数据结构&#xff0c;取代了原先 ERP 系统中多个财务和控制模块的表。ACDOCA 通过一个单一表格整合了财务会计&#xff08;FI&#xff09;和管理会计&…...

论文《OneLLM:One Framework to Align All Modalities with Language》

&#xff08;没有会员只有做100个节点&#xff0c;mindmaster金主爸爸可不可以给我一个会员啊啊啊啊呜呜呜~&#xff09; 欣赏论文的图和表&#xff1a; 表中作者将自己的模型那一行选择灰色作为背景&#xff0c;更加凸显自己的数据&#xff0c;另外对于最好的结果用加粗黑体…...

Ubuntu 22.04.4 LTS更换下载源

方法1&#xff1a;使用图形界面更换下载源 1. 打开软件和更新应用 2. 在Ubuntu 软件标签中&#xff0c;点击“下载自”旁边的下拉菜单&#xff0c;选择“其他” 3. 点击“选择最佳服务器”来自动选择最快的服务器 4. 选择服务器 5. 确定并关闭窗口&#xff0c;系统会提示您重新…...

html嵌入百度地图

html嵌入百度地图 key地址 https://lbsyun.baidu.com/apiconsole/key#/home &#xff0c;点进去注册应用、然后复制key换掉即可显示地图 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>百度地图搜索…...

【网络】详解TCP协议中的可靠传输

【网络】详解TCP协议中的可靠传输 一. TCP协议段格式二. 确认应答——确保可靠性的核心机制1.确保时序2.确保发送方知道数据是否被对方接收到 三. 超时重传1. 发送的数据丢包2. ACK报文丢失 一. TCP协议段格式 TCP协议段格式相比UDP要复杂很多&#xff0c;很多内容需要我们了解…...

【Python实例】Python读取并绘制nc数据

【Python实例】Python读取并绘制nc数据 准备&#xff1a;安装netCDF库等读取nc数据相关信息绘制图形利用basemap绘图 参考 准备&#xff1a;安装netCDF库等 以【1960-2020年中国1km分辨率月降水数据集】中2020年降水为例。 先在Panopoly中查看数据属性&#xff0c;如下&#…...

swift使用llama3.2-vision微调xray数据集

1.数据格式 [{"query": "通过这张胸部X光影像可以诊断出什么?","response": "根据X射线图像,心脏大小正常,肺部看起来很清晰。已经排除了肺炎、积液、水肿、气胸、腺病、结节或肿块的存在。该发现表明一切正常。换句话说,总体印象是胸…...

学习小课堂

1.多服务节点下Session-Cooki方案如何做&#xff1f; Session-Cookie 方案在单体环境是一个非常好的身份认证方案。但是&#xff0c;当服务器水平拓展成多节点时&#xff0c;Session-Cookie 方案就要面临挑战了。 举个例子&#xff1a;假如我们部署了两份相同的服务 A&#x…...

stm32学习笔记-RTC实时时钟

文章目录 一、RTC基础知识1.1 RTC简介1.2 RTC的晶振 二、stm32的RTC2.1 RTC和后备寄存器2.2 stm32 RTC结构框图及特性 三、stm32 RTC编程2.1 RTC初始化2.2 RTC控制程序 一、RTC基础知识 1.1 RTC简介 实时时钟的缩写是RTC(Real_Time Clock)。RTC 是集成电路&#xff0c;通常称…...

简历中的期望薪资怎么定?

在简历中撰写期望薪资时&#xff0c;既要体现你的价值认知&#xff0c;又要保持一定的灵活性和开放性&#xff0c;以便在后续的面试和薪资谈判中留有余地。以下是一些撰写期望薪资的合理方法&#xff1a; 一、明确薪资范围 1.市场调研&#xff1a; 在撰写期望薪资前&#xf…...

MySQL 中的 GROUP BY 使用

MySQL 中的 GROUP BY 使用指南 GROUP BY 是 SQL 中一个非常强大的语句&#xff0c;用于将查询结果按指定的列进行分组&#xff0c;并对每个分组执行聚合函数。它常常与聚合函数&#xff08;如 COUNT、SUM、AVG、MIN 和 MAX&#xff09;结合使用&#xff0c;以生成汇总信息。 …...

在 ubantu 20.04 云服务器上基于 bochs 编译 linux0.11

安装 bochs 将下面的命令全部执行一遍&#xff1a; sudo apt-get install build-essential sudo apt-get install xorg-dev sudo apt-get install bison sudo apt-get install g 我们区官网下载一下bochs的源码&#xff1a;bochs下载 这里我下载好了bochs2.6.8 这个版本的…...

docker-compose安装部署和使用

docker-compose 是用于定义和运行多容器 Docker 应用程序的工具。通过 Compose&#xff0c;您可以使用 YML 文件来配置应用程序需要的所有服务。然后&#xff0c;使用一个命令&#xff0c;就可以从 YML 文件配置中创建并启动所有服务 1.docker-compose安装 github上下载二进制文…...

Java之静态

静态&#xff1a; 使用 static 关键字声明的成分属于类本身&#xff0c;而不是类的任何特定对象的实例。这意味着你可以在创建类的任何对象之前访问它们。 静态变量&#xff1a; 静态变量&#xff08;也称为类变量&#xff09;是被类的所有实例共享的变量。无论你创建多少对象…...

PCB缺陷检测数据集 xml 可转yolo格式 ,共10688张图片

PCB缺陷检测数据集&#xff08;yolov5,v7,v8&#xff09; 数据集总共有两个文件夹&#xff0c;一个是pcb整体标注&#xff0c;一个是pcb部分截图。 整体标注有6个分类&#xff0c;开路&#xff0c;短路等都已经标注&#xff0c;标注格式为xml&#xff0c;每个文件夹下有100多张…...

【linux开发-驱动】-设备树

一、什么是设备树 描述设备树的文件叫做DTS&#xff08;Device Tree Source&#xff09;&#xff0c;采用树形结构描述板级设备&#xff0c;也就是开发板上的设备信息&#xff0c;比如IIC接口上接了那些设备&#xff0c;内存基地址等 树的主干就是系统总线&#xff0c;枝干就…...

不动产证ocr识别场景解析、房产证识别API

不动产证OCR识别、房产证识别接口是通过光学字符识别技术&#xff08;OCR&#xff09;从不动产证书的图像或扫描件中自动提取关键信息的技术应用。该场景的主要目标是提高信息录入的效率&#xff0c;减少人工输入的错误&#xff0c;并能自动化处理大量不动产证书、房产证的数据…...

gpg 密钥生成、导入、导出、自动输入密码

目录 一、系统环境 二、常用命令&#xff08;以签名密钥为例&#xff09; &#xff08;1&#xff09;生成密钥 &#xff08;2&#xff09;列出私钥 &#xff08;3&#xff09;列出公钥 &#xff08;4&#xff09;导出公钥 &#xff08;5&#xff09;导出私钥 &#xff…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

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

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

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...