【QuickSort】单边快排思路及实现
思路:
(1)首先定义一个递归函数:qucikSort(int [ ] arr,int l,int r)。函数的定义:给定一个数组arr,对它在[l,r]这个区间内的元素进行排序,从而使得整个数组在[l,r]这个区间内有序。
(2)每次排序后得到一个索引p,索引p左边的元素都小于它,索引p右边的元素都大于它;此时我们就可以到[l,p - 1]、[p+1,r]这两个区间上继续排序,直至l>=r,区间内没有元素可排序为止。
(3)对区间[l,r]排序时,首先确定基准元素pv(选择区间内最右的元素arr[r]),随后维护两个指针i、j,j指针用于寻找在[l,r - 1]区间内比pv小的元素,i指针用于在j指针找到比pv小的元素时,交换i、j两个指针指向元素的位置,同时i指针向右移动,为下一次位置交换做准备。
(4)退出循环后,区间[0,i - 1]区间的所有元素都小于pv,[i,r - 1]区间的所有元素都大于pv。此时再交换i、r两个索引处的元素位置,基准元素被交换到了索引i处,基准元素的位置固定,后续不再参与排序。
Code:
(1)generate方法,随机生成一个需要排序的数组:
//生成一个长度为n,元素值在1-v之间的整型数组private static int [] generate(int n,int v){int [] result = new int[n];for (int i = 0; i < n; i++) {result[i] = (int) ((Math.random() * v) + 1);}return result;}
(2)递归函数quickSort:
//递归函数定义:对数组arr在[l,r]区间上的元素进行排序private static void quickSort(int [] arr,int l,int r){//l == r:区间内只有一个元素,不用排序//l > r:区间内没有元素,不用排序if(l >= r)return;//p:排好序的元素的索引,在arr[p]左边都是小于它的元素,右边都是大于它的元素int p = partition(arr,l,r);quickSort(arr,p + 1,r);quickSort(arr,l,p - 1);}
(3)swap方法,交换两个元素arr[a]、arr[b]的位置:
//交换arr[a]、arr[b]两个元素的为止private static void swap(int [] arr,int a,int b){int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}
(4)关键的排序方法:
private static int partition(int [] arr,int l,int r){//选取[l,r]这个区间内,最右边的元素:arr[r]作为基准元素pvint pv = arr[r];//i:在[l,r]这个区间内,如果元素比基准元素小,那么这个元素就会被交换到i索引处int i = l;//从索引l开始遍历整个区间for(int j = l;j < r;j ++){//碰到比基准元素pv小的元素时if(arr[j] < pv) {//交换arr[i]、arr[j]两个元素的位置swap(arr, i, j);//i++是为了下一次交换位置做准备i++;}}//循环结束时,[l,r - 1]这个区间内,所有比基准元素小的元素都在[0,i - 1]这个区间上//此时交换arr[i]、arr[r]两个元素的位置,基准元素此时就是arr[i]//在arr[i]左边都是小于它的元素,在arr[i]右边都是大于它的元素swap(arr,i,r);//返回索引i,索引i上的元素位置不再发生变动return i;}
(5)测试:
public static void main(String[] args) {//生成一个长度为10,元素值在1-10之间的数组int[] test = generate(10, 10);System.out.println("排序前:"+Arrays.toString(test));quickSort(test,0,test.length - 1);System.out.println("排序后:" + Arrays.toString(test));}
(6)输出结果:

总结:
(1)首先明确base case:当l >= r时,数组不需要进行排序。
(2)每次排序确定一个索引位置p,p左边都是小于它的元素,p右边都是大于它的元素,它不再参与排序。
(3)索引位置p确定后,需要排序就只剩下区间:[l,p - 1]、[p + 1,r],不断递归,直至l >= r时,排序结束。
相关文章:
【QuickSort】单边快排思路及实现
思路: (1)首先定义一个递归函数:qucikSort(int [ ] arr,int l,int r)。函数的定义:给定一个数组arr,对它在[l,r]这个区间内的元素进行排序,从而使得整个数组在[l,r]这个区间内有序。 ࿰…...
C++:继承
继承: 继承的基本语法: 继承是面向对象三大特性之一: 我们发现,定义这些类,下级别的成员除了拥有上一级的共性,还有自己的特性。 这个时候我们就可以考虑利用继承的技术,减少重复代码。 继承的…...
苍穹外卖--客户催单
需求分析 用户在小程序中点击催单按钮后,需要第一时间通知外卖商家 设计思路:* 通过WebSocket实现管理端页面和服务端保持长连接状态当用户点击催单按钮后,调用WebSocket的相关API实现服务端向客户端推送消息客户端浏览器解析服务端推送的…...
春秋云境:CVE-2022-32991(sql注入)
靶标介绍: 该CMS的welcome.php中存在SQL注入攻击。 获取登录地址 http://eci-2zeb0096que0556y47vq.cloudeci1.ichunqiu.com:80 登录注册 注册成功登录进入注册接口 参数接口一 发现接口参数q http://eci-2zeb0096que0556y47vq.cloudeci1.ichunqiu.com/welcome.p…...
css实现鼠标移入背景图片变灰并浮现文字的效果
首先上效果图 说明一下我的html结构 如上图是一个div包裹的img标签, div的块大小width, height 自己定义, 我说明一下核心样式代码 下面写法是scss, 请自行替换 .web-query-image {position: relative; // 相对定位, 方便浮现文案进行绝对定位border-radius: 8px;box-sizing: …...
ES-深入理解倒排索引
倒排索引 idproductdesc1新版 小米 至尊-纪念版手机1小米 NFC 手机3NFC手机4小米 耳机5华为 耳机6扫地机器人7华为 Mata………………term_indexterm dictionaryposting list------------------------------------小米1……100W华为6,7,9NFC76,90耳机5352红米643,98机器人645,9…...
linux NAT网卡配置static
由于是内网,资料无法拷贝,借助参考资料,整理发出。 镜像安装 基本操作。 查看VM配置 图1,有几个信息。一个是NAT借用了网卡里的VMnet8适配器。 子网IP是从192.168.142.0 子网掩码255.255.255.255,对应下面配置的N…...
信奥编程 1168:大整数加法
解析:在c中需要考虑这么几个问题,第一个是大数据的输入,第二个是大数据的存储,第三是大数据的计算方式,最后是输出。 针对上述几个问题,第一个问题,采用字符串的方式或者数组加循环的方式接收输…...
k8s上Pod全自动调度、定向调度、亲和性调度、污点和容忍调度详解
目录 一.Pod调度简介 二.Deployment/RC全自动调度 1.简介 2.案例演示 (1)Deployment (2)RC 三.nodeSelector/nodeName指定节点调度 1.原理简介 (1)nodeSelector原理 (2)no…...
C# 动态编译代码并执行
写在前面 本文采用动态编译的方式,对目标文件code.txt中的C#代码进行实时编译并调用;当然也可以直接在代码中直接装配或读取已有的代码文本,动态编译可以用于很多需要热更新的场景,实现无需重启程序也能达到更新代码的需求。 代…...
nginx配置反向代理及负载均衡
目录 1.前端发送的请求,是如何请求到后端服务的1.nginx 反向代理的好处:2.nginx 反向代理的配置方式:3. nginx 负载均衡的配置方式 1.前端发送的请求,是如何请求到后端服务的 1.nginx 反向代理的好处: 提高访问速度 因…...
【古月居《ros入门21讲》学习笔记】09_订阅者Subscriber的编程实现
目录 说明: 1. 话题模型 图示 说明 2. 实现过程(C) 创建订阅者代码(C) 配置发布者代码编译规则 编译并运行 编译 运行 3. 实现过程(Python) 创建订阅者代码(Python&…...
Java全栈基础篇--集合
集合 集合:集合是java中提供的一种容器,可以用来存储多个数据。 特点: 长度不固定,还可以存储不同的数据(但是一般都用同一类型) 集合和数组既然都是容器,它们有啥区别呢? 数组的长…...
Facebook公共主页受限、被封?一文教你排雷解决
一、Facebook公共主页是什么? 现在人们的生活已经离不开各种社交媒体,只要有智能手机,或多或少会使用一些社交平台,而Facebook是一个拥有大量用户的社交平台。这对于各种企业而言,也是一个十分优秀的营销平台…...
Day04:每日一题:2661. 找出叠涂元素
2661. 找出叠涂元素 给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。 arr 和 mat 都包含范围 [1,m * n] 内的 所有 整数。从下标 0 开始遍历 arr 中的每个下标 i ,并将包含整数 arr[i] 的 mat 单元格涂色。请你找出 arr 中在 mat…...
SpringBoot 整合Redis
在Spring Boot中,你可以使用以下注解来实现Redis的整合: EnableCaching: 在启动类上添加该注解,开启Spring的缓存支持。 Cacheable: 标记方法的返回值可被缓存。当缓存中存在相同 key 的数据时,直接从缓存中获取数据,否则执行方法…...
tensorflow-gpu1.15 + win11 + RTX 4050环境配置
组了一套,不知道行不行 windows11GPURTX 4050python3.7.12tensorflow-gpu1.15.0cudatoolkit10.0.130cudnn7.6.5Keras2.3.1...
jmeter资料
1.jmeter介绍 Apache JMeter是Apache组织开发的基于Java的压力测试工具。用于对软件做压力测试,它最初被设计用于Web应用测试,但后来扩展到其他测试领域。 它可以用于测试静态和动态资源,例如静态文件、Java 小服务程序、CGI 脚本、Java 对象…...
代码随想录算法训练营第三十六天| 435 无重叠区间 763 划分字母区间 56 合并区间
目录 435 无重叠区间 763 划分字母区间 56 合并区间 435 无重叠区间 将intervals数组按照左端点进行升序排序。 设置变量len标志此时新加入端点后所有区间的位置,将其赋初值为第一对区间的右端点,因为该点是一定可达的。设置变量res来存储需要移除空间…...
2023-12-01 事业-代号s-引流技巧和营销思路
摘要: 2023-12-01 事业-代号s-引流技巧和营销思路 引流技巧和营销思路 独立站流量渠道主要有以下几种:1、CPC付费广告:搜索引擎、社交平台、广告联盟平台。2、网红营销:youtube、INS、博客论文、TT直播。适合比较时尚品类3、Affiliate促销网站:优惠券折扣网站发布产品优惠…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
ubuntu22.04 安装docker 和docker-compose
首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...
