常见排序算法总结 (四) - 快速排序与随机选择
快速排序
算法思想
每一轮在数组相应的范围上随机找一个元素进行划分,将不大于它的所有元素都放到左边,将大于它的元素都放到右边。在左右两个子数组上不断地递归,直到整个数组上有序。
注意:实现时选择的时参考荷兰国旗问题优化后的快排算法,它会在一次划分中维护一个包含所有等于划分标准元素的区间,保证小于该数的都在区间左侧,大于该数的都在区间右侧。这样的做法,在一定程度上能够减少划分次数。
稳定性分析
快速排序是不稳定的,它涉及到拆分区间,无法保证相等的数一定在同一个区间上被处理完成,也就无法保证它们的相对次序不发生变化。
具体实现
// 交换数组中的两个元素
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…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
JDK 17 序列化是怎么回事
如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...
如何通过git命令查看项目连接的仓库地址?
要通过 Git 命令查看项目连接的仓库地址,您可以使用以下几种方法: 1. 查看所有远程仓库地址 使用 git remote -v 命令,它会显示项目中配置的所有远程仓库及其对应的 URL: git remote -v输出示例: origin https://…...
qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001
qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类,直接把源文件拖进VS的项目里,然后VS卡住十秒,然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分,导致编译的时候找不到了。因…...
Copilot for Xcode (iOS的 AI辅助编程)
Copilot for Xcode 简介Copilot下载与安装 体验环境要求下载最新的安装包安装登录系统权限设置 AI辅助编程生成注释代码补全简单需求代码生成辅助编程行间代码生成注释联想 代码生成 总结 简介 尝试使用了Copilot,它能根据上下文补全代码,快速生成常用…...
在ubuntu等linux系统上申请https证书
使用 Certbot 自动申请 安装 Certbot Certbot 是 Let’s Encrypt 官方推荐的自动化工具,支持多种操作系统和服务器环境。 在 Ubuntu/Debian 上: sudo apt update sudo apt install certbot申请证书 纯手动方式(不自动配置)&…...
