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

【排序】快速排序

原理

对于一个数组x,快速排序流程如下:

  1. 确定分界点a,可以取x[l]、x[r]、x[l + r / 2]、随机(四种都可以)
  2. 调整区间,使得:区间被分成 <= a 和 >= a的两部分,左边 <= a,右边 >= a(注意,a不一定在原来的位置了)
  3. 递归处理左右两边

重点在于第二步调整区间上。

在这里插入图片描述

做法是:在区间[l, r]中,指定两个指针i、j。

  • 当i指向的数 < a的时候,i往右移动
  • 当j指向的数 > a的时候,j往左移动

当i和j停下来的时候,说明x[i] >= ax[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&#xff0c;快速排序流程如下&#xff1a; 确定分界点a&#xff0c;可以取x[l]、x[r]、x[l r / 2]、随机&#xff08;四种都可以&#xff09;调整区间&#xff0c;使得&#xff1a;区间被分成 < a 和 > a的两部分&#xff0c;左边 < a&#xff…...

Python大数据实践:selenium爬取京东评论数据

准备工作 selenium安装 Selenium是广泛使用的模拟浏览器运行的库&#xff0c;用于Web应用程序测试。 Selenium测试直接运行在浏览器中&#xff0c;就像真正的用户在操作一样&#xff0c;并且支持大多数现代 Web 浏览器。 #终端pip安装 pip install selenium #清华镜像安装 p…...

信息系统项目管理师019:存储和数据库(2信息技术发展—2.1信息技术及其发展—2.1.3存储和数据库)

文章目录 2.1.3 存储和数据库1.存储技术2.数据结构模型3.常用数据库类型4.数据仓库 记忆要点总结 2.1.3 存储和数据库 1.存储技术 存储分类根据服务器类型分为&#xff1a;封闭系统的存储和开放系统的存储。封闭系统主要指大型机等服务器。开放系统指基于包括麒麟、欧拉、UNIX…...

Python基础(六)之数值类型元组

Python基础&#xff08;六&#xff09;之数值类型元组 1、简介 元组&#xff1a; 在Python中是内置的数据结构之一&#xff0c;是一个不可变的序列,切可以是任何类型数据。元组的元素放在&#xff08;&#xff09;小括号内。一般我们希望数据不改变的时候使用 不可变与可变的…...

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报错&#xff1f; 文章目录 uniapp微信小程序随机生成canvas-id报错&#xff1f;效果图遇到问题解决 场景&#xff1a; 子组件&#xff0c;在 mounted 绘制 canvas&#xff1b;App、H5端正常显示&#xff0c;微信小程序报错&#xff1b; 效…...

爬虫 Day2

resp.close()#关掉resp 一requests入门 &#xff08;一&#xff09; 用到的网页&#xff1a;豆瓣电影分类排行榜 - 喜剧片 import requestsurl "https://movie.douban.com/j/chart/top_list" #参数太长&#xff0c;重新封装参数 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的功能&#xff0c;但要么收费要么有广告&#xff0c;实际上可以通过python&#xff0c;几行代码就能够实现视频转gif。 二、使用方法 1安装必备库moviepy pip install moviepy -i https://pypi.tuna.tsinghua.edu.cn/simple 2. 写入代码 …...

深入浅出Go的`encoding/xml`库:实战开发指南

深入浅出Go的encoding/xml库&#xff1a;实战开发指南 引言基本概念XML简介Go语言中的XML处理结构体标签&#xff08;Struct Tags&#xff09; 解析XML数据使用xml.Unmarshal解析XML结构体标签详解处理常见解析问题 生成XML数据使用xml.Marshal生成XML使用xml.MarshalIndent优化…...

深度学习之扩散模型(Diffusion model)

代码解析&#xff1a;正向扩散过程和加噪演示 引言 这段代码实现了一个正向扩散过程和加噪演示的功能。通过生成一个特定形状的数据集&#xff0c;并在每个时间步长上应用正向扩散过程和加噪过程&#xff0c;最终展示了数据点在空间中的演变过程。 数据集生成 通过 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.目标&#xff1a;如何实现会话保持/会话共享 方案一&#xff1a;登录状态写入cookie中.(wor…...

win7、win10、win11 系统能安装的.net framework 版本以

win7、win10、win11 系统能安装的.net framework 版本分别是多少&#xff1f;以及能安装的最高版本是多少&#xff1f; 以下是各Windows系统能够安装和支持的.NET Framework版本及其最高可安装版本的概述&#xff1a; Windows 7&#xff1a; 自带 .NET Framework 3.5.1&#x…...

RediSearch比Es搜索还快的搜索引擎

1、介绍 RediSearch是一个Redis模块&#xff0c;为Redis提供查询、二次索引和全文搜索。要使用RediSearch&#xff0c;首先要在Redis数据上声明索引。然后可以使用重新搜索查询语言来查询该数据。RedSearch使用压缩的反向索引进行快速索引&#xff0c;占用内存少。RedSearch索…...

mybatis-plus 的saveBatch性能分析

Mybatis-Plus 的批量保存saveBatch 性能分析 目录 Mybatis-Plus 的批量保存saveBatch 性能分析背景批量保存的使用方案循环插入使用PreparedStatement 预编译优点&#xff1a;缺点&#xff1a; Mybatis-Plus 的saveBatchMybatis-Plus实现真正的批量插入自定义sql注入器定义通用…...

python异常:pythonIOError异常python打开文件异常

1.python读取不存在的文件时&#xff0c;抛出异常 通过 open()方法以读“r”的方式打开一个 abc.txt 的文件&#xff08;该文件不存在&#xff09;&#xff0c;执行 open()打开一个不存在的文件时会抛 IOError 异常&#xff0c;通过 Python 所提供的 try...except...语句来接收…...

电话机器人语音识别用哪家更好精准度更高。

语音识别系统的选择取决于你的具体需求&#xff0c;包括但不限于识别精度、速度、易用性、价格等因素。以下是一些在语音识别领域表现较好的公司和产品&#xff1a; 科大讯飞&#xff1a;科大讯飞是中国最大的语音识别技术提供商之一&#xff0c;其语音识别技术被广泛应用于各…...

【Unity动画】Unity如何导入序列帧动画(GIF)

Unity 不支持GIF动画的直接播放&#xff0c;我们需要使用序列帧的方式 01准备好序列帧 02全部拖到Unity 仓库文件夹中 03全选修改成精灵模式Sprite 2D ,根据需要修改尺寸&#xff0c;点击Apply 04 创建一个空物体 拖动序列上去 然后全选所有序列帧&#xff0c;拖到这个空物体…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...