【排序算法】六、快速排序补充:三指针+随机数法
「前言」文章内容是对快速排序算法的补充,之前的算法流程细节多难处理,这里补充三指针+随机数法(递归),这个容易理解,在时间复杂度上也更优秀。
快排:三指针+随机数法
原理跟之前的一致,这里就不再解释,前面版本的细节太多,换成这个三指针很好。
传统的快速排序使用两个指针(一个指向当前序列的开始,另一个指向结束),并在每次迭代中根据一个选定的“基准值”来重新排列数组。
然而,为了处理一些特殊情况,比如包含大量重复元素的数组,有时可以使用三指针技术来优化性能。同时,为了增加算法的随机性并减少最坏情况发生的概率(即当输入数组已排序或接近排序时),可以使用随机数法来选择基准值。
随机数法选择基准值
为了避免最坏情况的发生(即当输入数组已排序或接近排序时),可以选择一个随机的元素作为基准值,而不是总是选择第一个或最后一个元素。这可以通过生成一个随机数来实现,该随机数对应于数组中的一个有效索引。
三指针
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…...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...

网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...
在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7
在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤: 第一步: 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为: // 改为 v…...