常见排序算法总结 (四) - 快速排序与随机选择
快速排序
算法思想
每一轮在数组相应的范围上随机找一个元素进行划分,将不大于它的所有元素都放到左边,将大于它的元素都放到右边。在左右两个子数组上不断地递归,直到整个数组上有序。
注意:实现时选择的时参考荷兰国旗问题优化后的快排算法,它会在一次划分中维护一个包含所有等于划分标准元素的区间,保证小于该数的都在区间左侧,大于该数的都在区间右侧。这样的做法,在一定程度上能够减少划分次数。
稳定性分析
快速排序是不稳定的,它涉及到拆分区间,无法保证相等的数一定在同一个区间上被处理完成,也就无法保证它们的相对次序不发生变化。
具体实现
// 交换数组中的两个元素
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…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)
在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...
