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

【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】单边快排思路及实现

思路&#xff1a; &#xff08;1&#xff09;首先定义一个递归函数&#xff1a;qucikSort(int [ ] arr,int l,int r)。函数的定义&#xff1a;给定一个数组arr&#xff0c;对它在[l,r]这个区间内的元素进行排序&#xff0c;从而使得整个数组在[l,r]这个区间内有序。 &#xff0…...

C++:继承

继承&#xff1a; 继承的基本语法&#xff1a; 继承是面向对象三大特性之一&#xff1a; 我们发现&#xff0c;定义这些类&#xff0c;下级别的成员除了拥有上一级的共性&#xff0c;还有自己的特性。 这个时候我们就可以考虑利用继承的技术&#xff0c;减少重复代码。 继承的…...

苍穹外卖--客户催单

需求分析 用户在小程序中点击催单按钮后&#xff0c;需要第一时间通知外卖商家 设计思路&#xff1a;* 通过WebSocket实现管理端页面和服务端保持长连接状态当用户点击催单按钮后&#xff0c;调用WebSocket的相关API实现服务端向客户端推送消息客户端浏览器解析服务端推送的…...

春秋云境:CVE-2022-32991(sql注入)

靶标介绍&#xff1a; 该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

由于是内网&#xff0c;资料无法拷贝&#xff0c;借助参考资料&#xff0c;整理发出。 镜像安装 基本操作。 查看VM配置 图1&#xff0c;有几个信息。一个是NAT借用了网卡里的VMnet8适配器。 子网IP是从192.168.142.0 子网掩码255.255.255.255&#xff0c;对应下面配置的N…...

信奥编程 1168:大整数加法

解析&#xff1a;在c中需要考虑这么几个问题&#xff0c;第一个是大数据的输入&#xff0c;第二个是大数据的存储&#xff0c;第三是大数据的计算方式&#xff0c;最后是输出。 针对上述几个问题&#xff0c;第一个问题&#xff0c;采用字符串的方式或者数组加循环的方式接收输…...

k8s上Pod全自动调度、定向调度、亲和性调度、污点和容忍调度详解

目录 一.Pod调度简介 二.Deployment/RC全自动调度 1.简介 2.案例演示 &#xff08;1&#xff09;Deployment &#xff08;2&#xff09;RC 三.nodeSelector/nodeName指定节点调度 1.原理简介 &#xff08;1&#xff09;nodeSelector原理 &#xff08;2&#xff09;no…...

C# 动态编译代码并执行

写在前面 本文采用动态编译的方式&#xff0c;对目标文件code.txt中的C#代码进行实时编译并调用&#xff1b;当然也可以直接在代码中直接装配或读取已有的代码文本&#xff0c;动态编译可以用于很多需要热更新的场景&#xff0c;实现无需重启程序也能达到更新代码的需求。 代…...

nginx配置反向代理及负载均衡

目录 1.前端发送的请求&#xff0c;是如何请求到后端服务的1.nginx 反向代理的好处&#xff1a;2.nginx 反向代理的配置方式&#xff1a;3. nginx 负载均衡的配置方式 1.前端发送的请求&#xff0c;是如何请求到后端服务的 1.nginx 反向代理的好处&#xff1a; 提高访问速度 因…...

【古月居《ros入门21讲》学习笔记】09_订阅者Subscriber的编程实现

目录 说明&#xff1a; 1. 话题模型 图示 说明 2. 实现过程&#xff08;C&#xff09; 创建订阅者代码&#xff08;C&#xff09; 配置发布者代码编译规则 编译并运行 编译 运行 3. 实现过程&#xff08;Python&#xff09; 创建订阅者代码&#xff08;Python&…...

Java全栈基础篇--集合

集合 集合&#xff1a;集合是java中提供的一种容器&#xff0c;可以用来存储多个数据。 特点&#xff1a; 长度不固定&#xff0c;还可以存储不同的数据&#xff08;但是一般都用同一类型&#xff09; 集合和数组既然都是容器&#xff0c;它们有啥区别呢&#xff1f; 数组的长…...

Facebook公共主页受限、被封?一文教你排雷解决

一、Facebook公共主页是什么&#xff1f; 现在人们的生活已经离不开各种社交媒体&#xff0c;只要有智能手机&#xff0c;或多或少会使用一些社交平台&#xff0c;而Facebook是一个拥有大量用户的社交平台。这对于各种企业而言&#xff0c;也是一个十分优秀的营销平台&#xf…...

Day04:每日一题:2661. 找出叠涂元素

2661. 找出叠涂元素 给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。 arr 和 mat 都包含范围 [1&#xff0c;m * n] 内的 所有 整数。从下标 0 开始遍历 arr 中的每个下标 i &#xff0c;并将包含整数 arr[i] 的 mat 单元格涂色。请你找出 arr 中在 mat…...

SpringBoot 整合Redis

在Spring Boot中&#xff0c;你可以使用以下注解来实现Redis的整合: EnableCaching: 在启动类上添加该注解&#xff0c;开启Spring的缓存支持。 Cacheable: 标记方法的返回值可被缓存。当缓存中存在相同 key 的数据时&#xff0c;直接从缓存中获取数据&#xff0c;否则执行方法…...

tensorflow-gpu1.15 + win11 + RTX 4050环境配置

组了一套&#xff0c;不知道行不行 windows11GPURTX 4050python3.7.12tensorflow-gpu1.15.0cudatoolkit10.0.130cudnn7.6.5Keras2.3.1...

jmeter资料

1.jmeter介绍 Apache JMeter是Apache组织开发的基于Java的压力测试工具。用于对软件做压力测试&#xff0c;它最初被设计用于Web应用测试&#xff0c;但后来扩展到其他测试领域。 它可以用于测试静态和动态资源&#xff0c;例如静态文件、Java 小服务程序、CGI 脚本、Java 对象…...

代码随想录算法训练营第三十六天| 435 无重叠区间 763 划分字母区间 56 合并区间

目录 435 无重叠区间 763 划分字母区间 56 合并区间 435 无重叠区间 将intervals数组按照左端点进行升序排序。 设置变量len标志此时新加入端点后所有区间的位置&#xff0c;将其赋初值为第一对区间的右端点&#xff0c;因为该点是一定可达的。设置变量res来存储需要移除空间…...

2023-12-01 事业-代号s-引流技巧和营销思路

摘要: 2023-12-01 事业-代号s-引流技巧和营销思路 引流技巧和营销思路 独立站流量渠道主要有以下几种:1、CPC付费广告:搜索引擎、社交平台、广告联盟平台。2、网红营销:youtube、INS、博客论文、TT直播。适合比较时尚品类3、Affiliate促销网站:优惠券折扣网站发布产品优惠…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

js 设置3秒后执行

如何在JavaScript中延迟3秒执行操作 在JavaScript中&#xff0c;要设置一个操作在指定延迟后&#xff08;例如3秒&#xff09;执行&#xff0c;可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法&#xff0c;它接受两个参数&#xff1a; 要执行的函数&…...

【Java多线程从青铜到王者】单例设计模式(八)

wait和sleep的区别 我们的wait也是提供了一个还有超时时间的版本&#xff0c;sleep也是可以指定时间的&#xff0c;也就是说时间一到就会解除阻塞&#xff0c;继续执行 wait和sleep都能被提前唤醒(虽然时间还没有到也可以提前唤醒)&#xff0c;wait能被notify提前唤醒&#xf…...

LINUX编译vlc

下载 VideoLAN / VLC GitLab 选择最新的发布版本 准备 sudo apt install -y xcb bison sudo apt install -y autopoint sudo apt install -y autoconf automake libtool编译ffmpeg LINUX FFMPEG编译汇总&#xff08;最简化&#xff09;_底部的附件列表中】: ffmpeg - lzip…...