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

常见排序算法总结 (四) - 快速排序与随机选择

快速排序

算法思想

每一轮在数组相应的范围上随机找一个元素进行划分,将不大于它的所有元素都放到左边,将大于它的元素都放到右边。在左右两个子数组上不断地递归,直到整个数组上有序。
注意:实现时选择的时参考荷兰国旗问题优化后的快排算法,它会在一次划分中维护一个包含所有等于划分标准元素的区间,保证小于该数的都在区间左侧,大于该数的都在区间右侧。这样的做法,在一定程度上能够减少划分次数。

稳定性分析

快速排序是不稳定的,它涉及到拆分区间,无法保证相等的数一定在同一个区间上被处理完成,也就无法保证它们的相对次序不发生变化。

具体实现

// 交换数组中的两个元素
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 平台上专门设置了卡快排的用例。

相关文章:

常见排序算法总结 (四) - 快速排序与随机选择

快速排序 算法思想 每一轮在数组相应的范围上随机找一个元素进行划分&#xff0c;将不大于它的所有元素都放到左边&#xff0c;将大于它的元素都放到右边。在左右两个子数组上不断地递归&#xff0c;直到整个数组上有序。 注意&#xff1a;实现时选择的时参考荷兰国旗问题优化…...

Doris的基础架构

Doris的基础架构 Frontend&#xff08;FE&#xff09;&#xff1a;主要负责用户请求的接入、查询解析规划、元数据的管理、节点管理相关工作。Backend&#xff08;BE&#xff09;&#xff1a;主要负责数据存储、查询计划的执行。 我的Github地址&#xff0c;欢迎大家加入我的开…...

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…...

标书里的“废标雷区”:你踩过几个?

在投标领域&#xff0c;标书的质量不仅决定了中标的可能性&#xff0c;更是体现企业专业度的关键。但即便是经验丰富的投标人&#xff0c;也难免会在标书编制过程中踩中“废标雷区”。这些雷区可能隐藏在技术方案的细节中&#xff0c;也可能是投标文件格式的规范问题。以下&…...

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】系统介绍 研究背景 随着互联网的普及和电子商务的发展&#xff0c;用户可以在线获取大量的图书资源。然而&#xff0c;面对海量的信息&#xff0c;用户往往难以找到自己真正感兴趣的书籍。同时&#xff0c;对于在线书店或图书馆等提供图书服务的平台来说&#xff0c;如何…...

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

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…...

Linux系统下安装配置 Nginx 超详细图文教程

一、下载Nginx安装包 nginx官网&#xff1a;nginx: downloadhttp://nginx.org/en/download.html找到我们所需要版本&#xff0c;把鼠标移动到上面&#xff0c;右键打开链接进行下载 或者如果Linux联网&#xff0c;直接在Linux服务上使用wget命令把Nginx安装包下载到/usr/local/…...

语言处理程序基础

逻辑运算 正规式 有限自动机 上下文无关文法 表达式&#xff08;前缀、后缀、中缀&#xff09; 将表达式&#xff08;a-b&#xff09;*&#xff08;c5&#xff09;构造成树的步骤为&#xff1a;括号不能出现在树中&#xff1b;按照表达式的计算顺序来依次构造&#xff01;&…...

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制作的数独小游戏 &#xff08;完整源码和介绍&#xff09; 感兴趣可以随时联系博主噢~常在线能秒回&#xff01; “Matlab数独小游戏”程序设计的关键技术流程和核心算法如下&#xff1a; 1.图形用户界面(GUI):使用MATLAB的GUIDE工具创建和管理用户界面&#xff0…...

使用docker让项目持续开发和部署

大多人选择开发时在本地&#xff0c;部署时文件都在容器里&#xff0c;如果没有容器&#xff0c;那就本地开发&#xff0c;没有映射文件&#xff0c;如果部署环境到容器了&#xff0c;容器内部启动时设置执行命令&#xff0c;再将映射的文件进行编译&#xff0c;这就直接能实现…...

电子应用设计方案-45:智能火锅系统方案设计

智能火锅系统方案设计 一、引言 随着人们生活水平的提高和对饮食体验的追求&#xff0c;智能火锅系统应运而生。本方案旨在设计一款集智能化控制、高效加热、安全保障和个性化体验于一体的智能火锅系统。 二、系统概述 1. 系统目标 - 实现精准的温度控制&#xff0c;满足不同…...

windows在conda下安装nlpia库

最近在学习《自然语言处理实战》这本书&#xff0c;书中用了其自己的库nlpia&#xff0c;我一直装不上&#xff0c;网上也找不到教程遂放弃&#xff0c;看到现在第四章没办法了&#xff0c;需要用到库里的一些文本语料&#xff0c;又折腾了一天&#xff0c;终于装好了&#xff…...

分布式事务的前世今生-纯理论

一个可用的复杂的系统总是从可用的简单系统进化而来。反过来这句话也正确: 从零开始设计的复杂的系统从来都用不了&#xff0c;也没办法让它变的可用。 --John Gal 《系统学》 1975 1. 事务的概念 百科&#xff1a; 事务&#xff08;Transaction&#xff09;&#xff0c;一般是…...

apache部署若依前后端分离项目(开启SSL)

网站部署之后,大多数需要配置https,所以本章教程,介绍使用apache部署若依前后端项目的时候,如何开启SSL,以及如何配置SSL证书。 一、安装ssl模块 默认情况下,ssl模块是没有安装的。需要手动安装,否则直接配置SSL模块的时候,会报错。 sudo yum install mod_ssl二、查询s…...

Elasticsearch scroll 之滚动查询

Elasticsearch scroll 之滚动查询 Elasticsearch 的 Scroll API 是一种用于处理大规模数据集的机制&#xff0c;特别是在需要从索引中检索大量数据时。通常情况下&#xff0c;Elasticsearch 的搜索请求会有一个结果集大小的限制 (fromsize 的检索数量默认是 10,000 条记录)&am…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...