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

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

电脑桌面太单调,用Python写一个桌面小宠物应用。

下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡&#xff0c;可以响应鼠标点击&#xff0c;并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...

云原生安全实战:API网关Envoy的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口&#xff0c;负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...

【NLP】 38. Agent

什么是 Agent&#xff1f; 一个 Agent 就是能够 理解、思考&#xff0c;并且进行世界交互 的模型系统&#xff0c;并不是纯粹的 prompt 返回器。 它可以&#xff1a; 读取外部数据&#xff08;文件/API&#xff09;使用记忆进行上下文维持用类Chain-of-Thought (CoT)方式进行…...