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

【洛谷 P1177】【模板】快速排序 题解(快速排序+指针)

【模板】快速排序

题目描述

利用快速排序算法将读入的 NNN 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料,掌握后独立完成。(C++ 选手请不要试图使用 STL,虽然你可以使用 sort 一遍过,但是你并没有掌握快速排序算法的精髓。)

输入格式

111 行为一个正整数 NNN,第 222 行包含 NNN 个空格隔开的正整数 aia_iai,为你需要进行排序的数,数据保证了 aia_iai 不超过 10910^9109

输出格式

将给定的 NNN 个数从小到大输出,数之间空格隔开,行末换行且无空格。

样例 #1

样例输入 #1

5
4 2 4 5 1

样例输出 #1

1 2 4 4 5

提示

对于 20%20\%20% 的数据,有 N≤103N\leq 10^3N103

对于 100%100\%100% 的数据,有 N≤105N\leq 10^5N105

思路

快速排序。数据过大,需要打开O2优化。

AC代码

#include <iostream>
#include <cstdio>
#define AUTHOR "HEX9CF"
using namespace std;const int maxn = 100005;
int n;void read(int &x){x = 0;char ch;while (('0' > ch || '9' < ch)){ch = getchar();}while (!('0' > ch || '9' < ch)){x = x * 10 + ch - '0';ch = getchar();}
}int* partition(int a[], int *low, int *high){int *i = low;int *j = high;int pivot = *low;while(i < j){// 右指针大于基准值,向左移动while(i < j && *j > pivot){j--;}// 左指针大于基准值,向右移动while(i < j && *i <= pivot){i++;}// 交换左右指针的值if(i < j){swap(*(i++), *(j--));}}// 左指针和基准值比较if(*i > pivot){// i - 1处为基准值swap(*(i - 1), *low);return i - 1;}else{// i处为基准值swap(*i, *low);return i;}
}void quickSort(int a[], int *low, int *high){if(low < high){int *mid = partition(a, low, high);quickSort(a, low, mid - 1);quickSort(a, mid + 1, high);}
}int main() {int arr[maxn];read(n);for(int i = 0; i < n; i++){int in;read(arr[i]);}quickSort(arr, arr, arr + n - 1);for(int i = 0; i < n; i++){printf("%d ", arr[i]);}return 0;
}

相关文章:

【洛谷 P1177】【模板】快速排序 题解(快速排序+指针)

【模板】快速排序 题目描述 利用快速排序算法将读入的 NNN 个数从小到大排序后输出。 快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料&#xff0c;掌握后独立完成。&#xff08;C 选手请不要试图使用 STL&#xff0c;虽然你可以…...

Pthon--自动化实用技巧篇--文件目录处理

为什么要讲这一篇&#xff0c;主要是因为这个在自动化测试框架或者脚本的编写的时候会用到&#xff0c;还是比较方便的。看上述两个函数。getcwd()、chdir()。使用 os.getcwd() 函数获得当前工作目录。使用 os.chdir()函数改变当前工作目录。所以在用chdir()函数的时候别忘记指…...

想招到实干派程序员?你需要这种面试法

技术招聘中最痛的点其实是不精准。技术面试官或CTO们常常会向我们吐槽&#xff1a; “我经常在想&#xff0c;能不能把我们项目中的代码打印出来&#xff0c;作为候选人的面试题的一部分&#xff1f;” “能不能把一个Bug带上环境&#xff0c;让候选人来试试怎么解决&#xf…...

cesium常见操作:鼠标点击获取对象

目录 一、viewer.scene.pick&#xff08;获取Cartesian2&#xff09; 二、 viewer.scene.pickPosition&#xff08;获取Cartesian3&#xff09; 三、viewer.scene.drillPick&#xff08;穿透拾取&#xff0c;获取所有对象&#xff09; 四、viewer.scene.globe.pick&#xf…...

【玩转c++】git的安装和使用以及可视化处理

本期主题&#xff1a;git的安装和使用&#xff08;windows环境&#xff09;博客主页&#xff1a;小峰同学分享小编的在Linux中学习到的知识和遇到的问题 小编的能力有限&#xff0c;出现错误希望大家不吝赐1.两个工具介绍第一个工具git&#xff0c;链接gitee或者github等代码托…...

第三阶段02-Mybatis框架

Mybatis框架 Mybatis框架是目前最流行的数据持久层框架, 使用Mybatis框架可以帮助程序员自动生成JDBC代码, 程序员只需要通过注解或xml配置文件提供需要执行的SQL语句,以及对象和表的映射关系, Mybatis框架会根据此映射关系和SQL自动生成出JDBC代码,从而提高开发效率 Mybatis框…...

基于超像素的多视觉特征图像分割算法研究

0.引言 背景&#xff1a; 经典聚类算法&#xff1a;Kmeans、FCM 现有问题&#xff1a; 1&#xff09;现有算法大都是基于单一的视觉特征而设计的&#xff0c;eg&#xff1a;基于颜色特征的分割。 2&#xff09;没有考虑像素周围的空间信息&#xff1b;分割结果&#xff1a;多噪…...

mysql的三大日志

摘自https://blog.csdn.net/chuige2013/article/details/123027580 一. 初步认识 binlog二进制日志 redolog undolog 二. binlog binlog记录写入行操作 作用 1&#xff09;、主从复制&#xff1a;在Master端开启binlog&#xff0c;然后将binlog发送到各个Slave端&#xff0c;S…...

API接口及社区电子商务化的解释

API是应用程序的开发接口&#xff0c;在开发程序的时候&#xff0c;我们有些功能可能不需要从到到位去研发&#xff0c;我们可以拿现有的开发出来的功能模块来使用&#xff0c;而这个功能模块&#xff0c;就叫做库(libary)。比如说&#xff1a;要实现数据传输的安全&#xff0c…...

[蓝帽杯 2021]One Pointer PHP

知识点&#xff1a;php 数组整型溢出&#xff0c;open_basedir 绕过分析 利用数组整型溢出绕过&#xff0c;因为PHP 会对溢出的数字处理为 float 类型。 <?php include "user.php"; if($userunserialize($_COOKIE["data"])){$count[$user->count]…...

【JAVA】xxl-job服务搭建

xxl-job服务搭建 1.下载xxl-job项目 https://github.com/xuxueli/xxl-job 2.数据库表创建 3.修改配置 注意&#xff1a;这是两个项目&#xff0c;一个是xxl-job前台&#xff0c;一个是xxl-job执行器&#xff0c;找到这两个项目得配置文件&#xff0c;修改配置。 配置文件地址…...

毕业设计 基于STM32单片机生理监控心率脉搏TFT彩屏波形曲线设计

基于STM32单片机生理监控心率脉搏TFT彩屏波形曲线设计1、项目简介1.1 系统构成1.2 系统功能2、部分电路设计2.1 STM32F103C8T6核心系统电路设计2.2心率检测电路设计2.3 TFT2.4寸彩屏电路设计3、部分代码展示3.1 ADC初始化3.2 获取ADC采样值3.3 LCD引脚初始化3.3 在LCD指定位置显…...

【10k~30k的区别】=== 功能测试、自动化测试、性能测试的区别

按测试执行的类型来分&#xff1a;功能测试、自动化测试、性能测试 1&#xff0e;功能测试 功能测试俗称点点点测试。初级测试人员的主要测试任务就是执行测试工程师所写的测试用 例&#xff0c;记录用例的执行状态及bug情况。与开发人员进行交互直到bug被修复。 功能测试理论…...

《MySQL学习》 索引失效的三种特殊情况

一.条件字段使用函数 explain select * from bpm_proc_instance bpi where CREATED_AT > 2022-06-01 CREATED_AT 字段建立了索引&#xff0c;此时explain分析的结果表明能使用到索引 但如果我们对 CREATED_AT 字段使用函数 explain select * from bpm_proc_instance bpi w…...

wafw00f 防火墙探测

kali机器自带防火墙探测工具wafw00&#xff0c;它可以通过发送正常以及不正常甚至包含恶意代码的HTTP请求&#xff0c;来探测网站是否存在防火墙&#xff0c;并识别防火墙的厂商及类型。安装&#xff1a;git clone https://github.com/EnableSecurity/wafw00f.git python setup…...

MySQL学习(1)[参考书籍:mysql是怎么运行的]

目录 一、mysql设计模式和技术 二、mysql服务器和客户端 启动mysql服务 启动mysql客户端程序 三、mysql存储引擎 四、mysql配置 五、mysql系统变量 六、mysql字符集 编码和解码&#xff1a; 常见字符集&#xff08;五种&#xff09;&#xff1a; 相关概念&#xff1…...

用Python制作邮件检测器

github地址&#xff1a; https://github.com/CaLlMeErIC/MailDetective 因为需求需要写一个简单的邮件检测系统的框架&#xff0c;这里记录下思路 首先第一反应,这个检测系统不应该是各个邮件收件系统都有自带的吗&#xff0c;于是搜索了下是否有相关的邮件检测开源软件&#…...

K8S---pod基础概念

目录 一、资源限制 二、Pod 的两种使用方式 三、Pod 资源共享 四、底层容器Pause 1、Pause共享资源 1.1 网络 1.2 存储 1.3 小结 2、Pause主要功能 3、Pod 与 Pause 结构的设计初衷 五、Pod容器的分类 1、基础容器&#xff08;infrastructure container&#xff09;…...

激活函数入门学习

本篇文章从外行工科的角度尽量详细剖析激活函数&#xff0c;希望不吝指教&#xff01; 学习过程如下&#xff0c;先知道这个东西是什么&#xff0c;有什么用处&#xff0c;以及怎么使用它&#xff1a; 1. 为什么使用激活函数 2. 激活函数总类及优缺点 3. 如何选择激活函数 …...

小文智能结合ChatGPT的产业未来

最近几个月&#xff0c;由人工智能实验室OpenAI发布的对话式大型语言模型ChatGPT在国内外各大平台掀起了一阵AI狂潮。短短几天时间&#xff0c;其用户量就突破了百万大关&#xff0c;注册用户之多一度导致服务器爆满。 继AI画图之后&#xff0c;ChatGPT成为了新的顶流&#xf…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

[USACO23FEB] Bakery S

题目描述 Bessie 开了一家面包店! 在她的面包店里&#xff0c;Bessie 有一个烤箱&#xff0c;可以在 t C t_C tC​ 的时间内生产一块饼干或在 t M t_M tM​ 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC​,tM​≤109)。由于空间…...