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

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...