讲师中心 微信公众号

工具推荐

视频效率加速
Seko
Seko

AI短剧一键生成成片

SoundView
SoundView

字幕擦除翻译、配音口型同步

AniShort
AniShort

AI短剧协同制作平台

Laper
Laper

剧本策划到成片协作

Golang快速排序的分区思路详解

星晨同学_2936

星晨同学_2936

发布时间:2026-11-22 08:13:48

|

705人浏览过

|

来源于php中文网

原创

分区操作必须单独封装,因其需严格保证:所有小于pivot的元素在左、大于的在右,且pivot最终落于排序后正确下标;混入递归函数易致越界、漏排或死循环,故须由partition返回pivot索引以安全划分区间。

golang快速排序的分区思路详解

分区操作为什么必须用 partition 单独封装

因为分区不是“找一个中间值然后 swap 两次”这么简单——它要保证:所有 arr[i] 的元素严格落在左半段,所有 <code>arr[j] > pivot 的元素严格落在右半段,且 pivot 最终停在它排序后该在的下标位置。如果把这个逻辑混在递归函数里,边界错一位、i 或 j 多走一步,整个数组就可能漏排、越界或死循环。

常见错误现象:panic: runtime error: index out of range,或排序后部分数据逆序、重复元素位置错乱。

  • partition 必须返回 pivot 的最终索引,供上层递归调用划分左右区间
  • 不能直接对 arr[:pivot] 和 arr[pivot+1:] 递归(这是切片版的简化写法,但隐藏了索引偏移风险)
  • 若用 Lomuto 方案(以 arr[high] 为 pivot),i 要从 low - 1 开始,否则第一个小于 pivot 的元素会被跳过

partition 里 i 和 j 的移动顺序为什么不能反

以 Hoare 分区方案为例(常用在双指针向中间收缩的实现中):先让 j 从右往左找第一个 的数,再让 <code>i 从左往右找第一个 >= pivot 的数,然后交换。顺序反了会导致 i 和 j 在未相遇前就交叉,或者某侧元素没被充分扫描。

典型表现:小数组如 []int{3, 1, 2} 排序后变成 [2, 1, 3],中间值没归位。

立即学习“go语言免费学习笔记(深入)”;

Golang Uber Dig
Golang Uber Dig

使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器,提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象,支持命名依赖等

下载
  • 必须是 “j 先动 → 判断 → i 再动 → 判断 → 交换”,形成闭环控制
  • 每次 i++ 或 j-- 后都要立刻检查是否越界(i ),否则交换时下标非法
  • 当 i == j 时,这一轮分区结束,arr[i] 就是 pivot 归位后的位置

选 pivot 用 arr[low]、arr[high] 还是 arr[(low+high)/2]

三种选法都合法,但行为差异明显:arr[low] 和 arr[high] 在已排序或近乎有序数组上极易触发最坏时间复杂度 O(n²);而中位数近似值(如 arr[(low+high)/2])能显著降低退化概率。

不过 Go 标准库 sort 实际采用的是三数取中(median-of-three)+ 随机回退策略,普通手写不必过度优化,但至少别固定用首/尾。

  • 用 arr[high] 最简洁,适合教学和小数据量验证
  • 用 arr[(low+high)/2] 对随机数据更鲁棒,且避免整数溢出(low+high 可能超 int)可改用 low + (high-low)/2
  • 生产代码建议加一层随机:用 rand.Intn(high - low + 1) + low 选下标,再 swap 到末尾,再进 partition

原地排序时切片截取 arr[low:high+1] 的陷阱

Go 切片传递的是底层数组引用,看似方便,但递归中若直接传 arr[low:pivot] 和 arr[pivot+1:high+1],会丢失原始切片的容量信息,且 pivot 是相对当前子数组的偏移,不是全局下标——这会让调试时打印的 len(arr) 和你脑内预期不一致,尤其在嵌套多层后。

最容易被忽略的一点:分区函数返回的 pivotIndex 是相对于入参切片的起始下标(即 low),不是相对于原始数组。如果你在递归调用时误写成 QuickSort(arr, 0, pivotIndex-1),就全乱了。

  • 始终用绝对下标传参:QuickSort(arr, low, pivotIndex-1) 和 QuickSort(arr, pivotIndex+1, high)
  • 避免在 partition 内部修改原始切片长度(如 arr = arr[:n]),这会破坏上层对底层数组的视图
  • 测试时用固定小数组(如 []int{5,2,4,7,1})并单步打印每轮的 low、high、pivotIndex,比看最终结果更能暴露索引偏差

热门AI工具

更多
WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

立刻MV
立刻MV Hot

立刻MV是一款AI文本写作工具,AI 音乐视频(MV)创作工具。

音述AI
音述AI Hot

一款AI音频处理工具,主要用于音述AI是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区,适合需要提升相关任务效率的用户。

墨刀AI
墨刀AI Hot

一款AI图像与设计工具,主要用于产品经理的专属智能体,适合需要提升相关任务效率的用户。

二狗PPT
二狗PPT Hot

一款AI演示文稿工具,主要用于专为中式职场打造的AI PPT生成工具,适合需要提升相关任务效率的用户。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

超级麦吉

一款通过数字员工协作完成调研、数据分析与文档制作的AI办公平台。

小橡皮AI

一款AI工具,主要用于小橡皮一键去AI味,将机器味重的内容改得更有活人感,防止因为 AI 内容被平台打上 AI 标签,以及限流,适合需要提升相关任务效率的用户。

相关专题

更多
Golang 入门学习路线:从零基础到上手开发
Golang 入门学习路线:从零基础到上手开发

Golang 入门路线涵盖从零到上手的核心路径:首先打牢基础语法与切片等底层机制;随后攻克 Go 的灵魂——接口设计与 Goroutine 并发模型;接着通过 Gin 框架与 GORM 深入 Web 开发实战;最后在微服务与云原生工具开发中进阶,旨在培养具备高性能并发处理能力的后端工程师。

246

2026.02.24

Golang 疑难杂症解决指南:常见问题排查与优化
Golang 疑难杂症解决指南:常见问题排查与优化

《Golang 疑难杂症解决指南》聚焦开发过程中常见却棘手的问题,从并发模型、内存管理、性能瓶颈到工程化实践逐步拆解。通过真实案例与调试思路,帮助开发者定位问题根因,建立系统化排查方法。不只给出答案,更强调分析路径与工具使用,让你在复杂 Go 项目中具备持续解决问题的能力。

153

2026.02.24

Golang 运行与部署实战:从本地到云端
Golang 运行与部署实战:从本地到云端

《Golang 运行与部署实战》围绕 Go 应用从开发完成到稳定上线的完整流程展开,系统讲解编译构建、环境配置、日志与配置管理、容器化部署以及常见运维问题处理。结合真实项目场景,拆解自动化构建与持续部署思路,帮助开发者建立可靠的发布流程,提升服务稳定性与可维护性。

697

2026.02.24

Golang 面试题精选:高频问题与解答
Golang 面试题精选:高频问题与解答

Golang 面试题精选》系统整理企业常见 Go 技术面试问题,覆盖语言基础、并发模型、内存与调度机制、网络编程、工程实践与性能优化等核心知识点。每道题不仅给出答案,还拆解背后的设计原理与考察思路,帮助读者建立完整知识结构,在面试与实际开发中都能更从容应对复杂问题。

258

2026.02.24

Golang 性能优化专题:提升应用效率
Golang 性能优化专题:提升应用效率

《Golang 性能优化专题》聚焦 Go 应用在高并发与大规模服务中的性能问题,从 profiling、内存分配、Goroutine 调度、GC 机制到 I/O 与锁竞争逐层分析。结合真实案例讲解定位瓶颈的方法与优化策略,帮助开发者建立系统化性能调优思维,在保证代码可维护性的同时显著提升服务吞吐与稳定性。

537

2026.02.24

Golang 生态工具与框架:扩展开发能力
Golang 生态工具与框架:扩展开发能力

《Golang 生态工具与框架》系统梳理 Go 语言在实际工程中的主流工具链与框架选型思路,涵盖 Web 框架、RPC 通信、依赖管理、测试工具、代码生成与项目结构设计等内容。通过真实项目场景解析不同工具的适用边界与组合方式,帮助开发者构建高效、可维护的 Go 工程体系,并提升团队协作与交付效率。

248

2026.02.24

Golang 并发编程专题:掌握多核时代的核心技能
Golang 并发编程专题:掌握多核时代的核心技能

《Golang 并发编程专题:掌握多核时代的核心技能》系统讲解 Go 在并发领域的设计哲学与实践方法,深入剖析 goroutine、channel、调度模型与并发安全机制,结合真实场景与性能思维,帮助开发者构建高吞吐、低延迟、可扩展的并发程序,全面提升多核时代的工程能力。

624

2026.02.26

Golang Web 开发路线:构建高效后端服务
Golang Web 开发路线:构建高效后端服务

《Golang Web 开发路线:构建高效后端服务》围绕 Go 在后端领域的工程实践,系统讲解 Web 框架选型、路由设计、中间件机制、数据库访问与接口规范,结合高并发与可维护性思维,逐步构建稳定、高性能、易扩展的后端服务体系,帮助开发者形成完整的 Go Web 架构能力。

265

2026.02.26

Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

0

2026.11.20

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn