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

【排序算法】六、快速排序补充:三指针+随机数法

「前言」文章内容是对快速排序算法的补充,之前的算法流程细节多难处理,这里补充三指针+随机数法(递归),这个容易理解,在时间复杂度上也更优秀。

快排:三指针+随机数法

原理跟之前的一致,这里就不再解释,前面版本的细节太多,换成这个三指针很好。

传统的快速排序使用两个指针(一个指向当前序列的开始,另一个指向结束),并在每次迭代中根据一个选定的“基准值”来重新排列数组。

然而,为了处理一些特殊情况,比如包含大量重复元素的数组,有时可以使用三指针技术来优化性能。同时,为了增加算法的随机性并减少最坏情况发生的概率(即当输入数组已排序或接近排序时),可以使用随机数法来选择基准值。

随机数法选择基准值

为了避免最坏情况的发生(即当输入数组已排序或接近排序时),可以选择一个随机的元素作为基准值,而不是总是选择第一个或最后一个元素。这可以通过生成一个随机数来实现,该随机数对应于数组中的一个有效索引。

三指针

  1. left指针:指向当前已经处理好的小于基准值的元素的末尾。
  2. right指针:指向当前尚未处理的元素的开始,且这些元素都大于基准值。
  3. i(current)指针:当前指针,用于遍历数组,找到小于或大于基准值的元素。

开始时,lefti 指向数组的起始位置,right 指向数组的末尾。遍历数组时,i 会向右移动,同时更新 leftright 的位置。

数组会分成三块:[l, left-1] [left, right] [right+1, r]

1.1 递归实现

算法大致分三步:

  1. 取基准值,采用随机数法
  2. 数组分三块
  3. 递归排序

代码如下:(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 非递归实现

快速排序的非递归算法基本思路:

  1. 使用栈代替递归
    1. 在递归版本中,函数调用栈会自动管理待排序的区间。使用 std::stack 来保存区间的起始和结束索引。
  2. 初始化栈
    1. 初始时,将整个数组的起始索引 left 和结束索引 right 压入栈中。
  3. 处理栈中的区间
    1. 进入一个循环,直到栈为空。每次从栈中弹出一个区间(leftright)。
    2. 检查当前区间是否有效(即 left < right),如果无效则跳过。
  4. 选择基准值:使用 GetRandom 函数从当前区间随机选择一个基准值 key
  5. 三指针分区
    1. 初始化三个指针:
      1. l 指向当前区间的左端。
      2. i 用于遍历当前区间。
      3. r 指向当前区间的右端。
    2. 遍历数组,根据元素与基准值的比较进行分区:
      1. 如果 nums[i] < key,将元素交换到左侧,并移动指针。
      2. 如果 nums[i] == key,只移动 i 指针。
      3. 如果 nums[i] > key,将元素交换到右侧,并移动 r 指针。
  6. 压入新的区间
    1. 在完成分区后,可能会产生两个新的子区间:
      1. 左侧区间 [left, l - 1]
      2. 右侧区间 [r + 1, right]
    2. 将这两个区间的起始和结束索引压入栈中,以便后续处理。
  7. 重复过程
    1. 重复上述过程,直到栈为空,所有的区间都被处理完毕,数组就会被排序完成。

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
「 声明 」 余之才疏学浅,故所撰文疏漏难免,或有谬误或不准确之处,敬请读者批评指正。

相关文章:

【排序算法】六、快速排序补充:三指针+随机数法

「前言」文章内容是对快速排序算法的补充&#xff0c;之前的算法流程细节多难处理&#xff0c;这里补充三指针随机数法&#xff08;递归&#xff09;&#xff0c;这个容易理解&#xff0c;在时间复杂度上也更优秀。 快排&#xff1a;三指针随机数法 原理跟之前的一致&#xff…...

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.服务类&#xff0c;纯虚类&#xff0c;提供接口 1.3.实现插件类&#xff0c;实现纯虚函数 1.4.激活插件&#xff0c;加入ctk框架的生命周期中 1.5.添加资源文件 1.6..pro文件 2.使用此插件 3.总结 1.生成插件 1.1.环境说明 编译ct…...

深入理解C代码中的条件编译

引言 条件编译是 C 编程中的一个重要特性&#xff0c;它允许开发人员根据不同的条件选择性地编译源代码的不同部分。这一特性对于编写跨平台的程序、优化代码性能或控制编译时资源消耗等方面非常重要。本文将深入探讨条件编译的工作原理、使用场景、高级应用以及注意事项&…...

Ubuntu16.04操作系统-内核优化

1. 概述 本文所用优化是生产环境中经过长期验证的内核优化策略&#xff0c;针对的服务器与POD主要用于高CPU、高内存、高IO的业务场景。 备注: OS: ubuntu16.04, 内核&#xff1a; 4.15.0-147-generic 主要涵盖以下内容优化&#xff1a; ulimit优化加强tcp参数其他内存参数 …...

Qt/C++编写的Onvif调试助手调试神器工具/支持云台控制/预置位设置等/有手机版本

一、功能特点 广播搜索设备&#xff0c;支持IPC和NVR&#xff0c;依次返回。可选择不同的网卡IP进行对应网段设备的搜索。依次获取Onvif地址、Media地址、Profile文件、Rtsp地址。可对指定的Profile获取视频流Rtsp地址&#xff0c;比如主码流地址、子码流地址。可对每个设备设…...

【原创】java+swing+mysql密码管理器系统设计与实现

个人主页&#xff1a;程序员杨工 个人简介&#xff1a;从事软件开发多年&#xff0c;前后端均有涉猎&#xff0c;具有丰富的开发经验 博客内容&#xff1a;全栈开发&#xff0c;分享Java、Python、Php、小程序、前后端、数据库经验和实战 文末有本人名片&#xff0c;希望和大家…...

JavaEE-HTTPHTTPS

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

iLogtail 开源两周年:社区使用调查报告

作者&#xff1a;玄飏 iLogtail 作为阿里云开源的可观测数据采集器&#xff0c;以其高效、灵活和可扩展的特性&#xff0c;在可观测采集、处理与分析领域受到了广泛的关注与应用。在 iLogtail 两周年之际&#xff0c;我们对 iLogtail 开源社区进行了一次使用调研&#xff0c;旨…...

Ubuntu 比较两个文件夹

比较两个文件夹下的大量文件是否一致&#xff0c;可以通过以下几种方式完成&#xff1a; 1. 使用 diff 命令 diff 命令不仅可以比较文件&#xff0c;还能递归比较文件夹。可以使用 -r 选项来递归比较两个目录下的文件&#xff1a; diff -r /path/to/dir1 /path/to/dir2 如…...

两数之和--力扣1

两数之和 题目思路C代码 题目 思路 根据题目要求&#xff0c;元素不能重复且不需要排序&#xff0c;我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中&#xff0c;使用目标值减去当前循环的nums[i]&#xff0c;得到差值&#xff0c;如果我们…...

vue原理分析(三)new()创建Vue实例

今天我们来分析Vue实例的创建 代码如下&#xff1a; Vue.config.productionTip falsenew Vue({render: h > h(App),}).$mount(#app) Vue.config.productionTip false 这个配置成false&#xff0c;是阻止启动生产消息 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&#xff0c;找到 s 中最长的 回文子串。 对于该题使用中心扩展法在某些情况下可以比动态规划方法更优&#xff0c;尤其是在处理较长字符串时。这是因为中心扩展法具有更好的空间复杂度&#xff0c;并且在实际应用中可能具有更快的运行速度&#xf…...

海康威视 嵌入式 面经 海康威视嵌入式软件 嵌入式硬件总结面试经验 面试题目汇总

标题海康威视 嵌入式 面经 海康威视嵌入式软件 嵌入式硬件总结面试经验 面试题目汇总 整理总结了海康威视嵌入式的面试题目&#xff01;&#xff0c;可以供大家面试参考 标题海康威视 嵌入式 面经 五月底投递&#xff0c;六月初面试&#xff0c;一场技术面&#xff0c;一场H…...

使用图论技巧——有遍数限制的最短路

给定一个 n个点 m 条边的有向图&#xff0c;图中可能存在重边和自环&#xff0c; 边权可能为负数。 请你求出从 11 号点到 n 号点的最多经过 k 条边的最短距离&#xff0c;如果无法从 1 号点走到 n 号点&#xff0c;输出 impossible。 注意&#xff1a;图中可能 存在负权回路…...

flume 使用 exec 采集容器日志,转储磁盘

flume 使用 exec 采集容器日志&#xff0c;转储磁盘 在该场景下&#xff0c;docker 服务为superset&#xff0c;flume 的sources 选择 exec &#xff0c; sinks选择 file roll 。 任务配置 具体配置文件如下&#xff1a; #simple.conf: A single-node Flume configuration#…...

459重复的子字符串

给定一个非空的字符串 s &#xff0c;检查是否可以通过由它的一个子串重复多次构成。 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】实现截图功能 【需求】 实现&#xff1a;实现点击截图按钮&#xff0c;实现对页面/组件的截图 【步骤】 编写页面UI Entry Component struct Screenshot {BuildergetSnapContent() {Column() {Image().width(100%).objectFit(ImageFit.Auto).borderRadi…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

相关类相关的可视化图像总结

目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系&#xff0c;可直观判断线性相关、非线性相关或无相关关系&#xff0c;点的分布密…...

接口 RESTful 中的超媒体:REST 架构的灵魂驱动

在 RESTful 架构中&#xff0c;** 超媒体&#xff08;Hypermedia&#xff09;** 是一个核心概念&#xff0c;它体现了 REST 的 “表述性状态转移&#xff08;Representational State Transfer&#xff09;” 的本质&#xff0c;也是区分 “真 RESTful API” 与 “伪 RESTful AP…...