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

【排序算法】快速排序(Quick Sort)

快速排序(Quick Sort)使用分治法算法思想。

快速排序介绍

它的基本思想是: 选择一个基准数,通过一趟排序将要排序的数据分割成独立的两部分;其中一部分的所有数据都比另外一部分的所有数据都要小。然后,再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序实现

  • 从数列中挑出一个基准值。

  • 将所有比基准值小的摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边);在这个分区退出之后,该基准就处于数列的中间位置。

  • 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。

下面以数列a={30,40,60,10,20,50}为例,演示它的快速排序过程(如下图)。

上图只是给出了第1趟快速排序的流程。在第1趟中,设置x=a[i],即x=30。

  • 从"右 --> 左"查找小于x的数: 找到满足条件的数a[j]=20,此时j=4;然后将a[j]赋值a[i],此时i=0;接着从左往右遍历。

  • 从"左 --> 右"查找大于x的数: 找到满足条件的数a[i]=40,此时i=1;然后将a[i]赋值a[j],此时j=4;接着从右往左遍历。

  • 从"右 --> 左"查找小于x的数: 找到满足条件的数a[j]=10,此时j=3;然后将a[j]赋值a[i],此时i=1;接着从左往右遍历。

  • 从"左 --> 右"查找大于x的数: 找到满足条件的数a[i]=60,此时i=2;然后将a[i]赋值a[j],此时j=3;接着从右往左遍历。

  • 从"右 --> 左"查找小于x的数: 没有找到满足条件的数。当i>=j时,停止查找;然后将x赋值给a[i]。此趟遍历结束!

按照同样的方法,对子数列进行递归遍历。最后得到有序数组!

快速排序时间复杂度和稳定性

快速排序稳定性

快速排序是不稳定的算法,它不满足稳定算法的定义。

算法稳定性 -- 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!

快速排序时间复杂度

快速排序的时间复杂度在最坏情况下是O(N2),平均的时间复杂度是O(N*lgN)。

这句话很好理解: 假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N),需要遍历多少次呢? 至少lg(N+1)次,最多N次。

  • 为什么最少是lg(N+1)次? 快速排序是采用的分治法进行遍历的,我们将它看作一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的定义,它的深度至少是lg(N+1)。因此,快速排序的遍历次数最少是lg(N+1)次。

  • 为什么最多是N次? 这个应该非常简单,还是将快速排序看作一棵二叉树,它的深度最大是N。因此,快读排序的遍历次数最多是N次。

代码实现

/*** 快速排序: Java** @author skywang* @date 2014/03/11*/public class QuickSort {/** 快速排序** 参数说明: *     a -- 待排序的数组*     l -- 数组的左边界(例如,从起始位置开始排序,则l=0)*     r -- 数组的右边界(例如,排序截至到数组末尾,则r=a.length-1)*/public static void quickSort(int[] a, int l, int r) {if (l < r) {int i,j,x;i = l;j = r;x = a[i];while (i < j) {while(i < j && a[j] > x)j--; // 从右向左找第一个小于x的数if(i < j)a[i++] = a[j];while(i < j && a[i] < x)i++; // 从左向右找第一个大于x的数if(i < j)a[j--] = a[i];}a[i] = x;quickSort(a, l, i-1); /* 递归调用 */quickSort(a, i+1, r); /* 递归调用 */}}public static void main(String[] args) {int i;int a[] = {30,40,60,10,20,50};System.out.printf("before sort:");for (i=0; i<a.length; i++)System.out.printf("%d ", a[i]);System.out.printf("\n");quickSort(a, 0, a.length-1);System.out.printf("after  sort:");for (i=0; i<a.length; i++)System.out.printf("%d ", a[i]);System.out.printf("\n");}
}

相关文章:

【排序算法】快速排序(Quick Sort)

快速排序(Quick Sort)使用分治法算法思想。快速排序介绍它的基本思想是: 选择一个基准数&#xff0c;通过一趟排序将要排序的数据分割成独立的两部分&#xff1b;其中一部分的所有数据都比另外一部分的所有数据都要小。然后&#xff0c;再按此方法对这两部分数据分别进行快速排…...

SpringIOC之创建Bean的核心方法doGetBean

概述面向资源&#xff08;XML、Properties&#xff09;、面向注解定义的 Bean 是如何被解析成 BeanDefinition&#xff08;Bean 的“前身”&#xff09;&#xff0c;并保存至 BeanDefinitionRegistry 注册中心里面&#xff0c;实际也是通过 ConcurrentHashMap 进行保存。Spring…...

docker快速部署xxjob2.3.0-SpringBoot快速集成示例

xxjob 2.3.0 部署 参考资料 docker安装xxl-job-admin步骤_JEECG低代码平台的技术博客_51CTO博客 run前准备 1 新建数据库 xxl_job 2 建表sql(可以直接使) https://github.com/xuxueli/xxl-job/blob/master/doc/db/tables_xxl_job.sql建库sql # # XXL-JOB v2.4.0-SNAPSHOT…...

项目管理的前路,前辈能给一些意见吗?

什么是项目管理&#xff1f;关于项目管理的解释主要是基于国际项目管理三大体系不同的解释及本领域权威专家的解释!!!! 项目管理就是以项目为对象的系统管理方法&#xff0c;通过一个临时性的、专门的柔性组织&#xff0c;对项目进行高效率的计划、组织、指导和控制&#xff0c…...

省钱的年轻人,钱包被折扣店钻了空子

【潮汐商业评论/原创】过年期间&#xff0c;除了商场超市&#xff0c;小区附近的折扣店成了Amy经常光顾的对象。用Amy的话来说&#xff0c;“跟附近超市比价格&#xff0c;跟大卖场比距离&#xff0c;综合下来折扣店就是我随时购物的不二选择。”从Amy的话里&#xff0c;我们可…...

【华为OD机试真题 js、python】优选核酸检测点、寻找核酸检测点【2022 Q4 100分】

代码请进行一定修改后使用,提供有js、python两种语言 题目描述 张三要去外地出差,需要做核酸,需要在指定时间点前做完核酸,请帮他找到满足条件的 核酸检测只点。 给出一组核酸检测点的距离和每个核酸检测点当前的人数给出张三要去做核酸的出发时间 出发时间是10分钟的倍数…...

【MySQL】MySQL 8.0 新特性之 - 公用表表达式(CTE)

MySQL 8.0 新特性之 - 公用表表达式&#xff08;CTE&#xff09;1. 公用表表达式&#xff08;CTE&#xff09; - WITH 介绍1.1 公用表表表达式1.1.1 什么是公用表表达式1.1.2 CTE 语法1.1.3 CTE示例1.3 递归 CTE1.3.1 递归 CTE 简介1.3.2 递归成员限制1.3.3 递归 CTE 示例1.3.4…...

基础面试题:C++中如何理解const修饰符

面试题目&#xff1a;1、题 int i10; const int*p &i; int *const* p &i; const在不同位置有什么不 同 2、const 修饰类成员变量是有什么特殊要求 3、const 修饰类成员函数会发什么 4、const 对象有什么意义 目录 前言 一、const的意义 二、const使用规则 1.初始化…...

在RT-Thread STM32F407平台下配置SPI flash为U盘

记录下SPI Flash U盘实现过程中踩过的坑&#xff0c;与您分享。前提条件是&#xff0c;需要先将SPI Flash 配置到elm fal文件系统&#xff0c;并挂载成功。如下图然后开始配置USB1&#xff0c;在CubeMX&#xff0c;选择SUB_OTG_FS2 选择USB Device3&#xff0c;确认USB时钟为48…...

数据存储技术复习(二)未完

module3存储是数据中心内的核心元素。请说明常用的存储选项及其特点。磁盘驱动器&#xff1a;具有很大的存储容量&#xff0c;随机读/写访问闪存驱动器&#xff1a;使用半导体介质&#xff0c;提供高性能&#xff0c;低功耗2&#xff0e;若某磁盘驱动器显示每个磁道有八个扇区&…...

使用 QuTrunk+Amazon Deep Learning AMI(TensorFlow2)构建量子神经网络

量子神经网络是基于量子力学原理的计算神经网络模型。1995年&#xff0c;Subhash Kak 和 Ron Chrisley 独立发表了关于量子神经计算的第一个想法&#xff0c;他们致力于量子思维理论&#xff0c;认为量子效应在认知功能中起作用。然而&#xff0c;量子神经网络的典型研究涉及将…...

python selenium浏览器复用技术

使用selenium 做web自动化的时候&#xff0c;经常会遇到这样一种需求&#xff0c;是否可以在已经打开的浏览器基础上继续运行自动化脚本&#xff1f; 这样前面的验证码登录可以手工点过去&#xff0c;后面页面使用脚本继续执行&#xff0c;这样可以解决很大的一个痛点。 命令行…...

第二章:创建虚拟机

创建Windows server&#xff1a;首先第一步就是打开我们的vm&#xff0c;然后找到上一章讲的主页图标创建新的虚拟机。点击这上面类似的&#xff0c;然后转站。博文地址&#xff1a;https://blog.csdn.net/ryduijftgvhj/article/details/127934939?spm1001.2014.3001.5502视频…...

码上【call,apply,bind】的手写

一、call &#xff08;1&#xff09;官方用法 call() 方法使用一个指定的 this 值和单独给出的一个或多个参数来调用一个函数。 语法&#xff1a;function.call(要绑定的this值&#xff0c;参数&#xff0c;参数&#xff0c;…)。不一定这些参数都需要&#xff0c;这些参数都…...

代谢组学Nature子刊!抑郁症居然“男女有别”,脑膜淋巴管起关键作用!

文章标题&#xff1a;A functional role of meningeal lymphatics in sex difference of stress susceptibility in mice 发表期刊&#xff1a;Nature Communications 影响因子&#xff1a;17.694 发表时间&#xff1a;2022年8月 作者单位&#xff1a;中山大学中山医学院 …...

nacos配置中心搭建

网站每次更新版本都有短暂暂停&#xff0c;影响用户使用&#xff0c;返回经常不可用&#xff0c;需要改进 需要实现高可用&#xff0c;搭建负载均衡&#xff0c;实现jenkinsnacos不停机部署 nacos搭建预备环境准备 64 bit OS&#xff0c;支持 Linux/Unix/Mac/Windows&#x…...

uni-app低成本封装一个取色器组件

在uni-ui中找不到对应的工具 后面想想也是 移动端取色干什么&#xff1f; 没办法 也挂不住特殊需求 因为去应用市场下载 这总东西 又不是很有必要 那么 下面这个组件或许能解决您的烦恼 <template><view class"content"><view class"dialog&…...

APP 怎么免费接入 MobPush

1、获取 AppKey 申请 Appkey 的流程&#xff0c;请点击 http://bbs.mob.com/thread-8212-1-1.html?fromuid70819 2、下载 SDK 下载解压后&#xff0c;如下图&#xff1a; 目录结构 &#xff08;1&#xff09;Sample&#xff1a;演示Demo。&#xff08;2&#xff09;SDK&am…...

XGBoost

目录 1.XGBoost推导示意图 2.分裂节点算法 Weighted Quantile Sketch 3.对缺失值得处理 1.XGBoost推导示意图 XGBoost有两个很不错得典型算法&#xff0c;分别是用来进行分裂节点选择和缺失值处理 2.分裂节点算法 Weighted Quantile Sketch 对于特征切点点得选择&#xff…...

你是什么时候从轻视到高看软件测试的?

刚开始学软件测试很轻视&#xff0c;因为我那时很无知&#xff0c;这也是那时绝大多数人员的心态&#xff0c;那时中国最讲究“编程才是硬道理”。 如今却非常热爱软件测试&#xff0c;包括软件测试工具&#xff0c;方法&#xff0c;理论&#xff0c;技术。因为我在3年的测试工…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

关于 WASM:1. WASM 基础原理

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

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...