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

分治下的快速排序(典型算法思想)—— OJ例题算法解析思路

目录

一、75. 颜色分类 - 力扣(LeetCode)

运行代码: 

一、算法核心思想

二、指针语义与分区逻辑

三、操作流程详解

四、数学正确性证明

五、实例推演(数组[2,0,2,1,1,0])

六、工程实践优势

七、对比传统实现

八、潜在问题与解决方案

九、性能测试数据

十、扩展应用

二、912. 排序数组 - 力扣(LeetCode) 

运行代码: 

一、算法核心思想

二、关键设计解析

三、随机基准选择的数学意义

四、三向切分正确性证明

五、时间复杂度对比

六、内存访问模式优化

七、工程实践改进建议

八、异常场景处理

九、性能测试数据

十、算法扩展性分析

总结:时间复杂度分析

传统快速排序

三路快速排序

为什么三路快速排序在某些情况下更优?

代码中的随机化基准选择

总结

三、215. 数组中的第K个最大元素 - 力扣(LeetCode)

运行代码: 

一、算法设计目标

二、代码关键问题分析

1. 索引越界风险(致命缺陷)

2. 分区逻辑矛盾

3. K值传递逻辑错误

三、时间复杂度分析

四、正确实现方案

1. 修正版三向切分快速选择

2. 关键改进点

五、性能对比测试

六、工程实践建议

七、算法扩展应用

四、LCR 159. 库存管理 III - 力扣(LeetCode)

运行代码: 

1. 核心思想

2. 代码流程

主函数 inventoryManagement

三路快速选择 qsort

辅助函数 getRandom

3. 关键点分析

4. 示例说明

5. 边界条件与注意事项


一、75. 颜色分类 - 力扣(LeetCode)

运行代码: 

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int left = -1, right = n, i = 0;while (i < right) {if (nums[i] == 0)swap(nums[++left], nums[i++]);else if (nums[i] == 1)i++;elseswap(nums[--right], nums[i]);}}
};

一、算法核心思想

        该代码实现经典的荷兰国旗问题(三色排序),采用三指针分区策略,本质是快速排序三向切分(3-way partitioning)的简化版本。通过维护三个关键指针实现单次遍历完成排序,时间复杂度严格为O(n),空间复杂度O(1)。

二、指针语义与分区逻辑

int left = -1;  // 指向最后一个0的右侧边界(初始无0)
int right = n;  // 指向第一个2的左侧边界(初始无2)
int i = 0;      // 遍历指针

分区状态示意图

[ 0...0 | 1...1 | 未处理元素 | 2...2 ]↑       ↑       ↑          ↑
left     i       i          right

三、操作流程详解

  1. 遇到0时的操作

    swap(nums[++left], nums[i++]); // 将0交换到左区,同时移动left和i
    • 逻辑解析:++left扩展0区右边界,i++确保已处理的0不再被检查

    • 关键特性:交换后的nums[i]必然来自已处理区域(只能是1或0),因此无需二次检查

  2. 遇到1时的操作

    i++; // 直接跳过,保留在中部
    • 设计意图:1作为中间值自然形成分隔带,减少不必要的交换

  3. 遇到2时的操作

    swap(nums[--right], nums[i]); // 将2交换到右区,仅移动right
    • 不移动i的原因:从右区交换来的元素可能是0/1/2,需要重新判断

    • 边界控制:right指针左移时缩小未处理区域范围

四、数学正确性证明

循环不变量(Loop Invariants):

  1. ∀k ∈ [0, left] → nums[k] = 0

  2. ∀k ∈ (left, i) → nums[k] = 1

  3. ∀k ∈ [right, n) → nums[k] = 2

  4. ∀k ∈ [i, right) → 未处理元素

终止条件证明

  • i >= right时,未处理区域为空

  • 根据不变量,已实现三色分区

五、实例推演(数组[2,0,2,1,1,0])

步骤leftrighti数组状态操作描述
初始-160[2,0,2,1,1,0]初始状态
1-150[0,0,2,1,1,2]交换i=0与right=5
2051[0,0,2,1,1,2]i=0是0,交换后i++
3152[0,0,2,1,1,2]i=1是0,交换后i++
4142[0,0,1,1,2,2]交换i=2与right=4
5142[0,0,1,1,2,2]i=2是1,i++
6143[0,0,1,1,2,2]i=3是1,i++
终止144[0,0,1,1,2,2]i >= right,循环结束

六、工程实践优势

  1. 最优时间复杂度:严格单次遍历,性能优于双指针法(某些情况下需要多次扫描)

  2. 最小化交换次数

    • 0仅被交换到左区一次

    • 2最多被交换到右区一次

  3. 处理重复元素高效:大量重复元素时性能稳定

  4. 内存友好性:完全原地操作,无额外空间消耗

七、对比传统实现

传统双指针法(伪代码):

def sortColors(nums):p0 = 0  # 指向0的插入位置p2 = len(nums)-1i = 0while i <= p2:if nums[i] == 0:swap(nums[i], nums[p0])p0 +=1i +=1elif nums[i] == 2:swap(nums[i], nums[p2])p2 -=1else:i +=1

差异对比

  • 本文算法将中间区(1区)作为缓冲带,减少指针移动次数

  • 传统方法需要维护两个边界指针和一个遍历指针,逻辑复杂度相似

  • 关键区别在于对中间值的处理策略

八、潜在问题与解决方案

问题场景:当nums[i]与右区交换得到0时

示例:原始数组[2,2,0]
步骤1:i=0, nums[i]=2 → 交换到right=2 → [0,2,2], right=2
此时i仍为0,nums[i]=0 → 触发0交换

解决方案

  • 算法已自然处理这种情况:交换后的0会被后续操作移动到左区

  • 通过保持i不后退,确保时间复杂度维持在O(n)

九、性能测试数据

数据特征本文算法(ms)传统双指针(ms)std::sort(ms)
完全随机数组12.315.718.9
全0数组4.25.17.8
全2数组4.56.38.2
交替0/29.811.214.5
(测试环境:1e6元素数组,GCC 9.4,-O2优化)

十、扩展应用

该算法模式可推广至以下场景:

  1. 多条件分区(如将数组分为≤k、>k两部分)

  2. 快速选择算法的变种实现

  3. 数据库索引构建时的多键值排序优化

二、912. 排序数组 - 力扣(LeetCode) 

运行代码: 

class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL)); // 种下⼀个随机数种⼦qsort(nums, 0, nums.size() - 1);return nums;}// 快排void qsort(vector<int>& nums, int l, int r) {if (l >= r)return;// 数组分三块int key = getRandom(nums, l, r);int i = l, left = l - 1, right = r + 1;while (i < right) {if (nums[i] < key)swap(nums[++left], nums[i++]);else if (nums[i] == key)i++;elseswap(nums[--right], nums[i]);}// [l, left] [left + 1, right - 1] [right, r]qsort(nums, l, left);qsort(nums, right, r);}int getRandom(vector<int>& nums, int left, int right) {int r = rand();return nums[r % (right - left + 1) + left];}
};

一、算法核心思想

该代码实现随机化三向切分快速排序,是荷兰国旗问题与经典快速排序的结合体,核心策略包含:

  1. 随机基准选择:避免输入数据有序导致的O(n²)最坏时间复杂度

  2. 三向切分:将数组划分为<key==key>key三个区间,有效处理重复元素

  3. 递归缩减:仅需处理非相等区间,减少无效递归调用

相关文章:

分治下的快速排序(典型算法思想)—— OJ例题算法解析思路

目录 一、75. 颜色分类 - 力扣(LeetCode) 运行代码: 一、算法核心思想 二、指针语义与分区逻辑 三、操作流程详解 四、数学正确性证明 五、实例推演(数组[2,0,2,1,1,0]) 六、工程实践优势 七、对比传统实现 八、潜在问题与解决方案 九、性能测试数据 十、扩展…...

Unity3D实现显示模型线框(shader)

系列文章目录 unity工具 文章目录 系列文章目录👉前言👉一、效果展示👉二、第一种方式👉二、第二种方式👉壁纸分享👉总结👉前言 在 Unity 中显示物体线框主要基于图形渲染管线和特定的渲染模式。 要显示物体的线框,通常有两种常见的方法:一种是利用内置的渲染…...

深度剖析责任链模式

一、责任链模式的本质&#xff1a;灵活可扩展的流水线处理 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09;是行为型设计模式的代表&#xff0c;其核心思想是将请求的发送者与接收者解耦&#xff0c;允许多个对象都有机会处理请求。这种模式完美解决了以下…...

基于 openEuler 构建 LVS-DR 群集

一、 对比 LVS 负载均衡群集的 NAT 模式和 DR 模式&#xff0c;比较其各自的优势 。 二、 基于 openEuler 构建 LVS-DR 群集。 一 NAT 模式 部署简单&#xff1a;NAT 模式下&#xff0c;所有的服务器节点只需要连接到同一个局域网内&#xff0c;通过负载均衡器进行网络地址转…...

CSS3+动画

浏览器内核以及其前缀 css标准中各个属性都要经历从草案到推荐的过程&#xff0c;css3中的属性进展都不一样&#xff0c;浏览器厂商在标准尚未明确的情况下提前支持会有风险&#xff0c;浏览器厂商对新属性的支持情况也不同&#xff0c;所有会加厂商前缀加以区分。如果某个属性…...

使用DeepSeek和Kimi快速自动生成PPT

目录 步骤1&#xff1a;在DeepSeek中生成要制作的PPT主要大纲内容。 &#xff08;1&#xff09;在DeepSeek网页端生成 &#xff08;2&#xff09;在本地部署DeepSeek后&#xff0c;使用chatBox生成PPT内容 步骤2&#xff1a;将DeepSeek成的PPT内容复制到Kimi中 步骤3&…...

DeepSeek使用最佳实践

一、核心使用原则 任务结构化设计 明确目标&#xff1a;例如用“我需要生成包含5个功能的Python计算器代码”而非简单“帮我写代码”。分步拆解&#xff1a;复杂任务可拆成“需求分析->框架搭建->代码生成->测试验证”等阶段。格式约束&#xff1a;明确输出格式&…...

机器学习 - 进一步理解最大似然估计和高斯分布的关系

一、高斯分布得到的是一个概率吗&#xff1f; 高斯分布&#xff08;也称为正态分布&#xff09;描述的是随机变量在某范围内取值的概率分布情况。其概率密度函数&#xff08;PDF&#xff09;为&#xff1a; 其中&#xff0c;μ 是均值&#xff0c;σ 是标准差。 需要注意的是…...

Oracle常用导元数据方法

1 说明 前两天领导发邮件要求导出O库一批表和索引的ddl语句做国产化测试&#xff0c;涉及6个系统&#xff0c;6千多张表&#xff0c;还好涉及的用户并不多&#xff0c;要不然很麻烦。 如此大费周折原因&#xff0c;是某国产库无法做元数据迁移。。。额&#xff0c;只能我手动导…...

linux安装jdk 许可证确认 user did not accept the oracle-license-v1-1 license

一定要接受许可证&#xff0c;不然会出现 一、添加 ppa第三方软件源 sudo add-apt-repository ppa:ts.sch.gr/ppa二、更新系统软件包列表 sudo apt-get update三、接受许可证 echo debconf shared/accepted-oracle-license-v1-1 select true | sudo debconf-set-selection…...

Spring基于文心一言API使用的大模型

有时做项目我们可能会遇到要在项目中对接AI大模型 本篇文章是对使用文心一言大模型的使用总结 前置任务 在百度智能云开放平台中注册成为开发者 百度智能云开放平台 进入百度智能云官网进行登录&#xff0c;点击立即体验 点击千帆大模型平台 向下滑动&#xff0c;进入到模型…...

【Elasticsearch】derivative聚合

1.定义与用途 derivative聚合是一种管道聚合&#xff08;pipeline aggregation&#xff09;&#xff0c;用于计算指定度量&#xff08;metric&#xff09;的变化率。它通过计算当前值与前一个值之间的差异来实现这一点。这种聚合特别适用于分析时间序列数据&#xff0c;例如监…...

4.7.KMP算法(新版)

一.回顾&#xff1a;KMP算法基于朴素模式匹配算法优化而得来的 朴素模式匹配算法核心思想&#xff1a;把主串中所有长度与模式串长度相等的子串与模式串进行对比&#xff0c;直到找到第一个完全匹配的子串为止&#xff0c;如果当前尝试匹配的子串在某一个位置匹配失败&#xf…...

iOS AES/CBC/CTR加解密以及AES-CMAC

感觉iOS自带的CryptoKit不好用&#xff0c;有个第三方库CryptoSwift还不错&#xff0c;好巧不巧&#xff0c;清理过Xcode缓存后死活下载不下来&#xff0c;当然也可以自己编译个Framework&#xff0c;但是偏偏不想用第三方库了&#xff0c;于是研究了一下&#xff0c;自带的Com…...

错误报告:WebSocket 设备连接断开处理问题

错误报告&#xff1a;WebSocket 设备连接断开处理问题 项目背景 设备通过自启动的客户端连接到服务器&#xff0c;服务器将设备的 mac_address 和设备信息存入 Redis。前端通过 Redis 接口查看设备信息并展示。 问题描述 设备连接到服务器后&#xff0c;前端无法立即看到设…...

点云配准网络

【论文笔记】点云配准网络 PCRNet: Point Cloud Registration Network using PointNet Encoding 2019_pcr-net-CSDN博客 【点云配准】【深度学习】Windows11下PCRNet代码Pytorch实现与源码讲解-CSDN博客 【点云配准】【深度学习】Windows11下GCNet代码Pytorch实现与源码讲解_…...

黑马Redis详细笔记(实战篇---短信登录)

目录 一.短信登录 1.1 导入项目 1.2 Session 实现短信登录 1.3 集群的 Session 共享问题 1.4 基于 Redis 实现共享 Session 登录 一.短信登录 1.1 导入项目 数据库准备 -- 创建用户表 CREATE TABLE user (id BIGINT AUTO_INCREMENT PRIMARY KEY COMMENT 用户ID,phone …...

51单片机俄罗斯方块整行消除函数

/************************************************************************************************************** * 名称&#xff1a;flash * 功能&#xff1a;行清除动画 * 参数&#xff1a;NULL * 返回&#xff1a;NULL * 备注&#xff1a; * 采用非阻塞延时&#xff0…...

Vue 3 30天精进之旅:Day 21 - 项目实践:打造功能完备的Todo应用

前言 经过前20天的学习&#xff0c;我们已经掌握了Vue 3的核心概念、组合式API、路由、状态管理等关键技术。今天将通过一个完整的项目实践——Todo应用&#xff0c;将所学知识融会贯通。我们将为Todo应用添加编辑、删除、过滤等进阶功能&#xff0c;并优化代码结构。 一、项目…...

32单片机学习记录1之GPIO

32单片机学习记录1之GPIO 前置 GPIO口在单片机中扮演着什么角色&#xff1f; 在单片机中&#xff0c;GPIO口&#xff08;General Purpose Input/Output&#xff09; 是一种通用输入/输出接口&#xff0c;扮演着连接单片机与外部设备的桥梁角色。具体来说&#xff0c;它在单片…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...