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

算法程序设计-快速排序

快速排序采用---分治策略

L |------x-------------| R

第一步确定分界点:q[l],q[(l+r)/2],q[r]随机

第二步调整范围:L |--------<=x|>=x------------| R

第三步递归处理左右两端

两种做法:

第一种:暴力解决

另外定义两个数组a[],b[]

判断q中的数组元素与x进行比较,小于x的放进a,大于x的放进b

最后将a,b放进数组q中,可以实现,左边的均小于x,右面的均大于x。

时间复杂度为o(n),可以考虑

优雅的做法:

在头部和尾部分别定义两个指针,两个指针同时往中间走,

左面的指针先走,当左面指针对应的数据小于x时,继续往后走,当左面指针对应的数据大于x时,i就停下来,则去移动j指针,同理当j大于x时,指针向左移动,当j小于x时,指针停止。

当两个指针都停止时,进行swap交换,那么交换完,继续按照以上步骤执行直到i和j相遇,那么左面的数据均小于x,右面的数据均大于x。

边界问题背算法

#include<iostream>
using namespace std;const int N=1e6+10;
int n;
int q[N];void quick_sort(int q[],int l,int r){if(l>=r)return;int x=q[(l+r) / 2],i=l-1,j=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(){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&q[i]);}quick_sort(q,0,n-1);for(int i=0;i<n;i++){printf("%d",&q[i]);}}

注意边界值要取中间值,边界值容易死循环

相关文章:

算法程序设计-快速排序

快速排序采用---分治策略 L |------x-------------| R 第一步确定分界点&#xff1a;q[l],q[(lr)/2],q[r]随机 第二步调整范围&#xff1a;L |--------<x|>x------------| R 第三步递归处理左右两端 两种做法&#xff1a; 第一种&#xff1a;暴力解决 另外定义两个…...

Jmeter用jdbc实现对数据库的操作

我们在用Jmeter进行数据库的操作时需要用到配置组件“JDBC Connection Configuration”&#xff0c;通过配置相应的驱动能够让我们通过Jmeter实现对数据库的增删改查&#xff0c;这里我用的mysql数据库一起来看下是怎么实现的吧。 1.驱动包安装 在安装驱动之前我们要先查看当前…...

Mac 上安装多版本的 JDK 且实现 自由切换

背景 当前电脑上已经安装了 jdk8; 现在再安装 jdk17。 期望 完成 jdk17 的安装&#xff0c;并且完成 环境变量 的配置&#xff0c;实现自由切换。 前置补充知识 jdk 的安装路径 可以通过查看以下目录中的内容&#xff0c;确认当前已经安装的 jdk 版本。 cd /Library/Java/Java…...

springboot如何发送邮件,java如何发送邮件随机码作为验证

maven <dependency><groupId>com.sun.mail</groupId><artifactId>javax.mail</artifactId><version>1.6.2</version></dependency> 然后java package com.metasoft.common.utils;import java.util.Properties;import javax.…...

使用QLoRA在自定义数据集上finetuning 大模型 LLAMA3 的数据比对分析

概述: 大型语言模型(LLM)展示了先进的功能和复杂的解决方案,使自然语言处理领域发生了革命性的变化。这些模型经过广泛的文本数据集训练,在文本生成、翻译、摘要和问答等任务中表现出色。尽管LLM具有强大的功能,但它可能并不总是与特定的任务或领域保持一致。 什么是LL…...

编译和链接(超详细)

✅博客主页:爆打维c-CSDN博客​​​​​​ &#x1f43e; &#x1f539;分享c语言知识及代码 一、编译和链接实例 假设我们有一个名为main.c的C语言源文件&#xff0c;它包含了一个简单的Hello World程序。我们可以使用gcc编译器对该源文件进行编译&#xff0c;生成一个可执行…...

Rust Turbofish 的由来

0x01 什么是 Turbofish 我们运行如下 Rust Snippet&#xff1a; fn main() {let numbers: Vec<i32> vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];let even_numbers numbers.into_iter().filter(|n| n % 2 0).collect();println!("{:?}", even_numbers); }不出意…...

2.外卖点餐系统(Java项目 springboot)

目录 0.系统的受众说明 1.系统功能设计 2.系统结构设计 3.数据库设计 3.1实体ER图 3.2数据表 4.系统实现 4.1用户功能模块 4.2管理员功能模块 4.3商家功能模块 4.4用户前台功能模块 4.5骑手功能模块 5.相关说明 新鲜运行起来的项目&#xff1a;如需要源码数据库…...

Universal Thresholdizer:将多种密码学原语门限化

参考文献&#xff1a; [LS90] Lapidot D, Shamir A. Publicly verifiable non-interactive zero-knowledge proofs[C]//Advances in Cryptology-CRYPTO’90: Proceedings 10. Springer Berlin Heidelberg, 1991: 353-365.[Shoup00] Shoup V. Practical threshold signatures[C…...

【UE5学习笔记】编辑及运行界面:关闭眼部识别(自动曝光)

自动曝光&#xff0c;也就是走进一个黑暗的环境&#xff0c;画面会逐渐变量&#xff0c;以模拟人眼进入黑暗空间时瞳孔放大&#xff0c;进光量增加的一种真实视觉感受&#xff1a; 制作过程中是否关闭自动曝光&#xff0c;取决于游戏的性质&#xff0c;但是个人认为&#xff0c…...

未来科技的前沿:深入探讨人工智能的进展、机器学习技术和未来趋势

文章目录 一、人工智能的定义和概述1. 人工智能的基本概念2. 人工智能的发展历史 二、技术深入&#xff1a;机器学习、深度学习和神经网络1. 机器学习2. 深度学习3. 神经网络 三、人工智能的主要目标和功能1. 自动化和效率提升2. 决策支持和风险管理3. 个性化服务和预测未来 本…...

3-qt综合实例-贪吃蛇的游戏程序

引言&#xff1a; 如题&#xff0c;本次实践课程主要讲解贪吃蛇游戏程序。 qt贪吃蛇项目内容&#xff1a; 一、功能需求 二、界面设计 各组件使用&#xff1a; 对象名 类 说明 Widget QWidge 主窗体 btnRank QPushButton 排行榜-按钮 groupBox QGroupBox 难…...

QGraphicsView实现简易地图12『平移与偏移』

前文链接&#xff1a;QGraphicsView实现简易地图11『指定层级-定位坐标』 提供地图平移与偏移功能。地图平移是指将地图的中心点更改为给定的点&#xff0c;即移动地图到指定位置。地图偏移是指将当前视口内的地图向上/下/左/右/进行微调&#xff0c;这里偏移视口宽/高的四分之…...

深入探索 Vue 中的 createVNode 与 resolveComponent

在 Vue 开发中&#xff0c;createVNode和resolveComponent是两个至关重要的工具&#xff0c;它们为我们提供了强大的能力来灵活地创建和操控组件。 一、首先&#xff0c;让我们深入了解一下createVNode。 这是一个用于创建虚拟节点的关键函数&#xff0c;通过它&#xff0c;我…...

【记录42】centos 7.6安装nginx教程详细教程

环境&#xff1a;腾讯云centos7.6 需求&#xff1a;安装nginx-1.24.0 1. 切入home文件 cd home 2. 创建nginx文件 mkdir nginx 3. 切入nginx文件 cd nginx 4. 下载nginx安装包 wget https://nginx.org/download/nginx-1.24.0.tar.gz 5. 解压安装包 tar -zxvf nginx-1.24.0.…...

C语言程序设计(不熟悉的点)

一、switch多路分支语句 二、条件表达式 三、循环 for循环&#xff1a; for循环的三个表达式不是必须的&#xff0c;第一个表达式之前声明过&#xff0c;可以不写&#xff0c;第三个表达式可以放在循环体里面&#xff1b;第二个表达式可以不写&#xff0c;为死循环。 空循环…...

DAO是什么?有什么用途?

DAO&#xff08;Decentralized Autonomous Organization&#xff0c;去中心化自治组织&#xff09;是一种基于区块链技术的组织形式&#xff0c;它没有中央管理层&#xff0c;而是通过智能合约和区块链上的代码来运作。DAO 的决策过程是透明的&#xff0c;通常由组织的成员通过…...

Socket学习记录

本次学习Socket的编程开发&#xff0c;该技术在一些通讯软件&#xff0c;比如说微信&#xff0c;QQ等有广泛应用。 网络结构 这些都是计算机网络中的内容&#xff0c;我们在这里简单回顾一下&#xff1a; UDP(User Datagram Protocol):用户数据报协议;TCP(Transmission Contr…...

黑马 - websocket搭建在线聊天室

这里写自定义目录标题 一、消息推送常见方式二、websocket 是什么&#xff1f;三、websocket api的介绍1、客户端 &#xff08;浏览器&#xff09;2、服务端api 四、实现在线聊天室1、需求2、聊天室流程分析3、消息格式4、代码实现 一、消息推送常见方式 1、轮训方式 2、SSE…...

【每日力扣】543. 二叉树的直径与101. 对称二叉树

&#x1f525; 个人主页: 黑洞晓威 &#x1f600;你不必等到非常厉害&#xff0c;才敢开始&#xff0c;你需要开始&#xff0c;才会变的非常厉害 543. 二叉树的直径 给你一棵二叉树的根节点&#xff0c;返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

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

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

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...