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

目录

前言

快速排序

代码示例

1. 算法包

2. 快速排序代码

3. 模拟程序

4. 运行程序

5. 从大到小排序

快速排序的思想

快速排序的实现逻辑

1. 选择基准值 (Pivot)

2. 分区操作 (Partition)

3. 递归排序

循环次数测试

假如 10 条数据进行排序

假如 20 条数据进行排序

假如 30 条数据进行排序

快速排序的适用场景

1. 大数据集

2. 随机数据

3. 缓存友好的

前言

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

快速排序

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

代码示例

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

1. 算法包

创建一个 pkg/algorithm.go

mkdir 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 次

快速排序的适用场景

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

1. 大数据集

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

2. 随机数据

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

3. 缓存友好的

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

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

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

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

LLM大模型：十大人工智能大模型技术介绍

LLM大模型：十大人工智能大模型技术介绍

十大人工智能大模型技术的简介&#xff1a; 深度学习模型 深度学习是人工智能领域中一种重要的机器学习技术&#xff0c;通过构建深度神经网络来模拟人脑的认知过程。深度学习模型能够自动提取数据的特征&#xff0c;并在海量数据中进行学习和优化&#xff0c;从而在语音识别…
阅读更多...
【优秀python案例】基于Python的京东商城口红商品的爬虫与可视化的设计与实现

【优秀python案例】基于Python的京东商城口红商品的爬虫与可视化的设计与实现

摘要&#xff1a;随着互联网的普及&#xff0c;网络购物已经成为了人们购物的首选&#xff0c;用户只需要在电商平台上进行自己喜欢的商品进行搜素&#xff0c;就可以得到成千上万条商品信息。而在购买商品时&#xff0c;商品价格就成为了用户的主要关注对象&#xff0c;而在一…
阅读更多...
安科瑞ASJ系列智能剩余电流继电器介绍

安科瑞ASJ系列智能剩余电流继电器介绍

产品概述&#xff1a; 安科瑞ASJ系列智能剩余电流继电器是一种重要的电气安全保护设备&#xff0c;‌主要用于交流50Hz、‌额定电压400V及以下的TT和TN系统配电线路中。‌该系列继电器的主要功能包括对电气线路进行接地故障保护&#xff0c;‌以防止接地故障电流引起的设备损坏…
阅读更多...
UE4调试手段：主动崩溃与“.pdb”解析“.dmp”文件

UE4调试手段：主动崩溃与“.pdb”解析“.dmp”文件

主动崩溃 尝试了一些做法&#xff0c;发现 check(false) 对于Development配置而言&#xff0c;是有效果的&#xff0c;代码如下&#xff1a; // Called when the game starts or when spawned void AMyActor::BeginPlay() {Super::BeginPlay();check(false); // 尝试用这个来…
阅读更多...
基于 SSM 的电器网上订购系统

基于 SSM 的电器网上订购系统

基于 SSM 的电器网上订购系统 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;Spring、JSP、MyBatis工具&#xff1a;MyEclipse/IDEA、Tomcat 课题背景 近年来&#xff0c;随着Internet的迅速崛起&#xff0c;互联网已日益成为收集提供信息的最佳渠道并逐…
阅读更多...
设计模式 - Singleton pattern 单例模式

设计模式 - Singleton pattern 单例模式

文章目录 定义单例模式的实现构成构成UML图 单例模式的六种实现懒汉式-线程不安全懒汉式-线程安全饿汉式-线程安全双重校验锁-线程安全静态内部类实现枚举实现 总结其他设计模式文章&#xff1a;最后 定义 单例模式是一种创建型设计模式&#xff0c;它用来保证一个类只有一个实…
阅读更多...
python做简单爬虫的一些常用组件

python做简单爬虫的一些常用组件

文章目录 前言requestjsonbs4 前言 最近一直在做零散的一次性的爬虫工作&#xff0c;基本都是用python开发的&#xff0c;整理一下python做小规模爬虫开发常用的一些工具类 request python最简单的发http请求的包&#xff0c;request.get和request.post就可以搞定绝大部分的…
阅读更多...
【Github】Github 上commit后 contribution 绿格子不显示 | Github绿格子 | Github贡献度不显示

【Github】Github 上commit后 contribution 绿格子不显示 | Github绿格子 | Github贡献度不显示

一、Github 消失的绿点 1、贡献值为什么没了&#xff1f; 2、选择要显示的贡献 如下配置 二、如何解决消失的绿点&#xff1f; 1、添加邮箱 确保邮箱的设置必须选择一个邮箱邮箱 2、git config 添加邮箱 设置邮箱如下&#xff1a; git config --local user.email 316434776…
阅读更多...
使用标量函数实现 EF Core 的实用方法

使用标量函数实现 EF Core 的实用方法

一.介绍 在构建应用程序时&#xff0c;您可能使用标量函数在数据库端实现一些逻辑。在 SQL 中&#xff0c;标量函数是一种对单个值或少量输入值进行操作并始终返回单个值作为输出的函数。这些函数本质上是可重复使用的代码块&#xff0c;用于对数据执行计算或操作。 以下是标…
阅读更多...
Java面试——Tomcat

Java面试——Tomcat

优质博文&#xff1a;IT_BLOG_CN 一、Tomcat 顶层架构 Tomcat中最顶层的容器是Server&#xff0c;代表着整个服务器&#xff0c;从上图中可以看出&#xff0c;一个Server可以包含至少一个Service&#xff0c;用于具体提供服务。Service主要包含两个部分&#xff1a;Connector和…
阅读更多...
Java实现数据库图片上传（包含从数据库拿图片传递前端渲染）-图文详解

Java实现数据库图片上传（包含从数据库拿图片传递前端渲染）-图文详解

目录 1、前言&#xff1a; 2、数据库搭建 &#xff1a; 建表语句&#xff1a; 3、后端实现&#xff0c;将图片存储进数据库&#xff1a; 思想&#xff1a; 找到图片位置&#xff08;如下图操作&#xff09; 图片转为Fileinputstream流的工具类&#xff08;可直接copy&#…
阅读更多...
系统学习渗透测试：从零到精通的全面指南

系统学习渗透测试：从零到精通的全面指南

渗透测试&#xff0c;作为网络安全领域的一项重要技术&#xff0c;旨在通过模拟黑客攻击来评估计算机系统的安全性。对于想要系统学习渗透测试的人来说&#xff0c;这既是一条充满挑战的道路&#xff0c;也是一次深入了解网络安全的宝贵机会。本文将从基础知识、技能提升、实战…
阅读更多...
【释放品牌魅力，开启营销新篇章】—— 短视频矩阵营销系统源码

【释放品牌魅力，开启营销新篇章】—— 短视频矩阵营销系统源码

【释放品牌魅力&#xff0c;开启营销新篇章】—— 短视频矩阵营销系统在这个数字化高速发展的时代&#xff0c;您是否还在为品牌曝光度不足、营销效果不佳而苦恼&#xff1f;来吧&#xff0c;让我们一起探索全新的解决方案——短视频矩阵营销系统&#xff01; 在这个数字化高速…
阅读更多...
NC 缺失的第一个正整数

NC 缺失的第一个正整数

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff0c;这篇文章男女通用&#xff0c;看懂了就去分享给你的码吧。 描述 给定一个无重…
阅读更多...
AI初学者必看： 什么是大型语言模型 (LLM)？

AI初学者必看： 什么是大型语言模型 (LLM)？

介绍 “人工智能&#xff08;AI&#xff09;”一词于 1956 年问世&#xff0c;如今已为大家所熟知。然而&#xff0c;在 ChatGPT 迅速流行之前&#xff0c;AI 的使用和讨论大多局限于科学研究或虚构电影。如今&#xff0c;AI 尤其是生成式 AI 已成为大家热议的话题。 初学者生…
阅读更多...
详解校门外的树(树状数组)

详解校门外的树(树状数组)

前言 在看之前建议先看一下 【学习笔记】详解树状数组-CSDN博客 题目 思路 建立两个树状数组,维护左括号与右括号。 假设有一个长度为10的数轴&#xff0c;我们要将区间[ 2 , 5 ]中种树&#xff0c;这时&#xff0c;我们将 2 处放一个左括号 ” ( ” ,5处放一个 ” )” &…
阅读更多...
3DMAX神经网络插件Neuron使用方法详解

3DMAX神经网络插件Neuron使用方法详解

3DMAX神经网络插件Neuron使用方法 3DMAX神经网络插件Neuron&#xff0c;从一系列样条曲线创建具有分支结构的几何体。适用于如神经网络、血管、树枝等形状的3D建模。 【适用版本】 3dMax2016及更高&#xff08;不仅限于此范围&#xff09; 【安装方法】 Neuron插件无需安装&a…
阅读更多...
【C++】跳转语句-continue语句

【C++】跳转语句-continue语句

continue语法特点&#xff1a; 中止循环后会继续执行下面循环&#xff08;除了continue所跳出的那些执行操作不会执行&#xff09; 这也是额continue语句和break语句最大的区别 break是直接跳出循环不再执行下面步骤 #include<iostream> using namespace std;int main…
阅读更多...
收集树中的金币

收集树中的金币

提示 1 定义一个点的度数为其邻居个数。如果一个点的度数为 1&#xff0c;那么这个点叫做叶子节点&#xff0c;例如示例 2 的 3,4,6,7 都是叶子节点。 如果叶子节点没有金币&#xff0c;我们有必要移动到叶子节点吗&#xff1f;没有必要。 那么可以先把这些没有金币的叶子节点…
阅读更多...
等保学习干货|等保测评2.0技术中间件自查阶段，零基础入门到精通，收藏这一篇就够了

等保学习干货|等保测评2.0技术中间件自查阶段，零基础入门到精通，收藏这一篇就够了

0x01 前言 以下是根据我国网络安全体系制订的一系列保护流程进行的等级保护测评。该测评针对已有和将上线的业务服务的基础设施&#xff08;系统、数据库、中间件等&#xff09;&#xff0c;执行一系列检查以确保安全合规。本次先行分享学习等保中的技术自查阶段知识&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023