当前位置: 首页 > 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…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

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

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

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

在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…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...