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

【JAVA】快速排序

快排,和冒泡排序一样,是同一类型的排序,都是交换排序

交换,涉及在遍历中比较,然后相互交换元素

冒泡排序是根据趟数两两比较,边比较边交换,快排也一样,不过冒泡是以顺序表的格式进行的,而快排则是建立在二叉树的基础上来完成遍历交换的~(个人理解)

快排有很多个版本,快速排序是一位名hoare的人发明的,快排有很多个版本,什么horae版本,什么挖坑法,什么双指针法,这里我们介绍horae版本,至于挖坑法和双指针以后有机会再说~


已经说了,快排基于二叉树的规则来进行排序,那么具体是怎么样的呢?

比如说我们先搞一个无序数组,然后定义left和right分别是数组的头尾下标

然后定义一个基准值  key  这个key  是用来划分数组的,当遍历交换完一次后,key下标所对应的值会在这个数组的某个位置,但是key左边的元素都会比key下标对应的元素小,key左边的元素都会比key下标对应的元素值要大,这就很类似于二分查找的时候的划分一样~

那具体是怎么样遍历和划分的呢?下面让老衲给你画张图即可

 

 下面我来解说一下第一轮的过程,首先给出了一个无序数组,把6设置为基准,然后存一份,接着right开始减减,遇到比6小的就停下来,所以right先减到了3后,停下不动,此时3比6这个基准小,然后right不动了,开始轮到left++,left的目的是寻找比基准6大的值,所以left++到了7,就停下,此时left对应的7比基准6大,接着把right的3和left的7开始交换,交换后left对应3,right对应7,接着right接着开始往下减减,寻找比基准6小的值,当减到4的时候right停止不动,然后接left开始++,寻找比6大的值,一直++到right,没有再比6大值,并且此时left和right相遇,暗示着第一轮循环结束,此时left和right相遇后,把它们相遇下标的值,也就是4,开始和最开始的基准,也就是下标为0的值,也就是6,开始交换:完成交换后,你会发现此时6的左边都是比6小的数,6的右边都是比6大的数,接着根据6所在的位置,开始划分成两部分,一部分比6小,一部分比6大

划分好后,我们现在只看比6小的部分,比6大的部分同理,看懂比6小的部分就行了

划分后,我们看比6小的 把它当做一个新数组  值 为  4   2   3 

然后根据上面的过程再来一遍,我们把这个数组的0下标元素4看作基准值,然后right对应3,我们开始right--,我们发现此时right的3就是比4小的,所以不动,接着left开始++,找比4大的,一直++到3,没发现比4大的,此时left和right又相遇了,接着再次划分,只有比4小的部分,没有比4大的部分了,那么我们就划分出比4小的部分

划分出3  2  后,我们按照刚才的过程再来一遍,把3看作基准,right--找比3小的,left++找比3大的,直到left和right再次相遇,然后再划分

一直到最后只剩下一个节点2的时候,就完成了遍历,接着返回,没错,就是递归的返回,所以快排要基于二叉树加上递归来实现,嘻嘻~~~


下面展示代码,再说说细节~

public class 快排 {public static void main(String[] args) {int[] arr = {3,5,2,1,43,33,22,64,74,25,13,27,98,56,100,21,7};quickSort(arr);for(int x : arr){System.out.print(x + " ");}}public static void quickSort(int[] array){quick(array,0,array.length-1);}private static void quick(int[] array, int left, int right) {//递归结束条件:这里代表只有一个根   大于号:有可能没有子树  1  2  3   4  1为基准,pivot-1就越界了if(left >= right){return;}int pivot = partition(array, left, right);quick(array,left,pivot-1);quick(array,pivot+1,right);}public static int partition(int[] array,int start, int end){int i = start;//这里存开始时基准的下标,为了循环结束后,相遇值和基准值交换时能找到基准值的下标int key = array[start];//这是基准while (start < end){while (start < end && array[end] >= key){end--;}while (start < end && array[start] <= key){start++;}swap(array,start,end);}//到这里s和e相遇,把相遇值和基准值交换swap(array,start,i);return start;//返回基准下标}public static void swap(int[] array, int n, int m){int temp = array[n];array[n] = array[m];array[m] = temp;}}

写快排就3个主要方法,一个是交换swap,一个是找基准partition,一个是递归过程quick方法,递归直到left >= right 的时候返回~


第一个方法quick是递归用的,主要是划分数组的功能,返回条件是left >= right

假如你的数组是1 2 3 4的话,我们让第一个元素为基准,如果要划分的话,只能划分比1大的部分,方法里面又会自动划分比1小的部分,也就是基准下标减一,那么就越界了


为什么要right先动,而不是left先动,那是因为我们以left为基准,如果left先动,划分好后,你会发现基准左边的值存在比基准大的值,而我们的策略是基准左边比基准小,基准右边比基准大~


partition方法里面有一个大while包含着两个小while,小while是独立的while,

所以要加上start < end

同时&&后面的array【end】 >= key, 为什么要是等于呢?如果不等于,假如你的数组头和尾相同

比如说   3  7 5  8  4   3,就会出现死循环了,3不大于3,而是等于3~


ok到这里就结束战斗了,老衲要去睡觉了~

相关文章:

【C++音视频开发】初级篇 | RGB与YUV

前言 本专栏将不间断更新有关C音视频开发的内容&#xff0c;其中有初级篇、中级篇与高级篇的内容&#xff0c;包括但不限于音视频基础、FFmpeg实战、QT、流媒体客户端、流媒体服务器、WebRTC实战、Android NDK等等。是博主花了将近5000元购买的课程中的知识点&#xff0c;其中…...

Java反射04:获取运行时类的属性结构及其内部结构

文章目录获取运行时类的属性结构及其内部结构新建测试类1.获取每一个Field&#xff08;属性&#xff09;2.获取运行时类的方法结构3.获取运行时类的构造器4.获取当前运行时所继承的父类和接口5.获取当前运行时类的注解、包、泛型获取运行时类的属性结构及其内部结构 通过反射获…...

qsettings 读写注册表

qsettings简单的实现一个注册表读写操作&#xff0c;记录程序中需要保存的信息。使用qsettings声明对象之前&#xff0c;需要指明qsettings的组织名和应用名&#xff0c;分别利用QCoreApplication::setOrganizationName()和QCoreApplication::setApplicationName()来指定组织名…...

【JavaScript高级进阶】构造函数和原型,学会prototype

目录 前言 1.构造函数和原型 1.1使用prototype解决内存浪费的问题 1.2constructor构造函数构造器构造函数 2.原型链 2.1js中成员查找规则 2.2原型对象this指向 2.3扩展内置对象 3.call作用 4.继承 4.1利用原型对象继承 写在最后 前言 哈喽哈喽大家好&#xff0c;因为…...

【学生个人网页设计作品】使用HMTL制作一个超好看的保护海豚动物网页

&#x1f389;精彩专栏推荐 &#x1f4ad;文末获取联系 ✍️ 作者简介: 一个热爱把逻辑思维转变为代码的技术博主 &#x1f482; 作者主页: 【主页——&#x1f680;获取更多优质源码】 &#x1f393; web前端期末大作业&#xff1a; 【&#x1f4da;毕设项目精品实战案例 (10…...

CodeForces - 545E Paths and Trees 最短路建树

题目链接&#xff1a;点击查看 Little girl Susie accidentally found her elder brothers notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to a…...

【工具使用】Visual Studio Code远程调试

VS Code的其中一个关键的特征就是它极好的调试支持。VS Code的内置调试器帮助加速你的编辑、编译和调试循环。 调试扩展 VS Code有Node.js运行的内置的调试支持&#xff0c;并且能够调试Java脚本或者任何其他可以转译为JavaScript的语言。为了调试其他语言&#xff08;包括P…...

ADB学习笔记

简介&#xff1a; ADB的全称为Android Debug Bridge&#xff08;调试桥&#xff09;&#xff0c; 它是一个客户端-服务器端程序&#xff0c;其中客户端是你用来操作的电脑, 服务器端是android设备。作用显而易见&#xff0c;能方便我们在PC上对手机进行调试的一些工作。 原理…...

http load介绍

前几天工作中要对项目的接口做简单压测&#xff0c;就使用了http load做了简单测试&#xff0c;下面介绍一下这款工具的使用说明。简介&#xff1a;http_load是基于linux平台的性能测试工具&#xff0c;它体积非常小&#xff0c;仅100KB。它以并行复用的方式运行&#xff0c;可…...

Linux shell脚本之回顾及实用笔记

一、前言 我们从事运维的小伙伴,除了自动化运维外,在没有自动化条件下,借助shell脚本/Python脚本来提升运维效率,无疑是一个必选项,当前也可以自建自动化运维平台,我们这里还是以Linux shell脚本为主,来汇总一些常用的运维脚本,对于有基础的同学,也随本文一起回顾下相…...

TestNG使用总结

TestNG简介&#xff1a; TestNG是一个测试框架&#xff0c;其灵感来自JUnit和NUnit&#xff0c;但同时引入了一些新的功能&#xff0c;使其功能更强大&#xff0c;使用更方便。 TestNG相较于Junit的优点&#xff1a; 可指定执行顺序&#xff0c; dependsOnMethods 属性来应对…...

面向对象编程的弊端

英文原文&#xff1a;What’s Wrong with OOP and FP 我不理解为什么人们会对面向对象编程和函数式编程做无休无止的争论。就好象这类问题已经超越了人类智力极限&#xff0c;所以你可以几个世纪的这样讨论下去。经过这些年对编程语言的研究&#xff0c;我已经清楚的看到了问题…...

flex 计算指定日期是本年度第几周

/** * 计算指定日期是本年度第几周 *传日年月日&#xff0c;返回number */ private function weekOfYear(yyyy:Number,mm:Number,dd:Number):Number{ var myDate:Date new Date(yyyy, mm - 1, dd); var startDate:Date new Date(yyyy,0,1); v…...

SpringCloud Zuul(四)之工作原理

一、筛选器概述 Zuul的中心是一系列过滤器&#xff0c;这些过滤器能够在HTTP请求和响应的路由期间执行一系列操作。 以下是Zuul过滤器的主要特征&#xff1a; 类型&#xff1a;通常定义路由流程中应用过滤器的阶段&#xff08;尽管它可以是任何自定义字符串&#xff09;执行…...

[CSS]圆角边框与阴影

前言 系列文章目录&#xff1a; [目录]HTML CSS JS 根据视频和PPT整理视频及对应资料&#xff1a;HTML CSS 老师笔记&#xff1a; https://gitee.com/xiaoqiang001/html_css_material.git视频&#xff1a;黑马程序员pink老师前端入门教程&#xff0c;零基础必看的h5(html5)css3…...

Google Swift 与 DC 传输

网络拥塞&#xff0c;默认指转发节点出现了严重的排队现象&#xff0c;甚至队列溢出而丢包。、 但接收端也是一个统计复用系统(通用 OS 均为统计复用系统&#xff0c;比如 Linux)&#xff0c;但凡统计复用系统就是潜在拥塞点&#xff0c;即可套用排队论模型。 人们很少将最后…...

webservice学习记录笔记(一)

一、先理解什么是服务 现在的应用程序变得越来越复杂&#xff0c;甚至只靠单一的应用程序无法完成全部的工作。更别说只使用一种语言了。 写应用程序查询数据库时&#xff0c;并没有考虑过为什么可以将查询结果返回给上层的应用程序&#xff0c;甚至认为&#xff0c;这就是数…...

spring Cloud微服务 security+oauth2认证授权中心自定义令牌增强,并实现登录和退出

文章目录认证授权中心自定义令牌增强自定义认证端点返回结果登录逻辑调整&#xff0c;增强令牌返回参数测试验证用户微服务构建配置类构建相关实体类登录退出登录在之前的博客我写了 SpringCloud整合spring security oauth2Redis实现认证授权&#xff0c;本文对返回的token实现…...

接口测试那些事儿

什么是接口&#xff1f; 首先&#xff0c;在讲接口测试之前&#xff0c;我们先要搞清楚接口类型的概念。 接口&#xff1a;可能是系统与系统&#xff08;包括服务与服务&#xff09;之间的调用&#xff0c;像A系统&#xff08;服务&#xff09;给B系统&#xff08;服务&#x…...

CodeForces - 1084C The Fair Nut and String 思维

The Fair Nut found a string s. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences p1,p2,…,pk , such that: For each i (1≤i≤k), spi a.For each i(1≤i<k), there is…...

Gym - 101986B Parallel Lines dfs暴力

链接&#xff1a;点击查看 题意&#xff1a;偶数个点&#xff0c;两点可连成一条线&#xff0c;求平行线最大对数 题解&#xff1a;当时想的时候傻逼了&#xff0c;想成了每次选两个点就是16*15/2 * 14*13/2 ..... 其实不需要这样&#xff0c;因为每个点必须要匹配一个的&…...

POJ - 2406 Power Strings next数组应用循环节

题目链接&#xff1a;点击查看 Language:Default Power Strings Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 61784 Accepted: 25534Description Given two strings a and b we define a*b to be their concatenation. For example, if a "abc" and…...

CodeForces - 545D Queue 贪心 排序

题目链接&#xff1a;点击查看 Little girl Susie went shopping with her mom and she wondered how to improve service quality. There are n people in the queue. For each person we know time ti needed to serve him. A person will be disappointed if the time he …...

Jmeter访问HTTPS请求

公司最近在搞全站HTTPS改造&#xff0c;进一步提高网站的安全性&#xff0c;防止运营商劫持。那么&#xff0c;改造完成后&#xff0c;所有前后端的URL将全部为https。 So &#xff0c;研究下怎么用Jmeter访问https请求呢。 其实很简单&#xff0c; 第一步在jmeter中创建HTT…...

python导入安装包

主要分两种方式&#xff1a;在线安装和离线安装 在线安装 因为我公司开发是在云桌面&#xff0c;里面是没有外网的。之前是只能离线安装&#xff0c;后面搭了一个内部镜像环境。 1.添加配置文件进行换源 2.检查requirements.txt配置 3.直接使用pycahrm工具install 换源 …...

HDU - 6188 Duizi and Shunzi 贪心

Nike likes playing cards and makes a problem of it. Now give you n integers, ai(1≤i≤n) We define two identical numbers (eg: 2,2) a Duizi, and three consecutive positive integers (eg: 2,3,4) a Shunzi. Now you want to use these integers to form Shunzi and …...

JSON相关知识点

JSON是工作中经常会遇到的一种数据结构&#xff0c;下面来讲讲与他相关的一些知识点。 JSON简介&#xff1a; JSON: JavaScript Object Notation(JavaScript 对象表示法) JSON 是存储和交换文本信息的语法,类似 XML。 JSON 比 XML 更小、更快&#xff0c;更易解析。 JSONObj…...

每天五分钟机器学习:超平面分离定理和凸优化

凸集和凸函数 在点集拓扑学与欧几里得空间中,凸集是一个点集,其中每两点之间的直线上的点都落在该点集中。如下所示: 函数任意两点(x,f(x))和(y,f(y))连线上的值大于(x,y)区间内任意一点m的值f(m),那么这个函数就是一个凸函数: 超平面分离定理 空间中存在两类样本,…...

数据中心典型测试场景浅析

数据中心概述 数据中心泛指拥有众多服务器的大型机房&#xff0c;通过利用通信运营商已有的互联网通信线路、带宽资源&#xff0c;建立标准化的数据中心机房环境&#xff0c;具有运行速度快、存储量大、安全性高等特点。数据中心东西向流量的占比更大&#xff0c;传统的园区网…...

2022学年第一学期郑州大学ACM招新赛选拔赛

A SW的与众不同数组 — 签到 一共n个数&#xff0c; 用set无重复值的性质统计一下有几个不同的数&#xff0c;记为 res n - res 如果是偶数 每次删除两个刚好可以&#xff0c;如果是奇数需要再删除一个不重复的数完成对应操作 #include <iostream> #include <set>…...

牛客网 Applese 走方格

题目链接&#xff1a;点击查看 题解&#xff1a;我们容易发现到当n,m都为奇数时&#xff0c;是回不到原点的&#xff0c;因为你无论哪个方向走一去一回就是两步&#xff0c;所以n和m必然有一个偶数&#xff0c;那至于我们怎么走呢&#xff0c;看下图&#xff0c;注意的是n1,m2…...

mysql重置Root密码

方法一: 在my.ini的[mysqld]字段加入&#xff1a; skip-grant-tables 重启mysql服务&#xff0c;这时的mysql不需要密码即可登录数据库 然后进入mysql mysql>use mysql; mysql>更新 user set passwordpassword(新密码) WHERE Userroot; mysql>flush privileges; 运…...

C · 初阶 | 循环语句

啊我摔倒了..有没有人扶我起来学习.... &#x1f471;个人主页&#xff1a;《CGod的个人主页》\color{Darkorange}{《CGod的个人主页》}《CGod的个人主页》交个朋友叭~ &#x1f492;个人社区&#xff1a;《编程成神技术交流社区》\color{Darkorange}{《编程成神技术交流社区》…...

idea常用技巧收集

idea相比eclipse的优点我在这里就不赘述了&#xff0c;更多参考&#xff1a;idea官网,本文重点讲下自己在idea使用过程中常用的一些技巧&#xff0c;以后随时更新…… 主要分成三大块&#xff1a; 1. 系统设置 2. 快捷键 3. 其他设置 系统设置 主题风格设置&#xff1a;默…...

深入理解spark高阶算子combineByKey

今天来详细说说spark中的一个比较底层的算子combineByKey。 熟悉spark的朋友应该知道&#xff0c;spark里面有很多类型的算子&#xff0c;有些比较基础&#xff0c;什么map&#xff0c;filter&#xff0c;可能看一眼就会了&#xff0c;有些稍微复杂点&#xff0c;但是也不难懂…...

架构设计 例子和实践 系统设计说明书

架构设计 例子和实践 系统设计说明书(架构、概要、详细)目录结构演进架构中的领域驱动设计Web架构设计经验分享软件架构设计从MVC框架看MVC架构的设计领域驱动设计(Domain Driven Design)参考架构详解关于垂直切分Vertical Sharding的粒度企业应用集成与开源ESB产品ServiceMix和…...

想要玩转实现负载均衡,你知道这些吗?

转载自 想要玩转实现负载均衡&#xff0c;你知道这些吗&#xff1f; 一、前言 互联网早期&#xff0c;业务流量比较小并且业务逻辑比较简单&#xff0c;单台服务器便可以满足基本的需求&#xff1b;但随着互联网的发展&#xff0c;业务流量越来越大并且业务逻辑也越来越复杂&…...

算法 - 里程表故障

题目描述 You are given a car odometer which displays the miles traveled as an integer. The odometer has a defect, however: it proceeds from the digit 2 to the digit 4 and from the digit 7 to the digit 9, always skipping over the digit 3 and 8. This defect…...

初识spring RestTemplate

《spring实战》读书笔记之初识spring RestTemplate。首先需要先了解下什么是REST。 REST&#xff1a;官方解释&#xff0c;表述性状态转移。 感觉还是不知所云&#xff0c;参考下怎样用通俗的语言解释REST&#xff0c;以及RESTful&#xff1f; 即URL定位资源&#xff0c;用H…...

程序员着装的改变

是什么力量&#xff0c;让任何地方的程序员都享有「免于体面的自由」&#xff1f; 在今天的社会里&#xff0c;工程师往往代表着知识水平和社会地位。每当普通人听到这个头衔&#xff0c;总会报之以敬仰的目光&#xff1a; 但有一种工程师&#xff0c;虽然也是如假包换的高级技…...

Simulink仿真中将工作空间中的数据变量保存成.mat文件

在基于模型开发的过程当中&#xff0c;除了模型本身之外&#xff0c;模型的参数也是开发成果的一个重要部分&#xff0c;为了下次仿真能够更快的运用参数&#xff0c;在本次仿真中可以将经常需要的参数保存&#xff0c;以便于下次仿真使用。 一般常用的有两种方法&#xff1a;…...

谈谈系统稳定性设计

转载自 谈谈系统稳定性设计 一、差旅随想 因为base在分公司&#xff0c;需要经常去总部出差&#xff0c;所以搭乘飞机成了家常便饭&#xff0c;很多时候坐在飞机上会不由的感叹&#xff0c;设计制造这样精密复杂的机器的那帮人真的是了不起&#xff0c;他们是怎样保证这样一台…...

内网渗透 Metasploit(MSF)基础使用

内网渗透 Metasploit&#xff08;MSF&#xff09;使用 1、认识 MSF ​ Metasploit 是一款开源的安全漏洞检测工具&#xff0c;可以帮助安全和IT专业人士识别安全性问题&#xff0c;验证漏洞的缓解措施&#xff0c;并管理专家驱动的安全性进行评估&#xff0c;提供真正的安全风…...

数据结构—笔记整理—初识数据结构

学习之路&#xff0c;长路漫漫&#xff0c;写学习笔记的过程就是把知识讲给自己听的过程。 目录 数据结构初定义 常用数据结构 这 8 种数据结构有什么区别呢&#xff1f; ①、数组 ②、链表 ③、栈 ④、队列 ⑤、树 ⑥、堆 ⑦、图 ⑧、哈希表 数据结构 集合结构(非…...

抖音10月的带货风向是什么?

站内大促氛围火爆&#xff0c;双十一好物节加持下&#xff0c;又有哪些亮眼主播、热卖商品和出圈品牌呢&#xff1f;通过新抖统计的10月1日-10月31日的月榜数据&#xff0c;一起来了解看看吧。01 30主播带货破亿 东方甄选蝉联榜首据新抖「主播带货榜」数据显示&#xff0c;10月…...

Linux学习笔记11 - 进程间通信(IPC)(二)

信号 其源于 UNIX 中的一种的古老方法&#xff0c;其是在软件层次上对中断机制的一种模拟(软中断)&#xff0c;是一种异步通信方式。可以直接进行用户空间进程(user process)和内核进程(kernel process)之间的交互&#xff0c;内核进程也可以利用其来通知用户空间进程(user pr…...

成为更优秀的程序员:退后一步看问题

转载自 成为更优秀的程序员&#xff1a;退后一步看问题 一天&#xff0c;在工作中… Bug #3890 来自客户&#xff1a; 有个程序出现了错误&#xff0c;程序提示说“SpeedCalculator::compute()里出现了除零情况”。 请尽快修复&#xff01; 你打开SpeedCalculator.php&#…...

【C++】多态 — 多态的原理 (下篇)

文章目录&#x1f4d6; 前言1. 虚函数表1.1 虚函数表的引入&#xff1a;1.2 基类的虚表&#xff1a;1.3 派生类虚表&#xff1a;2. 多态的原理2.1 多态虚函数的调用和普通函数的调用&#xff1a;2.1 - 1 到底什么是多态&#xff08;重点&#xff09;2.1 - 2 父类的指针实现多态…...

ZOJ - 2968 Difference Game 思维

题目链接&#xff1a;点击查看 Now you are going to play an interesting game. In this game, you are given two groups of distinct integers and C coins. The two groups, named Ga and Gbrespectively, are not empty and contain the same number of integers at firs…...

20个高级Java面试题汇总

转载自 20个高级Java面试题汇总 译文链接&#xff1a;http://www.codeceo.com/article/20-java-advanced-interview-questions.html 英文原文&#xff1a;Advanced Java Interview Questions 翻译作者&#xff1a;码农网 – 小峰 这是一个高级Java面试系列题中的部分。这一部分…...