常见排序算法总结 (四) - 快速排序与随机选择
快速排序
算法思想
每一轮在数组相应的范围上随机找一个元素进行划分,将不大于它的所有元素都放到左边,将大于它的元素都放到右边。在左右两个子数组上不断地递归,直到整个数组上有序。
注意:实现时选择的时参考荷兰国旗问题优化后的快排算法,它会在一次划分中维护一个包含所有等于划分标准元素的区间,保证小于该数的都在区间左侧,大于该数的都在区间右侧。这样的做法,在一定程度上能够减少划分次数。
稳定性分析
快速排序是不稳定的,它涉及到拆分区间,无法保证相等的数一定在同一个区间上被处理完成,也就无法保证它们的相对次序不发生变化。
具体实现
// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}// 全局变量 first 表示等于当前元素的第一个下标位置,last 表示最后一个
public static int first, last;private void quickSort(int[] arr, int left, int right) {// 无法构成区间,直接返回if (left >= right) {return;}// 在合法范围内随机一个元素作为划分标准int pivot = arr[left + (int) (Math.random() * (right - left + 1))];// 划分并递归处理左右子数组partition(arr, left, right, pivot);quickSort(arr, left, first - 1);quickSort(arr, last + 1, right);
}public void partition(int[] arr, int left, int right, int pivot) {first = left;last = right;int cur = left;while (cur <= last) {if (arr[cur] == pivot) {cur++; // 当前元素等于划分标准,不作处理并后移指针} else if (arr[cur] < pivot) {swap(arr, first++, cur++); // 小于划分标准,交换且分别后移两个指针} else {swap(arr, cur, last--); // 大于划分标准,交换并前移记录最后一个当前元素的指针}}
}
随机选择
算法思想
随机选择是基于快排的划分操作,能够快速地确定一个数在数组中排序后的理论位置。这部分内容其实和排序关系不大,但是与快排有很大的关联,可以放在一起整理。
实践案例:Leetcode 215. 数组中的第K个最大元素
class Solution {public int findKthLargest(int[] nums, int k) {return randomizedSelect(nums, nums.length - k);}// 全局变量 first 表示等于当前元素的第一个下标位置,last 表示最后一个public static int first, last;public int randomizedSelect(int[] arr, int cur) {int res = 0;for (int left = 0, right = arr.length - 1; left <= right;) {partition(arr, left, right, arr[left + (int) (Math.random() * (right - left + 1))]);if (cur < first) {right = first - 1; // 当前下标小于维护的第一个下标,到左边区间中找} else if (cur > last) {left = last + 1; // 当前下标大于维护的最后一个下标,到右边区间中找} else {res = arr[cur]; // 当前下标在维护的范围内,记录结果break;}}return res;}// 交换数组中的两个元素private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public void partition(int[] arr, int left, int right, int pivot) {first = left;last = right;int cur = left;while (cur <= last) {if (arr[cur] == pivot) {cur++; // 当前元素等于划分标准,不作处理并后移指针} else if (arr[cur] < pivot) {swap(arr, first++, cur++); // 小于划分标准,交换且分别后移两个指针} else {swap(arr, cur, last--); // 大于划分标准,交换并前移记录最后一个当前元素的指针}}}
}
梳理总结
快速排序的理论复杂度是 O ( N l o g N ) O(NlogN) O(NlogN),它通过划分来不断减小问题规模从而快速解决问题。但是实践中存在能使快排退化到 O ( N 2 ) O(N ^ 2) O(N2) 的阴间待排序列,因此需要通过随机划分标准这个手段来让时间复杂度尽可能地稳定在 O ( N l o g N ) O(NlogN) O(NlogN)。
随机选择算法,本质上是根据不同的标准,维护相应的数值区间。它能够在理论实践复杂度 O ( N ) O(N) O(N) 且不需要额外空间的情况下找出数组中第 K K K 大的数。
后记
使用 Leetcode 912. 排序数组 进行测试,随机快速排序能够比较高效地完成任务。
实际运行下来和归并排序之间都有一些差距,猜测原因是随机操作的耗时很大,并且 Leetcode 平台上专门设置了卡快排的用例。
相关文章:
常见排序算法总结 (四) - 快速排序与随机选择
快速排序 算法思想 每一轮在数组相应的范围上随机找一个元素进行划分,将不大于它的所有元素都放到左边,将大于它的元素都放到右边。在左右两个子数组上不断地递归,直到整个数组上有序。 注意:实现时选择的时参考荷兰国旗问题优化…...
Doris的基础架构
Doris的基础架构 Frontend(FE):主要负责用户请求的接入、查询解析规划、元数据的管理、节点管理相关工作。Backend(BE):主要负责数据存储、查询计划的执行。 我的Github地址,欢迎大家加入我的开…...
python录制鼠标键盘操作循环播放
依赖 pip install pynput 程序: from pynput import mouse, keyboard import time import threading# 用于存储录制的鼠标和键盘事件 mouse_events [] keyboard_events []# 定义事件处理函数# 处理鼠标事件 def on_move(x, y):mouse_events.append((move, x, y))def on_cl…...
标书里的“废标雷区”:你踩过几个?
在投标领域,标书的质量不仅决定了中标的可能性,更是体现企业专业度的关键。但即便是经验丰富的投标人,也难免会在标书编制过程中踩中“废标雷区”。这些雷区可能隐藏在技术方案的细节中,也可能是投标文件格式的规范问题。以下&…...
centos下使用acme来自动获取免费通配符ssl证书,并发布到nginx服务,(DNS服务为阿里云)
参考链接: 官方文档 acme.sh获取证书 # 下载acme的项目 git clone https://gitee.com/neilpang/acme.sh.git # 执行安装脚本 cd acme.sh ./acme.sh --install -m myexample.com # 安装脚本会新增一个定时任务,这个命令可以检查 crontab -l # 从阿里云获取ks,写入 export Ali_…...
基于协同过滤的图书推荐系统 爬虫分析可视化【源码+文档】
【1】系统介绍 研究背景 随着互联网的普及和电子商务的发展,用户可以在线获取大量的图书资源。然而,面对海量的信息,用户往往难以找到自己真正感兴趣的书籍。同时,对于在线书店或图书馆等提供图书服务的平台来说,如何…...
Hyperf jsonrpc
依赖的 composer 包 composer require hyperf/json-rpc composer require hyperf/rpc-server composer require hyperf/rpc-client composer require hyperf/service-governance composer require hyperf/service-governance-consul composer require hyperf/service-gove…...
计算机毕业设计Spark股票推荐系统 股票预测系统 股票可视化 股票数据分析 量化交易系统 股票爬虫 股票K线图 大数据毕业设计 AI
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 作者简介:Java领…...
Linux系统下安装配置 Nginx 超详细图文教程
一、下载Nginx安装包 nginx官网:nginx: downloadhttp://nginx.org/en/download.html找到我们所需要版本,把鼠标移动到上面,右键打开链接进行下载 或者如果Linux联网,直接在Linux服务上使用wget命令把Nginx安装包下载到/usr/local/…...
语言处理程序基础
逻辑运算 正规式 有限自动机 上下文无关文法 表达式(前缀、后缀、中缀) 将表达式(a-b)*(c5)构造成树的步骤为:括号不能出现在树中;按照表达式的计算顺序来依次构造!&…...
golang实现简单的redis服务
golang 手搓redis服务器仓库地址:实现思路: golang 手搓redis服务器 仓库地址: 仓库: https://github.com/dengjiayue/my-redis.git 实现思路: ● 协议: tcp通信 ● 数据包: 长度(4byte)方法(1byte)数据json ● 数据处理: 单线程map读写 ○ 依次处理待处理队列的请求(chan)…...
QT QTableWidget::setModel”: 无法访问 private成员
//严重性代码说明项目文件行禁止显示状态 //错误C2248 “QTableWidget::setModel”: 无法访问 private 成员(在“QTableWidget”类中声明) QSqlQueryModel* sql_model; ui.tableView_database->setModel(sql_model); //ok ui.tableWidget_database->setModel(sql_model)…...
STM32:Bootloader(AB备份,自动回滚)
目录 1.STM32的升级方式2.IAP升级3.代码逻辑展示3.1 划分存储区域3.2 IAP的状态4.源码分析4.1 记录IAP的状态4.2 APP代码异常判断4.3 IAP状态的切换以及异常的处理逻辑4.4 完整的逻辑代码1.STM32的升级方式 1、ICP:In Circuit Programing,简单说就是在单片机开发时使用烧录器…...
数独小游戏(Matlab)
基于Matlab制作的数独小游戏 (完整源码和介绍) 感兴趣可以随时联系博主噢~常在线能秒回! “Matlab数独小游戏”程序设计的关键技术流程和核心算法如下: 1.图形用户界面(GUI):使用MATLAB的GUIDE工具创建和管理用户界面࿰…...
使用docker让项目持续开发和部署
大多人选择开发时在本地,部署时文件都在容器里,如果没有容器,那就本地开发,没有映射文件,如果部署环境到容器了,容器内部启动时设置执行命令,再将映射的文件进行编译,这就直接能实现…...
电子应用设计方案-45:智能火锅系统方案设计
智能火锅系统方案设计 一、引言 随着人们生活水平的提高和对饮食体验的追求,智能火锅系统应运而生。本方案旨在设计一款集智能化控制、高效加热、安全保障和个性化体验于一体的智能火锅系统。 二、系统概述 1. 系统目标 - 实现精准的温度控制,满足不同…...
windows在conda下安装nlpia库
最近在学习《自然语言处理实战》这本书,书中用了其自己的库nlpia,我一直装不上,网上也找不到教程遂放弃,看到现在第四章没办法了,需要用到库里的一些文本语料,又折腾了一天,终于装好了ÿ…...
分布式事务的前世今生-纯理论
一个可用的复杂的系统总是从可用的简单系统进化而来。反过来这句话也正确: 从零开始设计的复杂的系统从来都用不了,也没办法让它变的可用。 --John Gal 《系统学》 1975 1. 事务的概念 百科: 事务(Transaction),一般是…...
apache部署若依前后端分离项目(开启SSL)
网站部署之后,大多数需要配置https,所以本章教程,介绍使用apache部署若依前后端项目的时候,如何开启SSL,以及如何配置SSL证书。 一、安装ssl模块 默认情况下,ssl模块是没有安装的。需要手动安装,否则直接配置SSL模块的时候,会报错。 sudo yum install mod_ssl二、查询s…...
Elasticsearch scroll 之滚动查询
Elasticsearch scroll 之滚动查询 Elasticsearch 的 Scroll API 是一种用于处理大规模数据集的机制,特别是在需要从索引中检索大量数据时。通常情况下,Elasticsearch 的搜索请求会有一个结果集大小的限制 (fromsize 的检索数量默认是 10,000 条记录)&am…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
aardio 自动识别验证码输入
技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”,于是尝试整合图像识别与网页自动化技术,完成了这套模拟登录流程。核心思路是:截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...
LUA+Reids实现库存秒杀预扣减 记录流水 以及自己的思考
目录 lua脚本 记录流水 记录流水的作用 流水什么时候删除 我们在做库存扣减的时候,显示基于Lua脚本和Redis实现的预扣减 这样可以在秒杀扣减的时候保证操作的原子性和高效性 lua脚本 // ... 已有代码 ...Overridepublic InventoryResponse decrease(Inventor…...
五、jmeter脚本参数化
目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...
P10909 [蓝桥杯 2024 国 B] 立定跳远
# P10909 [蓝桥杯 2024 国 B] 立定跳远 ## 题目描述 在运动会上,小明从数轴的原点开始向正方向立定跳远。项目设置了 $n$ 个检查点 $a_1, a_2, \cdots , a_n$ 且 $a_i \ge a_{i−1} > 0$。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时࿰…...
