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

快速排序 刷题笔记

思路 

分治+双指针 

在每个区间选定一个基准目标 

两个指针从数组的两边向中间推进 

使用

while循环判断

 do {i++;}while(q[i]<x); 
 do{j--;}while(q[j]>x);

每次这样做完就会找到q[i]>x,,,,q[j]小于x

此时我们交换 q[i] ,q[j]于是小于x的数分到了小于x的一侧 大于x的数分到了大于x的一侧

while(i<j){

        do {i++;}while(q[i]<x); 
        do{j--;}while(q[j]>x);


        if(i<j){swap(q[i],q[j]);}
    }

当做完这整个while 循环  就会形成所有小于 x的数在x一侧 而大于x的数在另一侧

在这个基础上 我们 不断划分区间 调整每一个局部区间 的顺序 从而达到整体有序

代码

#include<iostream>
using namespace std;
const int N = 100010;

int q[N];
void quick_sort(int q[],int l,int r){
    if(l>=r){
        return ;}
    int i=l-1,j=r+1,x=q[l+r>>1];
    while(i<j){

        do {i++;}while(q[i]<x); 
        do{j--;}while(q[j]>x);


        if(i<j){swap(q[i],q[j]);}
    }

        quick_sort(q,l,j);
        quick_sort(q,j+1,r);
}
int main()
{
    int n;
    cin>>n; 

    for (int i = 0; i < n; i ++ ) {
    cin>>q[i];}

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) {
    cout << q[i]<<' ';
    }

    return 0;
}

相关文章:

快速排序 刷题笔记

思路 分治双指针 在每个区间选定一个基准目标 两个指针从数组的两边向中间推进 使用 while循环判断 do {i;}while(q[i]<x); do{j--;}while(q[j]>x); 每次这样做完就会找到q[i]>x,,,,q[j]小于x 此时我们交换 q[i] ,q[j]于是小于x的数分到了小于x的一侧 大…...

DAY by DAY 史上最全的Linux常用命令汇总----man

man是按照手册的章节号的顺序进行搜索的。 man设置了如下的功能键&#xff1a; 功能键 功能 空格键 显示手册页的下一屏 Enter键 一次滚动手册页的一行 b 回滚一屏 f 前滚一屏 q 退出man命令 h 列出所有功能键 /word 搜索word字符串 注意&#xff1a…...

十六、接口隔离原则、反射、依赖注入

接口隔离原则、反射、特性、依赖注入 接口隔离原则 客户端不应该依赖它不需要的接口&#xff1b;一个类对另一个类的依赖应该建立在最小的接口上。 五种原则当中的i 上一章中的接口&#xff0c;即契约。 契约就是在说两件事&#xff0c;甲方说自己不会多要&#xff0c;乙方会在…...

Docker 进阶

1、容器数据卷 什么是容器数据卷&#xff1f; 就是当容器内存在了mysql&#xff0c;在里面书写了数据&#xff0c;如果容器删除了&#xff0c;那么数据也就没有了&#xff0c;通过容器数据卷的技术&#xff0c;可以让容器内的数据持久化到Linux服务器上 操作 #docker run -…...

科研学习|论文解读——一种修正评分偏差并精细聚类中心的协同过滤推荐算法

知网链接 一种修正评分偏差并精细聚类中心的协同过滤推荐算法 - 中国知网 (cnki.net) 摘要 协同过滤作为国内外学者普遍关注的推荐算法之一&#xff0c;受评分失真和数据稀疏等问题影响&#xff0c;算法推荐效果不尽如人意。为解决上述问题&#xff0c;本文提出了一种改进的聚类…...

云计算项目十一:构建完整的日志分析平台

检查k8s集群环境&#xff0c;master主机操作&#xff0c;确定是ready 启动harbor [rootharbor ~]# cd /usr/local/harbor [rootharbor harbor]# /usr/local/bin/docker-compose up -d 检查head插件是否启动&#xff0c;如果没有&#xff0c;需要启动 [rootes-0001 ~]# system…...

2.经典项目-海量用户即使通讯系统

1.实现功能-完成注册用户 完成用户注册的步骤(客户端) 1.将User移动到common/message文件夹下 2.在message中新增注册用户的结构体 const (LoginMesType "LoginMes"LoginResMesType "LoginResMes"RegisterMesType "RegisterMes"…...

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的交通标志识别系统详解(深度学习模型+UI界面代码+训练数据集)

摘要&#xff1a;本篇博客详细介绍了利用深度学习构建交通标志识别系统的过程&#xff0c;并提供了完整的实现代码。该系统采用了先进的YOLOv8算法&#xff0c;并与YOLOv7、YOLOv6、YOLOv5等早期版本进行了性能评估对比&#xff0c;分析了性能指标如mAP、F1 Score等。文章深入探…...

VMware下创建虚拟机

Centos7是比较常用的一个Linux发行版本&#xff0c;在国内的使用比例比较高 安装完VMware一定要检查虚拟网卡有没有安装成功&#xff0c;如果没有VMnet1和VMnet8 虚拟机是无法上网的&#xff0c;就需要卸载重启电脑重新安装 控制面板—网络和Internet—网络连接 快捷方式打开&a…...

基于Ambari搭建大数据分析平台

一、部署工具简介 1. Hadoop生态系统 Hadoop big data ecosystem in Apache stack 2. Hadoop的发行版本 Hadoop的发行版除了Apache的开源版本之外&#xff0c;国外比较流行的还有&#xff1a;Cloudera发行版(CDH)、Hortonworks发行版&#xff08;HDP&#xff09;、MapR等&am…...

Vue template到render过程,以及render的调用时机

Vue template到render过程 vue的模版编译过程主要如下&#xff1a;template -> ast -> render函数&#xff08;1&#xff09;调用parse方法将template转化为ast&#xff08;抽象语法树&#xff09;&#xff08;2&#xff09;对静态节点做优化&#xff08;3&#xff09;生…...

阿里云服务器Ngnix配置SSL证书开启HTTPS访问

文章目录 前言一、SSL证书是什么&#xff1f;二、如何获取免费SSL证书三、Ngnix配置SSL证书总结 前言 很多童鞋的网站默认访问都是通过80端口的Http服务进行访问&#xff0c;往往都会提示不安全&#xff0c;很多人以为Https有多么高大上&#xff0c;实际不然&#xff0c;他只是…...

12 list的使用

文档介绍 文档介绍 1.list是可以在常数范围内的任意位置进行插入和删除的序列式容器&#xff0c;并且该容器可以前后双向迭代 2.list的底层是带头双向链表循环结构&#xff0c;双向链表中每个元素存储在互不相关的独立节点中&#xff0c;在节点中通过指针指向其前一个元素和…...

控件交互与视图交互的区别

在实际应用中&#xff0c;控件交互和视图交互的区别主要体现在以下几个方面&#xff1a; (1)关注的对象不同&#xff1a;控件交互更关注于界面中的单个控件如何响应用户的操作&#xff0c;例如按钮的点击、列表项的滑动等。而视图交互则更关注于整个界面的布局、导航和交互设计…...

打包 加載AB包 webGl TextMeshPro 變紫色的原因

1.打包 加載AB包 webGl TextMeshPro 變紫色的原因 編輯器命令行https://docs.unity3d.com/cn/2019.4/Manual/CommandLineArguments.html 1.UnityHub 切換命令行參數 -force-gles 2.-force-gles&#xff08;仅限 Windows&#xff09;| 使 Editor 使用 OpenGL for Embedded Sys…...

美易官方:去年全球企业派息1.66万亿美元创新高

去年全球企业派息总额达到了1.66万亿美元&#xff0c;创下了历史新高。这一数字不仅彰显了全球企业的盈利能力和财务稳健性&#xff0c;也反映了它们对股东的责任感和对未来发展的信心。在这一背景下&#xff0c;微软和苹果这两家科技巨头在派息方面的表现尤为引人注目。 微软是…...

基于Springboot的面向智慧教育的实习实践系统设计与实现(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的面向智慧教育的实习实践系统设计与实现&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&…...

【数据库-黑马笔记】基础-SQL

本文参考b站黑马数据库视频,总结详细全面的笔记 ,可结合视频观看1~26集 MYSQL 的基础知识框架如下 目录 一、MYSQL概述 1、数据库相关概念 2、MYSQL的安装及启动 二、SQL 1、DDL【Data Defination】 2、DML【Data Manipulation】 ①、插入 ②、更新和删除 3、 DQL【Data…...

MySQL性能分析:性能模式和慢查询日志的使用

目录 一、性能模式 步骤1. 启用性能模式 步骤2. 查询性能数据 步骤3. 分析性能数据 步骤4. 优化与调整 注意事项 二、慢查询日志 步骤1. 启用慢查询日志...

【哈希表算法题记录】15. 三数之和,18. 四数之和——双指针法

题目链接 15. 三数之和 思路 这题虽然放在哈希表的分类里面&#xff0c;但是用双指针法会更高效。 之前的双指针我们要么是一头left一尾right&#xff0c;要么是快fast慢slow指针。这里是要计算三个数的和&#xff0c;我们首先对数组进行从小到大的排序&#xff0c;先固定一…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践

在电商行业蓬勃发展的当下&#xff0c;多平台运营已成为众多商家的必然选择。然而&#xff0c;不同电商平台在商品数据接口方面存在差异&#xff0c;导致商家在跨平台运营时面临诸多挑战&#xff0c;如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...