快排Java

快速排序的复杂度

在这里插入图片描述

快排代码

package leetcode;import java.util.Arrays;public class QuickSort {public static void quickSort(int[] array, int low, int high) {if (low < high) {int pivotIndex = partition(array, low, high);quickSort(array, low, pivotIndex - 1);  // 递归排序左子数组quickSort(array, pivotIndex + 1, high); // 递归排序右子数组}}private static int partition(int[] array, int low, int high) {int pivot = array[high]; // 选择最后一个元素作为基准// high = high;while (low < high){while(low<high && array[low] <= pivot){low++;}array[high] = array[low];while(low<high && array[high] >= pivot){high--;}array[low] = array[high];}array[low] = pivot;return low;}public static void main(String[] args) {int[] arr = {4, 1};int n = arr.length;quickSort(arr, 0, n - 1);System.out.println("Sorted array: ");for (int value : arr) {System.out.print(value + " ");}}
}

对于每一次分区调整,上边的代码有点小问题,但是不影响正确性,

即代码

private static int partition(int[] array, int low, int high) {int pivot = array[high]; // 选择最后一个元素作为基准//也就说,一开始最右边的是相当于空着的//所以一开始要先找左边大于基准的,可以放到high空着的地方while (low < high){while(low<high && array[low] <= pivot){low++;}array[high] = array[low];//相当于现在low这个位置空着//所以需要再从右边找一个比基准小的// 但是每一次都会重复判断highwhile(low<high && array[high] >= pivot){high--;}array[low] = array[high];}array[low] = pivot;return low;}

array[high] = array[low];
while(low<high && array[high] >= pivot){
high–;
}
每一次都会重复判断high,因为上一行代码 array[high] = array[low];
所以array[high] >= pivot 一定成立,我就感觉多了一次判断。
array[high] >= pivot

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

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

相关文章

浙大数据结构:03-树2 List Leaves

这道题我借用了一点上一题的代码思路&#xff0c;这题考察的主要是层序遍历&#xff0c;即用队列来实现&#xff0c;当然此处我依然采用数组模拟队列来实现。 机翻 1、条件准备 map的键存下标&#xff0c;后面值分别存左右子树的下标&#xff0c;没有子树就存-1. head数组只…

Buzzer:一款针对eBPF的安全检测与模糊测试工具

关于Buzzer Buzzer是一款功能强大的模糊测试工具链&#xff0c;该工具基于Go语言开发&#xff0c;可以帮助广大研究人员简单高效地开发针对eBPF的模糊测试策略。 功能介绍 下面给出的是当前版本的Buzzer整体架构&#xff1a; 元素解析&#xff1a; 1、ControlUnit&#xff1a…

Java 后端接口入参 - 联合前端VUE 使用AES完成入参出参加密解密

加密效果&#xff1a; 解密后的数据就是正常数据&#xff1a; 后端&#xff1a;使用的是spring-cloud框架&#xff0c;在gateway模块进行操作 <dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>30…

51单片机-AT24C02(IIC总线介绍及其时序编写步骤)-第一节(下一节实战)

IIC开始通信&#xff08;6大步&#xff09; 我以前的文章也有对基本常用的通信协议讲解&#xff0c;如SPI UART IIC RS232 RS485 CAN的讲解&#xff0c;可前往主页查询&#xff0c;&#xff08;2024.9.12,晚上20&#xff1a;53&#xff0c;将AT24C02存储芯片&#xff0c;掉电不…

charles配置安卓抓包(避坑版)

1. 下载Charleshttps://www.charlesproxy.com/ 2. 安装&#xff0c;疯狂点击下一步即可 3. 注册&#xff1a;打开Charles&#xff0c;选择“Help”菜单中的“Register Charles”&#xff0c;进网站生成密钥&#xff1a;https://www.zzzmode.com/mytools/charles/,将生成的密钥…

【Linux修行路】信号的产生

目录 ⛳️推荐 一、信号的产生 二、产生信号的系统调用 2.1 kill——给指定的进程发送指定的信号 2.2 模拟实现指令 kill 2.3 raise——给调用的进程发送指定的信号 2.4 abort——给调用者发送 6 号信号 三、验证哪些信号不可以被捕捉 四、为什么除0和解引用空指针会给…

【C++】——vector

文章目录 vector介绍vector的使用vector的构造vector迭代器vector空间增减vector增删查改 vector介绍 vector是一个动态数组&#xff0c;可以根据需求变大变小vector支持随机访问vector会自动管理内存分配和释放vector在尾部添加和删除的效率非常高&#xff0c;中间和头部插入较…

Leetcode面试经典150题-134.加油站

解法都在代码里&#xff0c;不懂就留言或者私信 class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {/**如果只有一个加油站&#xff0c;那它本来就在那个为止&#xff0c;0就是它的编号?但是这只是你的想象&#xff0c;题目有个变态规定&#xff0c;自…

GD32/STM32启动过程

GD32/STM32启动过程 文章目录 GD32/STM32启动过程前言一、系统架构二、自举配置三、启动文件四、启动流程总结 前言 本文以STM32F407为例简单介绍其启动过程。 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、系统架构 STM32F407的系统架构如图所…

DRW的公式推导及代码解析

流程 分阶段指定β值 # 根据当前epoch计算使用的beta值idx epoch // 160 # 每160轮epoch切换一次加权系数betas [0, 0.9999] # 两个beta值beta betas[idx] # 根据idx选择beta值 计算有效样本的权重 对权重进行归一化 &#xff08;每类权重值 / 权重总和&#xff09;* …

k8s--pod控制器--1

Pod控制器介绍 Pod是kubernetes的最小管理单元&#xff0c;在kubernetes中&#xff0c;按照pod的创建方式可以将其分为两类&#xff1a; 自主式pod&#xff1a;kubernetes直接创建出来的Pod&#xff0c;这种pod删除后就没有了&#xff0c;也不会重建 控制器创建的pod&#xf…

OpenStack × OceanBase: 打造高可用可扩展的基础设施平台

OceanBase 社区资深总监封仲淹在9月3日参加 OpenInfra 亚洲峰会中&#xff0c;分享了OceanBase与OpenStack的联合解决方案。本文将介绍这一联合方案的技术亮点及其为用户带来的独特价值。 OpenStack长期以来一直是云计算领域的先行者&#xff0c;通过提供强大的开源平台&#x…

前端正确设置资源上下文路径ContextPath(发布目录outDir 、公共基础路径),保证打包部署后站点能正常加载资源。

文章目录 引言I 处理资源上下文路径ContextPathjavascript对象获取上下文路径使用`./` 加载资源文件Vite 的basepublicPath是webpack部署应用包时的基本 URLII 知识扩展:URL的识别2.1 标准的链接格式2.2 URL中的?涵义2.3 URL中的&涵义2.4 传参III #fragment3.1为网页位置…

圆锥曲线练习

设 A ( x 1 , y 1 ) , B ( x 2 , y 2 ) A\left( x_{1}, y_{1} \right), B\left( x_{2}, y_{2} \right) A(x1​,y1​),B(x2​,y2​) l : y k ( x 2 ) l: y k\left( x2 \right) l:yk(x2) 显然 y 0 y0 y0符合题意 当 k ≠ 0 k\neq 0 k0 联立 l l l和 C C C ( k 2 1 2 ) x…

shader 案例学习笔记之偏移

效果 代码 #ifdef GL_ES precision mediump float; #endifuniform vec2 u_resolution; uniform float u_time;vec2 brickTile(vec2 _st, float _zoom){_st * 5.;_st.x step(1., mod(_st.y,2.0)) * 0.5;return fract(_st); }float box(vec2 _st, vec2 _size){_size vec2(0.5)…

【软考中级攻略站】-软件设计师(5)- 软件工程

软件生存周期 什么是软件生存周期&#xff1f; 软件生存周期指的是一个软件从开始构思到最终停止使用&#xff08;或被替换&#xff09;的整个过程。就像人的生命一样&#xff0c;软件也有一个从出生到死亡的过程。 软件生存周期的几个阶段 软件生存周期通常可以分为以下几…

DAY13信息打点-Web 应用源码泄漏开源闭源指纹识别GITSVNDS备份

#知识点 0、Web架构资产-平台指纹识别 1、开源-CMS指纹识别源码获取方式 2、闭源-习惯&配置&特性等获取方式 3、闭源-托管资产平台资源搜索监控 演示案例&#xff1a; ➢后端-开源-指纹识别-源码下载 ➢后端-闭源-配置不当-源码泄漏 ➢后端-方向-资源码云-源码泄漏 …

苹果宣布iOS 18正式版9月17日推送:支持27款iPhone升级

9月10日消息&#xff0c;在苹果秋季发布会结束后&#xff0c; 苹果宣布将于9月17日(下周二)推送iOS 18正式版系统。 苹果官网显示&#xff0c;iOS 18正式版将兼容第二代iPhone SE及之后的所有机型&#xff0c;加上刚发布的iPhone 16系列&#xff0c;共兼容27款iPhone。 iOS 18升…

算法学习攻略总结 : 入门至进阶,通关之路指南

❃博主首页 &#xff1a; <码到三十五> ☠博主专栏 &#xff1a; <mysql高手> <elasticsearch高手> <源码解读> <java核心> <面试攻关> ♝博主的话 &#xff1a; <搬的每块砖&#xff0c;皆为峰峦之基&#xff1b;公众号搜索(码到…

UE中如何制作后处理设置面板

1&#xff09;UE中如何制作后处理设置面板 2&#xff09;Magica Clothes 2插件与Burst编译问题 3&#xff09;UI大小和文本变量 4&#xff09;如何检索直线与网格的所有交点 这是第399篇UWA技术知识分享的推送&#xff0c;精选了UWA社区的热门话题&#xff0c;涵盖了UWA问答、社…