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

基础算法--快速排序

快速排序

算法原理

1. 取一个元素p(第一个元素,最后一个元素,中间元素,随机 都可以),使元素p归位。
2. 列表被p分成两部分,左边都比p小,右边都比p大。
3. 递归完成排序。

在这里插入图片描述

动态演示

在这里插入图片描述

python代码实现

import sys
import time# 修改递归最大深度
sys.setrecursionlimit(100000)def partition(li, left, right):# 先把最左边的值拿出来,放入tmp变量临时存储tmp = li[left]# 循环条件 左边指针一直小于右边指针while left < right:# 从最右边找比tmp小的数,放入tmp位置while left < right and li[right] >= tmp:right -= 1# 把右边的值写道左边空位上li[left] = li[right]while left < right and li[left] <= tmp:left += 1# 把左边的值写道右边的空位上li[right] = li[left]# 当左右指针相等,就是碰头了,把最左边取出来的值,放入中间左右指针碰头的地方li[left] = tmp  # 把tmp归位return leftdef quick_sort(li, left, right):# 至少两个元素if left < right:mid = partition(li, left, right)quick_sort(li, left, mid - 1)quick_sort(li, mid + 1, right)li = [5, 7, 4, 6, 3, 1, 2, 9, 8]
print(li)
quick_sort(li, 0, len(li) - 1)
print(li)

C++代码实现 同上方python代码

#include <iostream>
using namespace std;const int N = 1000010;
int a[N];int partition(int a[], int left, int right)
{int tmp = a[left];while(left < right){while(left < right && a[right] >= tmp) {right --;}a[left] = a[right];while(left < right && a[left] <= tmp) {left ++;}a[right] = a[left];}a[left] = tmp;return left;
}void quick_sort(int a[],int left,int right)
{if(left < right){  int mid = partition(a, left, right);quick_sort(a, mid + 1, right);quick_sort(a, left, mid - 1);}
}
int main()
{int n;scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);quick_sort(a, 0, n - 1);for(int i = 0; i < n; i++) printf("%d ", a[i]);return 0;
}

C++代码实现 acwing模板

#include <iostream>
using namespace std;const int N = 1000010;
int a[N];void quick_sort(int a[],int left,int right)
{if(left >= right) return;int tmp = a[(left + right) / 2], q = left - 1, e = right + 1;while(q < e){do q++;while(a[q] < tmp);do e--;while(a[e] > tmp);if(q < e) swap(a[q], a[e]);}quick_sort(a, left, e);quick_sort(a, e + 1, right);
}int main()
{int n;scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);quick_sort(a, 0, n - 1);for(int i = 0; i < n; i++) printf("%d ", a[i]);return 0;
}

相关文章:

基础算法--快速排序

快速排序 算法原理 1. 取一个元素p(第一个元素&#xff0c;最后一个元素&#xff0c;中间元素&#xff0c;随机 都可以)&#xff0c;使元素p归位。 2. 列表被p分成两部分&#xff0c;左边都比p小&#xff0c;右边都比p大。 3. 递归完成排序。 动态演示 python代码实现 import…...

机器学习的第一节基本概念的相关学习

目录 1.1 决策树的概念 1.2 KNN的概念 1.2.1KNN的基本原理 1.2.2 流程&#xff1a; 1.2.3 优缺点 1.3 深度学习 1.4 梯度下降 损失函数 1.5 特征与特征选择 特征选择的目的 1.6 python中dot函数总结 一维数组的点积&#xff1a; 二维数组&#xff08;矩阵&#xff09;的乘法&am…...

Python 之__name__的用法以及解释

文章目录 介绍代码 介绍 __name__ 是一个在 Python 中特殊的内置变量&#xff0c;用于确定一个 Python 文件是被直接运行还是被导入为模块。 文件作为模板导入&#xff0c;则其 __name__属性值被自动设置为模块名 文件作为程序直接运行&#xff0c;则__name__属性属性值被自动设…...

【FPGA零基础学习之旅#12】三线制数码管驱动(74HC595)串行移位寄存器驱动

&#x1f389;欢迎来到FPGA专栏~三线制数码管驱动 ☆* o(≧▽≦)o *☆嗨~我是小夏与酒&#x1f379; ✨博客主页&#xff1a;小夏与酒的博客 &#x1f388;该系列文章专栏&#xff1a;FPGA学习之旅 文章作者技术和水平有限&#xff0c;如果文中出现错误&#xff0c;希望大家能指…...

networkX-03-连通度、全局网络效率、局部网络效率、聚类系数计算

文章目录 1.连通度1.1 检查图是否连通1.2 检查有向图是否为强连通1.3 点连通度、边连通度&#xff1a; 2.网络效率2.1全局效率2.2 局部效率2.2.1 查找子图2.2.3 局部效率源码分析 3.聚类系数&#xff08;Clustering Coefficient&#xff09;3.1 聚类系统源码分析 教程仓库地址&…...

【深入解读Redis系列】Redis系列(五):切片集群详解

首发博客地址 https://blog.zysicyj.top/ 系列文章地址[1] 如果 Redis 内存很大怎么办&#xff1f; 假设一台 32G 内存的服务器部署了一个 Redis&#xff0c;内存占用了 25G&#xff0c;会发生什么&#xff1f; 此时最明显的表现是 Redis 的响应变慢&#xff0c;甚至非常慢。 这…...

无涯教程-JavaScript - NORMDIST函数

NORMDIST函数替代Excel 2010中的NORM.DIST函数。 描述 该函数返回指定均值和标准差的正态分布。此功能在统计中有非常广泛的应用,包括假设检验。 语法 NORMDIST(x,mean,standard_dev,cumulative)争论 Argument描述Required/OptionalXThe value for which you want the dis…...

递归应用判断是否循环引用

var data await _IDBInstance.DBOperation.QueryAsync<FormulaReference>(sql);//向上查询引用公式 List<FormulaReference> GetSonNode(long id, List<FormulaReference> nodeList, List<long> path null){if (path null){path new List<long…...

使用nginx-lua配置统一url自动跳转到hadoop-ha集群的active节点

下载安装nginx所用的依赖 yum -y install gcc zlib zlib-devel pcre-devel openssl openssl-devel下载nginx wget http://nginx.org/download/nginx-1.12.2.tar.gz tar -xvf nginx-1.12.2.tar.gz稍后安装nginx 安装lua语言 yum install readline-develcurl -R -O http://w…...

AJAX学习笔记2发送Post请求

AJAX学习笔记1发送Get请求_biubiubiu0706的博客-CSDN博客 继续 AJAX发送POST请求 无参数 测试 改回来 测试 AJAX POST请求 请求体中提交参数 测试 后端打断点 如何用AJAX模拟form表单post请求提交数据呢&#xff1f; 设置请求头必须在open之后,send之前 请求头里的设置好比…...

产品团队的需求分析指南

需求分析是软件开发流程中需求识别与管理的关键环节&#xff0c;需求分析的目的在于确保所有产品需求准确地代表了利益相关者的需求和要求。选择合适的需求分析方式可以帮助我们获取准确的产品需求&#xff0c;从而保证我们所交付的成果与利益相关者预期相符。 一、什么是需求…...

Python算法——排序算法(冒泡、选择、插入、快速、堆排序、并归排序、希尔、计数、桶排序、基数排序)

本文章只展示代码实现 &#xff0c;原理大家可以参考&#xff1a; https://zhuanlan.zhihu.com/p/42586566 一、冒泡排序 def bubble_sort(lst):for i in range(len(lst) - 1): # 表示第i趟exchange False # 每一趟做标记for j in range(len(lst)-i-1): # 表示箭头if ls…...

[Linux]文件描述符(万字详解)

[Linux]文件描述符 文章目录 [Linux]文件描述符文件系统接口open函数close函数write函数read函数系统接口与编程语言库函数的关系 文件描述符文件描述符的概念文件数据交换的原理理解“一切皆文件”进程默认文件描述符文件描述符和编程语言的关系 重定向输出重定向输入重定向追…...

RenderTarget导出成图片,CineCamera相机

一、获取Cinecamera相机图像 1.1、启用UE自带插件 1.2、在UE编辑器窗口栏找到Composure合成&#xff0c;打开窗口 1. 3、右键空白处&#xff0c;新建合成&#xff0c;默认名称为 0010_comp&#xff1b;再右键新建的 0010_comp&#xff0c;新建图层元素 CGLayer层&#xff0c;默…...

深入探讨Java虚拟机(JVM):执行流程、内存管理和垃圾回收机制

目录 什么是JVM&#xff1f; JVM 执行流程 JVM 运行时数据区 堆&#xff08;线程共享&#xff09; Java虚拟机栈&#xff08;线程私有&#xff09; 什么是线程私有? 程序计数器&#xff08;线程私有&#xff09; 方法区&#xff08;线程共享&#xff09; JDK 1.8 元空…...

3D 碰撞检测

推荐&#xff1a;使用 NSDT场景编辑器快速搭建3D应用场景 轴对齐边界框 与 2D 碰撞检测一样&#xff0c;轴对齐边界框 &#xff08;AABB&#xff09; 是确定两个游戏实体是否重叠的最快算法。这包括将游戏实体包装在一个非旋转&#xff08;因此轴对齐&#xff09;的框中&#…...

Unity Canvas动画不显示的问题

问题描述: 我通过角色创建了一个walk的动画&#xff0c;当我把这个动画给到Canvas里面的一个image上&#xff0c;这个动画就不能正常播放了&#xff0c;经过一系列的查看我才发现&#xff0c;canvas里面动画播放和非canvas得动画播放&#xff0c;他们的动画参数是不一样的。一个…...

NSSCTF2nd与羊城杯部分记录

文章目录 前言[NSSCTF 2nd]php签到[NSSCTF 2nd]MyBox[NSSCTF 2nd]MyHurricane[NSSCTF 2nd]MyJs[NSSCTF 2nd]MyAPK羊城杯[2023] D0nt pl4y g4m3!!!羊城杯[2023]ezyaml羊城杯[2023]Serpent羊城杯[2023]EZ_web羊城杯[2023]Ez_misc总结 前言 今天周日&#xff0c;有点无聊没事干&a…...

数据库(一) 基础知识

概述 数据库是按照数据结构来组织,存储和管理数据的仓库 数据模型 数据库系统的核心和基础是数据模型&#xff0c;数据模型是严格定义的一组概念的集合。因此数据模型一般由数据结构、数据操作和完整性约束三部分组成。数据模型主要分为三种:层次模型&#xff0c;网状模型和关…...

vue从零开始学习

npm install慢解决方法:删掉nodel_modules。 5.0.3:表示安装指定的5.0.3版本 ~5.0.3:表示安装5.0X中最新的版本 ^5.0.3: 表示安装5.x.x中最新的版本。 yarn的优点: 1.速度快,可以并行安装 2.安装版本统一 项目搭建: 安装nodejs查看node版本:node -v安装vue clie : np…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...