【排序算法】六、快速排序补充:三指针+随机数法
「前言」文章内容是对快速排序算法的补充,之前的算法流程细节多难处理,这里补充三指针+随机数法(递归),这个容易理解,在时间复杂度上也更优秀。
快排:三指针+随机数法
原理跟之前的一致,这里就不再解释,前面版本的细节太多,换成这个三指针很好。
传统的快速排序使用两个指针(一个指向当前序列的开始,另一个指向结束),并在每次迭代中根据一个选定的“基准值”来重新排列数组。
然而,为了处理一些特殊情况,比如包含大量重复元素的数组,有时可以使用三指针技术来优化性能。同时,为了增加算法的随机性并减少最坏情况发生的概率(即当输入数组已排序或接近排序时),可以使用随机数法来选择基准值。
随机数法选择基准值
为了避免最坏情况的发生(即当输入数组已排序或接近排序时),可以选择一个随机的元素作为基准值,而不是总是选择第一个或最后一个元素。这可以通过生成一个随机数来实现,该随机数对应于数组中的一个有效索引。
三指针
left
指针:指向当前已经处理好的小于基准值的元素的末尾。right
指针:指向当前尚未处理的元素的开始,且这些元素都大于基准值。i
(current)指针:当前指针,用于遍历数组,找到小于或大于基准值的元素。
开始时,left
和 i
指向数组的起始位置,right
指向数组的末尾。遍历数组时,i
会向右移动,同时更新 left
和 right
的位置。
数组会分成三块:[l, left-1] [left, right] [right+1, r]
。
1.1 递归实现
算法大致分三步:
- 取基准值,采用随机数法
- 数组分三块
- 递归排序
代码如下:(C++)
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;// 创建随机数
int GetRandom(vector<int>& nums, int left, int right)
{int rNum = rand();return nums[left + rNum % (right - left + 1)];
}
// quick sort: 三指针+随机数法
void QuickSort(vector<int>& nums, int l, int r)
{if (l >= r) return;// 数组分三块int key = GetRandom(nums, l, r);int left = l, i = l, right = r;while (i <= right){if (nums[i] < key){swap(nums[left], nums[i]);++left;++i;}else if (nums[i] == key){++i;}else // nums[i] > key{std::swap(nums[i], nums[right]);--right;}}// 递归去排序// [l, left-1] [left, right] [right+1, r]QuickSort(nums, l, left - 1);QuickSort(nums, right + 1, r);
}int main()
{srand(time(nullptr));vector<int> arr = { 4, 6, 1, 0, 9, 5, 7, 7, 6, 6, 2, 3, 8 };QuickSort(arr, 0, arr.size() - 1);for (auto& x : arr) cout << x << " ";cout << endl;return 0;
}
1.2 非递归实现
快速排序的非递归算法基本思路:
- 使用栈代替递归
- 在递归版本中,函数调用栈会自动管理待排序的区间。使用
std::stack
来保存区间的起始和结束索引。
- 在递归版本中,函数调用栈会自动管理待排序的区间。使用
- 初始化栈
- 初始时,将整个数组的起始索引
left
和结束索引right
压入栈中。
- 初始时,将整个数组的起始索引
- 处理栈中的区间
- 进入一个循环,直到栈为空。每次从栈中弹出一个区间(
left
和right
)。 - 检查当前区间是否有效(即
left < right
),如果无效则跳过。
- 进入一个循环,直到栈为空。每次从栈中弹出一个区间(
- 选择基准值:使用
GetRandom
函数从当前区间随机选择一个基准值key
。 - 三指针分区
- 初始化三个指针:
l
指向当前区间的左端。i
用于遍历当前区间。r
指向当前区间的右端。
- 遍历数组,根据元素与基准值的比较进行分区:
- 如果
nums[i] < key
,将元素交换到左侧,并移动指针。 - 如果
nums[i] == key
,只移动i
指针。 - 如果
nums[i] > key
,将元素交换到右侧,并移动r
指针。
- 如果
- 初始化三个指针:
- 压入新的区间
- 在完成分区后,可能会产生两个新的子区间:
- 左侧区间
[left, l - 1]
- 右侧区间
[r + 1, right]
- 左侧区间
- 将这两个区间的起始和结束索引压入栈中,以便后续处理。
- 在完成分区后,可能会产生两个新的子区间:
- 重复过程
- 重复上述过程,直到栈为空,所有的区间都被处理完毕,数组就会被排序完成。
C++代码如下:(升序)
int GetRandom(vector<int>& arr, int left, int right)
{int rNum = rand();return arr[left + rNum % (right - left + 1)];
}void QuickSortNonRecursive(std::vector<int>& nums, int left, int right)
{std::stack<int> stack;stack.push(left);stack.push(right);while (!stack.empty()) // 栈为空结束{right = stack.top(); stack.pop();left = stack.top(); stack.pop();// 判断左右区间是否合理,若不合理则跳过本次循环if (left >= right) continue;// 三指针+随机数法int key = GetRandom(nums, left, right);int l = left, i = left, r = right;while (i <= r) {if (nums[i] < key){std::swap(nums[l], nums[i]);++l;++i;}else if (nums[i] == key){++i;}else // nums[i] > key{std::swap(nums[i], nums[r]);--r;}}// 将需要排序的部分压入栈中if (left < l - 1){stack.push(left);stack.push(l - 1);}if (r + 1 < right){stack.push(r + 1);stack.push(right);}}
}
--------------- END ---------------
「 作者 」 枫叶先生
「 更新 」 2024.4.9
「 声明 」 余之才疏学浅,故所撰文疏漏难免,或有谬误或不准确之处,敬请读者批评指正。
相关文章:
【排序算法】六、快速排序补充:三指针+随机数法
「前言」文章内容是对快速排序算法的补充,之前的算法流程细节多难处理,这里补充三指针随机数法(递归),这个容易理解,在时间复杂度上也更优秀。 快排:三指针随机数法 原理跟之前的一致ÿ…...
PyTorch torch.cdist函数介绍及示例代码
1. torch.cdist 函数介绍 torch.cdist 是 PyTorch 中用于计算两组向量之间成对距离的函数。它可以计算两个张量(矩阵)中的每对向量之间的距离,支持多种距离度量方式,如欧氏距离(默认)或 p 范数距离。 函数原型 torch.cdist(x1, x2, p=2.0, compute_mode=use_mm_for_eu…...

CTK框架(四): 插件编写
目录 1.生成插件 1.1.环境说明 1.2.服务类,纯虚类,提供接口 1.3.实现插件类,实现纯虚函数 1.4.激活插件,加入ctk框架的生命周期中 1.5.添加资源文件 1.6..pro文件 2.使用此插件 3.总结 1.生成插件 1.1.环境说明 编译ct…...

深入理解C代码中的条件编译
引言 条件编译是 C 编程中的一个重要特性,它允许开发人员根据不同的条件选择性地编译源代码的不同部分。这一特性对于编写跨平台的程序、优化代码性能或控制编译时资源消耗等方面非常重要。本文将深入探讨条件编译的工作原理、使用场景、高级应用以及注意事项&…...
Ubuntu16.04操作系统-内核优化
1. 概述 本文所用优化是生产环境中经过长期验证的内核优化策略,针对的服务器与POD主要用于高CPU、高内存、高IO的业务场景。 备注: OS: ubuntu16.04, 内核: 4.15.0-147-generic 主要涵盖以下内容优化: ulimit优化加强tcp参数其他内存参数 …...

Qt/C++编写的Onvif调试助手调试神器工具/支持云台控制/预置位设置等/有手机版本
一、功能特点 广播搜索设备,支持IPC和NVR,依次返回。可选择不同的网卡IP进行对应网段设备的搜索。依次获取Onvif地址、Media地址、Profile文件、Rtsp地址。可对指定的Profile获取视频流Rtsp地址,比如主码流地址、子码流地址。可对每个设备设…...

【原创】java+swing+mysql密码管理器系统设计与实现
个人主页:程序员杨工 个人简介:从事软件开发多年,前后端均有涉猎,具有丰富的开发经验 博客内容:全栈开发,分享Java、Python、Php、小程序、前后端、数据库经验和实战 文末有本人名片,希望和大家…...

JavaEE-HTTPHTTPS
目录 HTTP协议 一、概念 二、http协议格式 http请求报文 http响应报文 URL格式 三、认识方法 四、认识报头 HTTP响应中的信息 HTTPS协议 对称加密 非对称加密 中间人攻击 解决中间人攻击 HTTP协议 一、概念 HTTP (全称为 "超⽂本传输协议") 是⼀种应⽤…...

iLogtail 开源两周年:社区使用调查报告
作者:玄飏 iLogtail 作为阿里云开源的可观测数据采集器,以其高效、灵活和可扩展的特性,在可观测采集、处理与分析领域受到了广泛的关注与应用。在 iLogtail 两周年之际,我们对 iLogtail 开源社区进行了一次使用调研,旨…...
Ubuntu 比较两个文件夹
比较两个文件夹下的大量文件是否一致,可以通过以下几种方式完成: 1. 使用 diff 命令 diff 命令不仅可以比较文件,还能递归比较文件夹。可以使用 -r 选项来递归比较两个目录下的文件: diff -r /path/to/dir1 /path/to/dir2 如…...

两数之和--力扣1
两数之和 题目思路C代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们…...
vue原理分析(三)new()创建Vue实例
今天我们来分析Vue实例的创建 代码如下: Vue.config.productionTip falsenew Vue({render: h > h(App),}).$mount(#app) Vue.config.productionTip false 这个配置成false,是阻止启动生产消息 new Vue({render: h > h(App),}).$mount(#app)…...
Spring MVC: 构建Web应用的强大框架
Spring MVC: 构建现代Web应用的强大框架 1. MVC设计模式简介 MVC (Model-View-Controller) 是一种广泛使用的软件设计模式,它将应用程序的逻辑分为三个相互关联的组件: Model (模型): 负责管理数据、业务逻辑和规则。View (视图): 负责用户界面的展示,将数据呈现给用户。Con…...

网络学习-eNSP配置NAT
NAT实现内网和外网互通 #给路由器接口设置IP地址模拟实验环境 <Huawei>system-view Enter system view, return user view with CtrlZ. [Huawei]undo info-center enable Info: Information center is disabled. [Huawei]interface gigabitethernet 0/0/0 [Huawei-Gigabi…...
动态规划-最长回文子串
题目描述 给你一个字符串 s,找到 s 中最长的 回文子串。 对于该题使用中心扩展法在某些情况下可以比动态规划方法更优,尤其是在处理较长字符串时。这是因为中心扩展法具有更好的空间复杂度,并且在实际应用中可能具有更快的运行速度…...
海康威视 嵌入式 面经 海康威视嵌入式软件 嵌入式硬件总结面试经验 面试题目汇总
标题海康威视 嵌入式 面经 海康威视嵌入式软件 嵌入式硬件总结面试经验 面试题目汇总 整理总结了海康威视嵌入式的面试题目!,可以供大家面试参考 标题海康威视 嵌入式 面经 五月底投递,六月初面试,一场技术面,一场H…...
使用图论技巧——有遍数限制的最短路
给定一个 n个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。 请你求出从 11 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。 注意:图中可能 存在负权回路…...

flume 使用 exec 采集容器日志,转储磁盘
flume 使用 exec 采集容器日志,转储磁盘 在该场景下,docker 服务为superset,flume 的sources 选择 exec , sinks选择 file roll 。 任务配置 具体配置文件如下: #simple.conf: A single-node Flume configuration#…...
459重复的子字符串
给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。 public repeatedSubstringPattern(String s){int n s.length();for(int i 1; i < n / 2; i){if(n % i ! 0) continue;// substring获取子字符串是左闭右开的String ss s.substring(0,…...

【HarmonyOS NEXT】实现截图功能
【HarmonyOS NEXT】实现截图功能 【需求】 实现:实现点击截图按钮,实现对页面/组件的截图 【步骤】 编写页面UI Entry Component struct Screenshot {BuildergetSnapContent() {Column() {Image().width(100%).objectFit(ImageFit.Auto).borderRadi…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

归并排序:分治思想的高效排序
目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法,由约翰冯诺伊曼在1945年提出。其核心思想包括: 分割(Divide):将待排序数组递归地分成两个子…...

GraphRAG优化新思路-开源的ROGRAG框架
目前的如微软开源的GraphRAG的工作流程都较为复杂,难以孤立地评估各个组件的贡献,传统的检索方法在处理复杂推理任务时可能不够有效,特别是在需要理解实体间关系或多跳知识的情况下。先说结论,看完后感觉这个框架性能上不会比Grap…...