排序算法：快速排序，golang实现

目录

前言

快速排序

代码示例

1. 算法包

2. 快速排序代码

3. 模拟程序

4. 运行程序

5. 从大到小排序

快速排序的思想

快速排序的实现逻辑

1. 选择基准值 (Pivot)

2. 分区操作 (Partition)

3. 递归排序

循环次数测试

假如 10 条数据进行排序

假如 20 条数据进行排序

假如 30 条数据进行排序

假设 5000 条数据，对比 冒泡、选择、插入、堆、归并

快速排序的适用场景

1. 大数据集

2. 随机数据

3. 缓存友好的

前言

在实际场景中，选择合适的排序算法对于提高程序的效率和性能至关重要，本节课主要讲解"快速排序"的适用场景及代码实现。

快速排序

快速排序(Quick Sort) 是一种非常高效的排序算法，采用分治法的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。其基本思想是：选择一个基准值(pivot)，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以达到整个数据变成有序序列。

代码示例

下面我们使用Go语言实现一个快速排序

1. 算法包

创建一个 pkg/algorithm.go

touch pkg/algorithm.go

(如果看过上节课的插入排序，则已存在该文件，我们就不需要再创建了)

2. 快速排序代码

打开 pkg/algorithm.go 文件，代码如下

从小到大 排序

package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
...// InsertionSort 插入排序
...// QuickSort 快速排序
func QuickSort(arr []int, low, high int) {if low < high {// partitionIndex 是分区操作后基准的索引partitionIndex := partition(arr, low, high)// 分别对基准左侧和右侧的子数组进行快速排序QuickSort(arr, low, partitionIndex-1)QuickSort(arr, partitionIndex+1, high)}
}// partition 分区操作
func partition(arr []int, low, high int) int {pivot := arr[high] // 选择最后一个元素作为基数i := low - 1for j := low; j < high; j++ {// 如果当前元素小于或等于基数if arr[j] <= pivot {i++// 交换 arr[i] 和 arr[j]arr[i], arr[j] = arr[j], arr[i]}}// 交换 arr[i+1] 和 arr[high] (基准值)arr[i+1], arr[high] = arr[high], arr[i+1]return i + 1
}

3. 模拟程序

打开 main.go 文件，代码如下：

package mainimport ("demo/pkg""fmt"
)func main() {// 定义一个切片，这里我们模拟 10 个元素arr := []int{51, 224, 67, 322, 825, 103, 50, 965, 789, 601}fmt.Println("Original data:", arr) // 先打印原始数据pkg.QuickSort(arr, 0, len(arr)-1)  // 调用快速排序fmt.Println("New data:  ", arr)    // 后打印排序后的数据
}

4. 运行程序

go run main.go

能发现， Original data 后打印的数据，正是我们代码中定义的切片数据，顺序也是一致的。

New Data 后打印的数据，则是经过快速排序后的数据，是从小到大的。

5. 从大到小排序

如果需要 从大到小 排序也是可以的，在代码里，将两个元素比较的 小于等于符号 改成 大于等于符号 即可。

修改 pkg/algorithm.go 文件：

package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
...// InsertionSort 插入排序
...// QuickSort 快速排序
func QuickSort(arr []int, low, high int) {if low < high {// partitionIndex 是分区操作后基准的索引partitionIndex := partition(arr, low, high)// 分别对基准左侧和右侧的子数组进行快速排序QuickSort(arr, low, partitionIndex-1)QuickSort(arr, partitionIndex+1, high)}
}// partition 分区操作
func partition(arr []int, low, high int) int {pivot := arr[high] // 选择最后一个元素作为基数i := low - 1for j := low; j < high; j++ {// 如果当前元素大于或等于基数if arr[j] >= pivot {i++// 交换 arr[i] 和 arr[j]arr[i], arr[j] = arr[j], arr[i]}}// 交换 arr[i+1] 和 arr[high] (基准值)arr[i+1], arr[high] = arr[high], arr[i+1]return i + 1
}

只需要一丁点的代码即可

从 package pkg 算第一行，上面示例中在第三十一行代码中，我们将 "<=" 改成了 ">=" ，这样就变成了 从大到小排序了

快速排序的思想

  • 分而治之：将大问题分解为小问题，然后递归地解决小问题，最后将小问题的解合并成原问题的解
  • 原地排序：快速排序是原地排序算法，它只需要一个很小的栈空间(用于递归)来进行排序，不需要额外的存储空间
  • 不稳定性：快速排序在某些情况下可能不是稳定的排序算法，因为相同元素的相对位置可能会在排序过程中改变

快速排序的实现逻辑

1. 选择基准值 (Pivot)

  • 在快速排序中，首先需要选择一个基准值(pivot)。基准值的选择对排序的效率有很大的影响，但在本文的示例代码中，我们简单地选择了数组的最后一个元素作为基准值

2. 分区操作 (Partition)

  • 分区操作是快速排序的核心。它的目的是将数组重新排列，使得所有比基准值小的元素都移到基准值的左边，所有比基准值大的元素都移到右边。分区操作完成后，基准值就处于其最终排序位置
  • 在 partition 函数中，我们使用两个指针 i 和 j，其中 i 指向小于基准值的最后一个元素的下一个位置(初始化为 low - 1)， j 用于遍历数组 (从 low 开始到 high - 1)。当 arr[j] 小于或等于基准值时，我们将其与 arr[i+1] 交换，并将 i 增加 1。这样，所有小于或等于基准值的元素都被交换到了基准值的左边
  • 最后，我们将基准值 (原本在 arr[high] ) 与 arr[i + 1] 交换，此时 i + 1 就是基准值的最终位置，也是分区操作的返回值

3. 递归排序

  • 分区操作完成后，我们得到了基准值的正确位置，并且数组被分成了两部分：一部分是基准值左边的所有元素 (都比基准值小)，另一部分是基准值右边的所有元素 (都比基准值大)
  • 然后，我们递归地对这两部分分别进行快速排序。这是通过调用 QuickSort 函数，并传入适当的参数 (基准值左侧和右侧的子数组的范围) 来实现的

循环次数测试

按照上面示例进行测试

假如 10 条数据进行排序

[]int{51, 224, 67, 322, 825, 103, 50, 965, 789, 601}

总计循环了 30 次

假如 20 条数据进行排序

[]int{997, 387, 461, 530, 979, 502, 36, 459, 99, 60, 454, 37, 182, 273, 529, 130, 315, 351, 975, 497}

总计循环了 83 次

假如 30 条数据进行排序

[]int{755, 247, 642, 652, 38, 587, 387, 284, 476, 924, 339, 830, 614, 534, 832, 450, 8, 641, 768, 788, 472, 750, 169, 479, 386, 124, 868, 259, 550, 613}

总计循环了 138 次

上面我们说到，"基准值的选择对排序的效率有很大的影响"，我们修改一条，依旧使用 30 条数据，我们将其最后一位数据 613，改成其他数 120 (这个值可随便改，这里示例 120)

通过调试，循环了 151 次

如果将 120 改成 700

通过调试，循环了 131 次

假设 5000 条数据，对比 冒泡、选择、插入、堆、归并

  • 冒泡排序：循环次数 12,502,499 次
  • 选择排序：循环次数 12,502,499 次
  • 插入排序：循环次数 6,323,958 次
  • 快速排序：循环次数 74,236 次
  • 堆排序：循环次数 59,589 次
  • 归并排序：循环次数 60,288 次

快速排序的适用场景

快速排序在多种情况下都是非常高效的，特别是以下几种情况：

1. 大数据集

对于大数据集，快速排序通常比简单的排序算法 (如 冒泡排序、插入排序) 更快

2. 随机数据

当输入数组中的数据是随机分布的时，快速排序的平均时间复杂度是 O(n log n)，这是非常高效的

3. 缓存友好的

快速排序通过递归地在数组的不同部分上工作，倾向于产生良好的缓存局部性，特别是在处理大数据集时

然后，快速排序在某些情况下可能不是最佳选择，例如：

  • 小数据集：对于非常小的数据集，快速排序的递归开销可能使得它不如简单的排序算法 (如 插入排序) 快
  • 几乎已经排序的数据：在这种情况下，快速排序的性能可能退化为 O(n^2)，因为它依赖于分区操作来减少问题的规模。如果分区操作不能有效地减少数组的大小 (例如，基准值总是最大或最小的元素)，则会导致性能下降。在这种情况下，可以考虑使用归并排序或堆排序等算法
  • 不稳定的排序需求：虽然快速排序在大多数情况下是稳定的 (如果实现得当)，但在某些特定实现中可能不是。如果稳定性是排序算法的一个关键要求，可能需要考虑其他算法

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/388393.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

DC-7靶机通关

DC-7靶机通关

今天咱们来学习第七个靶机&#xff01;&#xff01;&#xff01; 1实验环境 攻击机&#xff1a;kali2023.2 靶机&#xff1a;DC-7 2.1主机发现 2.2端口扫描 依旧是开了两个端口&#xff0c;一个 22 一个 80 &#xff01;&#xff01;&#xff01; 3.1查看对方网页 在这里我…
阅读更多...
2024年必备技能：小红书笔记评论自动采集，零基础也能学会的方法

2024年必备技能：小红书笔记评论自动采集，零基础也能学会的方法

摘要&#xff1a; 面对信息爆炸的2024年&#xff0c;小红书作为热门社交平台&#xff0c;其笔记评论成为市场洞察的金矿。本文将手把手教你&#xff0c;即便编程零基础&#xff0c;也能轻松学会利用Python自动化采集小红书笔记评论&#xff0c;解锁营销新策略&#xff0c;提升…
阅读更多...
redis的集群（高可用）

redis的集群（高可用）

redis集群的三种模式&#xff1a; 主从复制 奇数 三台 一主两从 哨兵模式 3 一主两从 cluster集群 六台 主从复制&#xff1a;和mysql的主从复制类似&#xff0c;主可以写&#xff0c;写入主的数据通过RDB方式把数据同步到从服务器&#xff0c;从不能更新到主&#xff0c;也…
阅读更多...
【卫星载荷之QF项目-001】Vivado 2018.3安装

【卫星载荷之QF项目-001】Vivado 2018.3安装

1.简介 Vivado 是 FPGA 厂商赛灵思公司&#xff08;Xilinx&#xff09;于 2012 年起发布的集成设计环境。Vivado2018.3 是 2018 年 Xilinx 推出的 Vivado 最后一个版本&#xff0c;相对稳定。 2.软件下载 网上自己去官网即可获取安装资源包。 3.软件安装 解压缩安装包&…
阅读更多...
通配符/泛域名https证书申请流程

通配符/泛域名https证书申请流程

通配符证书也叫泛域名证书&#xff0c;是一种SSL/TLS证书&#xff0c;用于同时保护一个域名及其所有二级子域名的安全&#xff0c;如果企业拥有众多子域名&#xff0c;那么通配符证书是一个非常合适的选择。市面上通配符证书很多&#xff0c;但是收费不一&#xff0c;从哪里申请…
阅读更多...
开放式耳机有哪些比较推荐的？开放式耳机五款精品推荐

开放式耳机有哪些比较推荐的？开放式耳机五款精品推荐

看到这篇文章的小伙伴&#xff0c;没错&#xff0c;这篇文章就是为了告诉你如何去挑选一款适合自己的开放式耳机&#xff0c;作为一个开放式耳机的测评师&#xff0c;这几年开放式耳机的产品是越来越多&#xff0c;我们的选择也是越来越多元&#xff0c;所以在我们面对这么多选…
阅读更多...
Java 应用性能优化

Java 应用性能优化

一、性能调优涉及哪些方面 Java 编程性能调优。包括数据类型&#xff0c;集合容器&#xff0c;网络通信。 多线程性能调优。包括线程安全&#xff0c;同步锁的问题&#xff0c;多线程的性能问题。 JVM 性能监控及调优。包括Java对象的创建和回收&#xff0c;内存分配。 设计…
阅读更多...
CRC的手算过程——MODBUS

CRC的手算过程——MODBUS

软件计算结果&#xff1a; 原理参考下面的文章&#xff1a; https://www.cnblogs.com/esestt/archive/2007/08/09/848856.html https://blog.csdn.net/weixin_44256803/article/details/105805628 https://blog.csdn.net/d_leo/article/details/73572373 手算过程如下&#x…
阅读更多...
LeetCode面试150——122买卖股票的最佳时机II

LeetCode面试150——122买卖股票的最佳时机II

题目难度&#xff1a;中等 默认优化目标&#xff1a;最小化平均时间复杂度。 Python默认为Python3。 目录 1 题目描述 2 题目解析 3 算法原理及题目解析 3.1 动态规划 3.2 贪心算法 参考文献 1 题目描述 给你一个整数数组 prices &#xff0c;其中 prices[i] 表示某支…
阅读更多...
如何做OLED屏幕安装方案

如何做OLED屏幕安装方案

制定OLED屏幕安装方案时&#xff0c;需要综合考虑多个方面&#xff0c;包括安装环境、屏幕尺寸、支架选择、电源与信号连接、调试与测试等。以下是一个详细的OLED屏幕安装方案&#xff1a; 一、前期准备 确定安装位置&#xff1a; 根据使用需求和环境条件&#xff0c;选择一个…
阅读更多...
装修新选择：探索浦东地区口碑排名前五的大平层装修公司！

装修新选择：探索浦东地区口碑排名前五的大平层装修公司！

在繁华的浦东中寻找一个安静的港湾&#xff0c;大平层无疑是许多成功人士的首选。宽敞的空间、自由的布局设计&#xff0c;以及优雅的生活氛围&#xff0c;都是大平层备受青睐的理由。以下为您探索的浦东地区口碑排名前五的大平层装修公司&#xff1a; 1.即住空间装饰 即住空…
阅读更多...
MoE：混合专家模型介绍（一）

MoE：混合专家模型介绍（一）

MoE&#xff1a;混合专家模型介绍&#xff08;一&#xff09; 本文是对混合专家模型 (MoE) 详解重点摘要与归纳&#xff0c;有兴趣的小伙伴可以点击链接阅读原文。 混合专家模型 (MoEs)特点 与稠密模型相比&#xff0c;预训练速度更快与具有相同参数数量的模型相比&#xff…
阅读更多...
与OpenAI合作：期待已久的苹果AI战略

与OpenAI合作：期待已久的苹果AI战略

探讨 Apple 和 OpenAI 合作的AI战略 ©作者|CodeDan 来源|神州问学 一&#xff0e;引言 在当今科技发展日新月异的背景下&#xff0c;大型科技公司的合作与联盟日益成为关注焦点。在最近的2024苹果全球开发者大会上&#xff0c;苹果展示了最新苹果系统上搭载的大模型应用…
阅读更多...
Godot入门 05收集物品

Godot入门 05收集物品

创建新场景&#xff0c;添加Area2D节点&#xff0c;AnimatedSprite2D节点 &#xff0c;CollisionShape2D节点 添加硬币 按F键居中&#xff0c;放大视图。设置动画速度设为10FPS&#xff0c;加载后自动播放&#xff0c;动画循环 碰撞形状设为圆形&#xff0c;修改Area2D节点为Co…
阅读更多...
Vue3父子组件传属性和方法调用Demo

Vue3父子组件传属性和方法调用Demo

Vue3父子组件传属性和方法调用Demo 说明目录父组件给子组件传值和方法父组件给子组件传值-使用defineProps接受父组件属性值父组件给子组件传值-使用defineModel接受父组件v-model值当子组件只需要接收父组件一个v-model值时,写法1如下:子组件接收单个v-model写法2如下:当子组件…
阅读更多...
海尔智家三翼鸟：从家电到场景，能否跨越智能化陷阱？

海尔智家三翼鸟：从家电到场景，能否跨越智能化陷阱？

在智能家居浪潮的席卷之下&#xff0c;三翼鸟作为海尔智家旗下的场景品牌&#xff0c;曾一度被视为传统家电厂商转型升级的典范。然而&#xff0c;在光鲜亮丽的宣传背后&#xff0c;三翼鸟正逐步暴露出难以忽视的困境与挑战&#xff0c;其智能化之路似乎并不如预期般顺畅。 从用…
阅读更多...
微软：云服务大规模宕机因DDoS“防卫过当”

微软：云服务大规模宕机因DDoS“防卫过当”

杀毒软件导致全球蓝屏&#xff0c;DDoS防护导致云服务宕机&#xff0c;微软这家全球最大的网络安全公司&#xff0c;正在不断刷新人们对“安全威胁”的认知。 微软本周三晚间宣布&#xff0c;本周二全球范围内多个Microsoft 365和Azure云服务大规模长时间宕机事件的原因&#…
阅读更多...
AI大模型应用(2)ChatGLM3本地部署及其在alpaca_zh数据集上的低精度微调

AI大模型应用(2)ChatGLM3本地部署及其在alpaca_zh数据集上的低精度微调

AI大模型应用(2)ChatGLM3部署及其在alpaca_zh数据集上的低精度微调 我们之前已经了解了HuggingFace中peft库的几种高效微调方法。 参数高效微调PEFT(一)快速入门BitFit、Prompt Tuning、Prefix Tuning 参数高效微调PEFT(二)快速入门P-Tuning、P-Tuning V2 参数高效微调PEFT…
阅读更多...
deepseek杀疯了，偷摸开源全球一梯队大模型——DeepSeek-V2-Chat-0628

deepseek杀疯了，偷摸开源全球一梯队大模型——DeepSeek-V2-Chat-0628

就在今年6月&#xff0c;深度求索团队发布了DeepSeek-V2模型后不久&#xff0c;新版本DeepSeek-V2-Chat-0628 模型也在7月开源了。其推理能力有了极大提升。尤其在数学解题、逻辑推理、编程、指令跟随、Json格式输出不同维度上&#xff0c;最高有16%的性能提升。 在Arena-Hard…
阅读更多...
推荐一款前端滑动验证码插件（Vue、uniapp）

推荐一款前端滑动验证码插件（Vue、uniapp）

uniapp版本&#xff1a;滑块拼图验证码&#xff0c;有后端&#xff0c;简单几步即可实现&#xff0c;小程序、h5都可以用 - DCloud 插件市场 Vue版本及cdn版本可以查阅文档&#xff1a; 行为验证 | Poster 文档 示例代码&#xff1a; <template><view id"app&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发