当前位置: 首页 > 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促销网站:优惠券折扣网站发布产品优惠…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

Monorepo架构: Nx Cloud 扩展能力与缓存加速

借助 Nx Cloud 实现项目协同与加速构建 1 &#xff09; 缓存工作原理分析 在了解了本地缓存和远程缓存之后&#xff0c;我们来探究缓存是如何工作的。以计算文件的哈希串为例&#xff0c;若后续运行任务时文件哈希串未变&#xff0c;系统会直接使用对应的输出和制品文件。 2 …...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...