当前位置: 首页 > 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…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...