【排序】快速排序
原理
对于一个数组x,快速排序流程如下:
- 确定分界点a,可以取x[l]、x[r]、x[l + r / 2]、随机(四种都可以)
- 调整区间,使得:区间被分成 <= a 和 >= a的两部分,左边 <= a,右边 >= a(注意,a不一定在原来的位置了)
- 递归处理左右两边
重点在于第二步调整区间上。

做法是:在区间[l, r]中,指定两个指针i、j。
- 当i指向的数 < a的时候,i往右移动
- 当j指向的数 > a的时候,j往左移动
当i和j停下来的时候,说明x[i] >= a,x[j] <= a,则x[i] >= x[j]。那根据我们的想要实现的目的,要保证左边 <= a,右边 >= a,也就是x[i] <= x[j]。因此,需要将x[i]与x[j]交换。
复杂度
代码
import java.util.*;
import java.io.*;class Main {public static void quick(int[] x, int l, int r) {if (l >= r) return ;int a = x[l + r >> 1], i = l - 1, j = r + 1;while (i < j) {/**内层的循环不能加 i < j原因:如果加了i < j,那么两个do while之后,i = j。此时,如果x[j] > a,而后续的递归就会出问题,因为要保证[l, j]的数都 < a所以原则就是,最后外层循环退出的时候,要保证i > j,不能i = j*/do i ++ ; while (x[i] < a);do j -- ; while (x[j] > a);if (i < j) {int t = x[i];x[i] = x[j];x[j] = t;}}quick(x, l, j);quick(x, j + 1, r);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] x = new int[n];for(int i = 0; i < n; i ++ ) x[i] = sc.nextInt();quick(x, 0, n - 1);for(int i = 0; i < n; i ++ ) System.out.print(x[i] + " ");}
}
相关文章:
【排序】快速排序
原理 对于一个数组x,快速排序流程如下: 确定分界点a,可以取x[l]、x[r]、x[l r / 2]、随机(四种都可以)调整区间,使得:区间被分成 < a 和 > a的两部分,左边 < aÿ…...
Python大数据实践:selenium爬取京东评论数据
准备工作 selenium安装 Selenium是广泛使用的模拟浏览器运行的库,用于Web应用程序测试。 Selenium测试直接运行在浏览器中,就像真正的用户在操作一样,并且支持大多数现代 Web 浏览器。 #终端pip安装 pip install selenium #清华镜像安装 p…...
信息系统项目管理师019:存储和数据库(2信息技术发展—2.1信息技术及其发展—2.1.3存储和数据库)
文章目录 2.1.3 存储和数据库1.存储技术2.数据结构模型3.常用数据库类型4.数据仓库 记忆要点总结 2.1.3 存储和数据库 1.存储技术 存储分类根据服务器类型分为:封闭系统的存储和开放系统的存储。封闭系统主要指大型机等服务器。开放系统指基于包括麒麟、欧拉、UNIX…...
Python基础(六)之数值类型元组
Python基础(六)之数值类型元组 1、简介 元组: 在Python中是内置的数据结构之一,是一个不可变的序列,切可以是任何类型数据。元组的元素放在()小括号内。一般我们希望数据不改变的时候使用 不可变与可变的…...
Chrome历史版本下载地址:Google Chrome Older Versions Download (Windows, Linux Mac)
最近升级到最新版本Chrome后发现页面居然显示错乱,是在无语, 打算退回原来的版本, 又发现官方只提供最新的版本下载, 为了解决这个问题所有收集了Chrome历史版本的下载地址分享给大家. Google Chrome Windows version 32-bit VersionSizeDate104.0.5112.10279.68 MB2022-05-30…...
ROS2纯跟踪实现(C++)
#include <tf2_ros/buffer.h> #include <tf2_ros/transform_broadcaster.h> #include <tf2_ros/transform_listener.h>#include <geometry_msgs/msg/transform_stamped.hpp> #include...
uniapp微信小程序随机生成canvas-id报错?
uniapp微信小程序随机生成canvas-id报错? 文章目录 uniapp微信小程序随机生成canvas-id报错?效果图遇到问题解决 场景: 子组件,在 mounted 绘制 canvas;App、H5端正常显示,微信小程序报错; 效…...
爬虫 Day2
resp.close()#关掉resp 一requests入门 (一) 用到的网页:豆瓣电影分类排行榜 - 喜剧片 import requestsurl "https://movie.douban.com/j/chart/top_list" #参数太长,重新封装参数 param {"type": "…...
达梦数据库SQL
达梦JSON函数技术文档 SQL中关键词处理 -- 必须要使用双引号包裹 select id,"comment" from t_cmp_rd_process;select id,"commit" from t_cmp_rd_gjj_eva;JSON_EXTRACT函数 -- party_sup_other_json 是包含JSON数据的列名。 -- $.content_abstract 是J…...
python教程——把视频转成gif
一、前言 很多网站提供视频转GIF的功能,但要么收费要么有广告,实际上可以通过python,几行代码就能够实现视频转gif。 二、使用方法 1安装必备库moviepy pip install moviepy -i https://pypi.tuna.tsinghua.edu.cn/simple 2. 写入代码 …...
深入浅出Go的`encoding/xml`库:实战开发指南
深入浅出Go的encoding/xml库:实战开发指南 引言基本概念XML简介Go语言中的XML处理结构体标签(Struct Tags) 解析XML数据使用xml.Unmarshal解析XML结构体标签详解处理常见解析问题 生成XML数据使用xml.Marshal生成XML使用xml.MarshalIndent优化…...
深度学习之扩散模型(Diffusion model)
代码解析:正向扩散过程和加噪演示 引言 这段代码实现了一个正向扩散过程和加噪演示的功能。通过生成一个特定形状的数据集,并在每个时间步长上应用正向扩散过程和加噪过程,最终展示了数据点在空间中的演变过程。 数据集生成 通过 make_swiss…...
Tomcat Session ID---会话保持
简单拓补图 一、负载均衡、反向代理 7-1nginx代理服务器配置 [rootdlnginx ~]#yum install epel-release.noarch -y ###安装额外源[rootdlnginx ~]#yum install nginx -y[rootdlnginx ~]#systemctl start nginx.service[rootdlnginx ~]#systemctl status nginx.service [ro…...
Session会话绑定
1.需求原因 用户的请求,登录的请求,经过负载均衡后落到后面的web服务器上,登录的状态/信息也会记录在web服务器上,就会导致不通的web服务器上,登录状态不统一,造成用户频繁需要登录 2.目标:如何实现会话保持/会话共享 方案一:登录状态写入cookie中.(wor…...
win7、win10、win11 系统能安装的.net framework 版本以
win7、win10、win11 系统能安装的.net framework 版本分别是多少?以及能安装的最高版本是多少? 以下是各Windows系统能够安装和支持的.NET Framework版本及其最高可安装版本的概述: Windows 7: 自带 .NET Framework 3.5.1&#x…...
RediSearch比Es搜索还快的搜索引擎
1、介绍 RediSearch是一个Redis模块,为Redis提供查询、二次索引和全文搜索。要使用RediSearch,首先要在Redis数据上声明索引。然后可以使用重新搜索查询语言来查询该数据。RedSearch使用压缩的反向索引进行快速索引,占用内存少。RedSearch索…...
mybatis-plus 的saveBatch性能分析
Mybatis-Plus 的批量保存saveBatch 性能分析 目录 Mybatis-Plus 的批量保存saveBatch 性能分析背景批量保存的使用方案循环插入使用PreparedStatement 预编译优点:缺点: Mybatis-Plus 的saveBatchMybatis-Plus实现真正的批量插入自定义sql注入器定义通用…...
python异常:pythonIOError异常python打开文件异常
1.python读取不存在的文件时,抛出异常 通过 open()方法以读“r”的方式打开一个 abc.txt 的文件(该文件不存在),执行 open()打开一个不存在的文件时会抛 IOError 异常,通过 Python 所提供的 try...except...语句来接收…...
电话机器人语音识别用哪家更好精准度更高。
语音识别系统的选择取决于你的具体需求,包括但不限于识别精度、速度、易用性、价格等因素。以下是一些在语音识别领域表现较好的公司和产品: 科大讯飞:科大讯飞是中国最大的语音识别技术提供商之一,其语音识别技术被广泛应用于各…...
【Unity动画】Unity如何导入序列帧动画(GIF)
Unity 不支持GIF动画的直接播放,我们需要使用序列帧的方式 01准备好序列帧 02全部拖到Unity 仓库文件夹中 03全选修改成精灵模式Sprite 2D ,根据需要修改尺寸,点击Apply 04 创建一个空物体 拖动序列上去 然后全选所有序列帧,拖到这个空物体…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
