排序算法:选择排序,golang实现
目录
前言
选择排序
代码示例
1. 算法包
2. 选择排序代码
3. 模拟排序
4. 运行程序
5. 从大到小排序
循环细节
外层循环
内层循环
总结
选择排序的适用场景
1. 数据规模非常小
2. 稳定性不重要
3. 几乎全部数据已排序
4. 教育目的
前言
在实际场景中,选择合适的排序算法对于提高程序的效率和性能至关重要,本节课主要讲解"选择排序"的适用场景及代码实现。
选择排序
选择排序(Selection Sort) 是一种简单直观的排序算法,它的工作原理是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
代码示例
下面我们使用Go语言实现一个选择排序:
1. 算法包
创建一个 pkg/algorithm.go
mkdir pkg/algorithm.go
(如果看过上节课的冒泡排序,则已存在该文件,我们就不需要再创建了)
2. 选择排序代码
打开 pkg/algorithm.go 文件,代码如下
从小到大 排序
package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
func SelectionSort(arr []int) {n := len(arr) // 获取切片长度for i := 0; i < n-1; i++ {// 假设当前位置是最小的minIndex := i// 遍历未排序的部分,寻找真正的最小值的索引for j := i + 1; j < n; j++ {if arr[j] < arr[minIndex] {minIndex = j}}// 如果找到更小的数,就交换arr[i], arr[minIndex] = arr[minIndex], arr[i]}
}
3. 模拟排序
打开 main.go 文件,代码如下:
package mainimport ("demo/pkg""fmt"
)func main() {// 定义一个切片,这里我们模拟 10 个元素arr := []int{789, 59, 1500, 847, 633, 2456, 901, 2, 752, 100}fmt.Println("Original data:", arr) // 先打印原始数据pkg.SelectionSort(arr) // 调用选择排序fmt.Println("New data: ", arr) // 后打印排序后的数据
}
4. 运行程序
打开终端,我们运行 go :
go run main.go
能发现, Original data 后打印的数据,正是我们代码中定义的切片数据,顺序也是一致的。
New Data 后打印的数据,则是经过选择排序后的数据,是从小到大的。
5. 从大到小排序
如果需要 从大到小 排序也是可以的,在代码里,将两个元素比较的 大于符号 改成 小于符号 即可。
修改 pkg/algorithm.go 文件:
package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
func SelectionSort(arr []int) {n := len(arr) // 获取切片长度for i := 0; i < n-1; i++ {// 假设当前位置是最小的minIndex := i// 遍历未排序的部分,寻找真正的最小值的索引for j := i + 1; j < n; j++ {if arr[j] > arr[minIndex] {minIndex = j}}// 如果找到更小的数,就交换arr[i], arr[minIndex] = arr[minIndex], arr[i]}
}
只需要一丁点的代码即可
从 package pkg 算第一行,上面示例中在第十四行代码中,我们将 "<" 改成了 ">" ,这样就变成了 从大到小排序了
补充:
代码里还有一处可以完善,在最后两个数进行交换时
思考一下这一行代码:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
如果,arr[minIndex] 和 arr[i] 这两个数是相同的,那么还有必要进行交换吗?
当然是可以不用交换,所以我们可以再加上一个判断:
// 如果它们不相等
if arr[minIndex] != arr[i] {// 如果找到更小的数,就交换arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
循环细节
在选择排序算法中,外层循环和内层循环扮演着至关重要的角色,它们共同协作以实现对整个数组的排序。下面是这两个循环的详细说明
外层循环
- 目的:外层循环负责控制排序的轮次。对于包含 n 个元素的数组,外层循环需要进行 n - 1 轮排序(因为当只剩下一个元素时,它自然就是排序好的)。每一轮排序都会从未排序的部分找到一个最小(或最大)的元素,并将其放到已排序部分的末尾
- 起始与结束:外层循环通常从一个起始索引(如 0)开始,直到达到数组长度减 1 (n - 1) 的索引结束。这是因为当外层循环到达 n - 1 时,所有元素都已经排好序,只剩下最后一个元素(即索引为 n - 1 的元素),它自然就是已排序的
- 作用:在每一轮排序开始时,外层循环的索引(假设为 i )代表当前已排序部分的末尾。然后,内层循环会从未排序的部分(即索引 i + 1 到 n - 1 的部分)中找到一个最小(或最大)元素的索引,并与索引 i 处的元素进行可能的交换
内层循环
- 目的:内层循环负责在每一轮排序中,从未排序的部分找到最小(或最大)元素的索引。一旦找到,就可能与当前轮次的外层循环索引处的元素进行交换(如果它们不是同一个元素的话)
- 起始与结束:内层循环的起始索引通常是外层循环索引的下一个位置(即 i + 1),而结束索引是数组的最后一个元素(即 n - 1)。这是因为内层循环需要遍历整个未排序的部分来找到最小(或最大)的元素
- 作用:在每一轮外层循环中,内层循环都会遍历未排序的部分,通常比较来找到最小(或最大)元素的索引。这个索引会被存储在某个变量中(如 minIndex),以便在遍历结束后与外层循环索引处的元素进行可能的交换
- 交换:如果内层循环找到了一个比外层循环索引处更小的元素(即 minIndex 不等于外层循环的索引 i ),那么就需要进行交换操作,将这两个元素的位置互换。这样,外层循环索引处的元素就变成了当前轮次中未排序部分的最小(或最大)元素,被正确地放置在了已排序部分的末尾
总结
外层循环控制排序的轮次,每一轮都试图从未排序的部分找到一个最小(或最大)元素,并将其放置到正确的位置上。内层循环则负责在每一轮中执行这个查找和可能的交换操作。通过这两层循环的协作,整个数组最终被排序完成。
选择排序的适用场景
尽管选择排序在大多数现代应用中不是最高效的排序算法(其平均和最坏情况时间复杂度都是 O(n ^ 2)),但在某些特定场景下,它仍然有其用途
1. 数据规模非常小
对于非常小的数据集,选择排序在效率损失可能微不足道,而它实现简单,易于理解和实现
2. 稳定性不重要
选择排序不是稳定的排序算法(即相等元素的相对顺序可能会改变)。如果应用场景不需要保持元素的原始相对顺序,那么选择排序可以作为一个简单的选择
3. 几乎全部数据已排序
虽然理论上来说,即使数据几乎全部已排序,选择排序的效率也不会显著提升,但在某些特定应用中,如果已知数据集接近排序状态,并且算法设计可以利用这一点(例如,通过提前终止不必要的比较)。则可能略有优势。然而,这通常需要结合其他优化技巧
4. 教育目的
由于选择排序简单直观,它常被用于教学目的,帮助学生理解排序算法的基本概念和工作原理
总之,尽管存在更高效的排序算法,但在特定场景下,选择排序仍然有其用武之地。
相关文章:
排序算法:选择排序,golang实现
目录 前言 选择排序 代码示例 1. 算法包 2. 选择排序代码 3. 模拟排序 4. 运行程序 5. 从大到小排序 循环细节 外层循环 内层循环 总结 选择排序的适用场景 1. 数据规模非常小 2. 稳定性不重要 3. 几乎全部数据已排序 4. 教育目的 前言 在实际场景中…...
【测试】博客系统的测试报告
项目背景 个人博客系统采用了 SSM 框架与 Redis 缓存技术的组合 ,为用户提供了一个功能丰富、性能优越的博客平台。 在技术架构上 ,SSM 框架确保了系统的稳定性和可扩展性。Spring 负责管理项目的各种组件 ,Spring MVC 实现了清晰的请求处理…...
PointCLIP: Point Cloud Understanding by CLIP
Abstract 近年来,基于对比视觉语言预训练(CLIP)的零镜头和少镜头学习在二维视觉识别中表现出了令人鼓舞的效果,该方法在开放词汇设置下学习图像与相应文本的匹配。然而,通过大规模二维图像-文本对预训练的CLIP是否可以推广到三维识别&#x…...
搜索(剪枝)
定义: 剪枝,就是减少搜索树的规模、尽早排除搜索树中不必要分支的一种手段。 在深度优先搜索中,有以下几类常见的剪枝方法: 优化搜索顺序排除等效冗余可行性剪枝最优性剪枝记忆化剪枝 例题1:AcWing 167.木棒 题目:…...
python基础知识点
最近系统温习了一遍python基础语法,把自己不熟知的知识点罗列一遍,便于查阅~~ python教程 Python 基础教程 | 菜鸟教程 1、python标识符 以单下划线开头 _foo 的代表不能直接访问的类属性,需通过类提供的接口进行访问,不能用 f…...
Android SurfaceFlinger——GraphicBuffer获取内存信息(三十一)
上一篇文章介绍了 GraphicBuffer 初始化的 initWithSize() 函数中的申请内存流程,这里我们看一下另一个比较重要的函数,GraphicBufferMapper. getTransportSize 获取内存信息。该函数通常在需要了解缓冲区的实际内存占用情况时调用,例如在调试内存使用情况或优化性能时。 一…...
基于 SASL/SCRAM 让 Kafka 实现动态授权认证
一、说明 在大数据处理和分析中 Apache Kafka 已经成为了一个核心组件。然而在生产环境中部署 Kafka 时,安全性是一个必须要考虑的重要因素。SASL(简单认证与安全层)和 SCRAM(基于密码的认证机制的盐化挑战响应认证机制ÿ…...
通用多级缓件组件
背景 业界第三方缓存框架一般为redis,本地缓地ehcache或guava,一般通过spring提供的restTemplate操作缓存 然而这样会存在以下问题: 与缓存中间件强耦合需手动整合多级缓存不支持注解数据更新时无法自动刷新缓存存在缓存穿透、缓存击穿、缓…...
MindIE Service服务化集成部署通义千问Qwen模型
一、昇腾开发者平台申请镜像 登录Ascend官网昇腾社区-官网丨昇腾万里 让智能无所不及 二、登录并下载mindie镜像 #登录docker login -u XXX#密码XXX#下载镜像docker pull XXX 三、下载Qwen的镜像 使用wget命令下载Qwen1.5-0.5B-Chat镜像,放在/mnt/Qwen/Qwen1.5-…...
chrome 接口请求等待时间(installed 已停止)过长问题定位
参考: 解决实际项目中stalled时间过久的问题 背景: 测试反馈系统开 6 个标签页后, 反应变的很慢 定位: 看接口请求瀑布流, 已停止时间很长, 后端返回速度很快, 确定是前端的问题 推测是并发请求窗口数量的问题, 屏蔽部分一直 pending 的接口, 发现速度正常了, 搜到上面的参…...
HDialog特殊动画效果
基于HDialog的特殊动画效果实现 业务场景 在开发过程中直接使用HDialog所展现的效果很快,同时不能够与用户所点击位置进行交互,会造成用户的体验观感不够好。因此需要实现一种能够从用户点击按钮位置以可变动画效果所展现的Dialog效果。 工作原理及实…...
基因组挖掘指导天然药物分子的发现-文献精读34
基因组挖掘指导天然药物分子的发现 摘要 天然产物是临床药物的主要来源,也是新药研发过程中先导化合物结构设计和优化的灵感源泉。但传统策略天然药源分子的发现却遭遇了瓶颈,新颖天然产物的数量逐渐无法满足现代药物开发的需求和应对全球多药耐药的威胁…...
hcip学习 DHCP中继
DHCP 中继 在可能收到 DHCP Discover 报文的接口配置 DHCP 中继, 指明 DHCP 服务器的地址,然后将 DHCP 发现报文以单播的形式送到 DHCP 服务器上 DHCP 中继报文的源地址和目标地址怎么确定 1、源地址:收到 Discover 报文的接口地址 2、目…...
[Mysql-函数、索引]
目录 函数: 日期函数 字符串函数 数学函数 聚合函数 索引: 索引分类 慢查询 创建索引 函数: MySQL函数,是一种控制流程函数,属于数据库用语言。 MySQL常见的函数有: 数学函数 用作常规的数学运…...
org.eclipse.jgit 简单总结
org.eclipse.jgit 是一个用于处理 Git 版本控制系统的纯 Java 库。它允许你读取和写入 Git 仓库,执行如克隆、拉取、推送、提交等操作。下面我将通过几个例子来展示如何使用 org.eclipse.jgit 进行一些常见的 Git 操作。 1. 克隆仓库 克隆一个远程 Git 仓库到本地目…...
Fork软件笔记:一键拉取仓库所有模块
Fork是一个好用的git工具,只是没有中文而已(不过不用翻译也能看使用)。 工具下载地址:https://fork.dev/ 界面展示: 当项目中仓库模块比较多时,可以看到每个模块都是一个分页,每一个都要手动切换…...
常见的锂电保护芯片 单节锂电保护/双节锂电保护芯片
目前外出贸易的要求不断增多,出口的产品基本上都需要带上锂电保护芯片 以下是常见的单节锂电保护芯片的选型 包括了市面上大部分的可用型号。 锂电保护芯片的脚位上面基本都是通用,可以直接替代 双节的锂电保护使用情况较少,需要外置MOS管调节…...
初识Java(六)
一、String类 1、类中有操作字符串的方法 查找:找到某个字符是字符串内的第几个:charAt;找到某个字符在字符串内第一次出现的下标:index 替换:替换所有:replaceAll;替换首个:repla…...
Spring-原理篇-DispatcherServlet 初始化 怎么和IOC进行了打通?
委托模式的体现,在初始化醒目的时候Spring MVC为我们提供了一个DispatcherServlet,映射了所有的路径,所有的请求都会先到达这里然后被转发到具体的Controller 进行处理,此文来探索一下,DispatcherServlet 初始化的时候…...
关于swift- OC混编使用Pod遇到的2个错误
错误1 Cannot find interface declaration for UITableViewCell, superclass of "DEFUITalbleViewCell" Cannot find interface declaration for UIView, superclass of "DefUIView" Cannot find interface declaration for 系统类, superclass of "自…...
Golang | Leetcode Golang题解之第290题单词规律
题目: 题解: func wordPattern(pattern string, s string) bool {word2ch : map[string]byte{}ch2word : map[byte]string{}words : strings.Split(s, " ")if len(pattern) ! len(words) {return false}for i, word : range words {ch : patt…...
【Django5】模型定义与使用
系列文章目录 第一章 Django使用的基础知识 第二章 setting.py文件的配置 第三章 路由的定义与使用 第四章 视图的定义与使用 第五章 二进制文件下载响应 第六章 Http请求&HttpRequest请求类 第七章 会话管理(Cookies&Session) 第八章 文件上传…...
HTML--JavaScript操作DOM对象
目录 本章目标 一.DOM对象概念 编辑 二.节点访问方法 常用方法: 层次关系访问节点 三.节点信息 四.节点的操作方法 操作节点的属性 创建节点 删除替换节点 五.节点操作样式 style属性 class-name属性 六.获取元素位置 总结 本章目标 了解DOM的分类和节…...
Redis 缓存
安装 安装 Redis 下载: Releases tporadowski/redis (github.com) winr ----services.msc-----将redis 设置为手动(只是学习,如果经常用可以设置为自动) 安装 redis-py 库 pip install redis-py Redis 和 StrictRedis redis-py 提供 Redis 和 Str…...
Prozyme糖样本检测平台--GlykoPrep® Rapid N-Glycan Preparation with APTS
单克隆抗体已成为生物制药行业具有潜力的新兴蛋白候选药物。其药物研发流程包括一系列精细的控制和评估步骤,需要仔细、严格地监测目标化合物的治疗稳定性及有效性。因此,在商业化前的每个阶段对单克隆抗体进行全面表征是极其有益的。在大量研究成熟的蛋…...
力扣面试题(一)
1、给你两个字符串 word1 和 word2 。请你从 word1 开始,通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长,就将多出来的字母追加到合并后字符串的末尾。 char * mergeAlternately(char * word1, char * word2){int len1 strlen(word1);i…...
Python 输入输出
重点内容: 1、梳理掌握输入和输出函数的应用。 2、熟练使用int() float() str()等函数进行数据转换 3、常用转义字符在数据输入、输出中的应用 4、熟练使用ljust()、center()、rjust()等方法对字符位置进行控制。 5、灵活应用ASCII码、字母、数字及特殊字符解决…...
国服最强文字转音频?Fish Speech
官网文档与示例 Fish Speech V1.2 是一款领先的文本到语音 (TTS) 模型,使用 30 万小时的英语、中文和日语音频数据进行训练。我尝试用1066运行,但是质量不尽如人意,建议使用RTX系列的显卡进行推理。 使用结果展示 text """20…...
数据结构(6):图
1 图的基本概念 1.1 基本概念 1.1.1 定义【多对多的关系】 一个图不可能是空图!!!一个图的顶点集一定是非空集,但是边集可以为空集! 1.1.2 应用 1.2 无向图和有向图 弧头是有箭头的那一边,弧尾是没有箭头…...
kaggle使用api下载数据集
背景 kaggle通过api并配置代理下载数据集datasets 步骤 获取api key 登录kaggle,点个人资料,获取到自己的api key 创建好的key会自动下载 将key放至家目录下的kaggle.json文件中 我这里是windows的administrator用户。 装包 我用了虚拟环境 pip …...
前缀表达式(波兰式)和后缀表达式(逆波兰式)的计算方式
缀是指操作符。 1. 前缀表达式(波兰式) (1)不需用括号; (2)不用考虑运算符的优先级; (3)操作符置于操作数的前面。(如 3 2 ) 1.1 中…...
智能井盖管理系统:城市窨井的井下“保镖”
随着城市化进程的加速,城市的生命线基础设施面临着越来越多的挑战。其中,旭华智能智能井盖传感器技术的发展为提升城市基础设施的安全性和管理效率提供了新的解决方案。它专门用于监控市政窨井、燃气井、供水井内的积水状况以及井盖状态,以增…...
vue3-环境变量-JavaScript-axio-基础使用-lzstring-字符串压缩-python
文章目录 1.Vue3环境变量1.1.简介1.2.全局变量的引用1.3.package.json文件 2.axio2.1.promise2.2.安装2.3.配置2.3.1.全局 axios 默认值2.3.2.响应信息格式 2.4.Axios的拦截器2.4.1.请求拦截器2.4.2.响应拦截器2.4.3.移除拦截器2.4.4.自定义实例添加拦截器 3.lz-string3.1.java…...
ubuntu下载docker依赖包
Ubuntu下载docker依赖包 公司对外客户一直偏向对安全性要求较高,因此在外部署服务得时候,安装docker是一件极为重要得事情,之前得服务器得系统是centos7。在上一家公司的时候,已经把docker所需得rpm包已经集成打包好了。并且d…...
java面向对象进阶进阶篇--《JDK8,JDK9接口中新增的方法、接口的应用、适配器设计模式》
个人主页→VON 收录专栏→java从入门到起飞 接口→接口和接口与抽象类综合案例 一、JDK8接口中新增的方法 在JDK 8中,接口新增了几个重要的特性和方法,其中最显著的是默认方法(Default Methods)和静态方法(Static Met…...
15.2 zookeeper java client
15.2 zookeeper java client 1. Zookeeper官方1.1 依赖1.2 Zookeeper客户端连接测试1.3***************************************************************************************1. Zookeeper官方 1.1 依赖 <!-- 集成方式一:官方集成zookeeper依赖 --><dependenc…...
素材管理太繁琐?有这一个就够了!
引言: 在创意行业中,素材管理一直是设计师们的痛点。从灵感的捕捉到作品的完成,每一步都离不开素材的积累与整理。然而,传统的素材管理方式往往繁琐且效率低下,让人头疼不已。今天,我要介绍的这款智能素材管…...
KubeSphere 部署向量数据库 Milvus 实战指南
作者:运维有术星主 Milvus 是一个为通用人工智能(GenAI)应用而构建的开源向量数据库。它以卓越的性能和灵活性,提供了一个强大的平台,用于存储、搜索和管理大规模的向量数据。Milvus 能够执行高速搜索,并以…...
前端canvas——贝塞尔曲线
曲线之美,不在于曲线本身,而在于用的人。 所以就有了这期贝塞尔曲线。 新规矩,先上个GIT。 效果图 开局一张图,代码全靠编。 代码 画骨 先想着怎么画一个心形吧,等你想好了,就知道怎么画了。 首先就还…...
Elasticsearch模糊查询之Wildcard
{“wildcard” : { “LPR.keyword” : { “wildcard” : “${Keyword}”} }},你的示例中使用了 wildcard 查询,它适用于模糊搜索,允许使用通配符(* 和 ?)来匹配字段值。你使用了 keyword 子字段来确保精确匹配,这是一…...
【人工智能】穿越科技迷雾:解锁人工智能、机器学习与深度学习的奥秘之旅
文章目录 前言一、人工智能1. 人工智能概述a.人工智能、机器学习和深度学习b.人工智能发展必备三要素c.小案例 2.人工智能发展历程a.人工智能的起源b.发展历程 3.人工智能的主要分支 二、机器学习1.机器学习工作流程a.什么是机器学习b.机器学习工作流程c.特征工程 2.机器学习算…...
Nginx服务 rewrite、proxy_pass 用rewrite去除URL中的特定参数
Nginx 是一个高性能的开源反向代理服务器,可以用于处理跨域请求、负载均衡和缓存等功能。在本文中,我们将介绍如何使用 Nginx 配置文件来实现反向代理。 我们可以实现跨域请求的处理,同时保护用户的隐私和安全。此外,Nginx 还…...
RocketMQ事务消息机制原理
RocketMQ工作流程 在RocketMQ当中,当消息的生产者将消息生产完成之后,并不会直接将生产好的消息直接投递给消费者,而是先将消息投递个中间的服务,通过这个服务来协调RocketMQ中生产者与消费者之间的消费速度。 那么生产者是如何…...
【C++】选择结构- 嵌套if语句
嵌套if语句的语法格式: if(条件1) { if(条件1满足后判断是否满足此条件) {条件2满足后执行的操作} else {条件2不满足执行的操作} } 下面是一个实例 #include<iostream> using namespace std;int main4() {/*提示用户输入一个高考分数,根据分…...
scrapy解决管道阻塞问题采用threadpool库线程池+twisted同步语法异步编程
实现方法:process_item和download任务函数像下面编写即可,其他管道像往常一样写法 import time import threadpool import random from twisted.internet import deferclass VideoPipeline:def __init__(self):self.pool threadpool.ThreadPool(10) # …...
Axure RP:打造动态交互的大屏可视化设计利器
Axure大屏可视化是指使用Axure RP这款原型设计工具来创建具有视觉冲击力和数据展示功能的大屏幕界面。Axure以其强大的交互设计和丰富的组件库,成为了实现大屏可视化的重要工具之一。以下是对Axure大屏可视化的详细阐述: 一、Axure在大屏可视化中的优势 …...
“八股文”在实际工作中是助力、阻力还是空谈
目录 1.概述 1.1.对实际工作的助力 1.2.存在的问题 2.“八股文”对招聘过程的影响 2.1.“八股文”在筛选候选人时的作用 2.2.面试中的比重及其合理性 2.3.如何平衡“八股文”与实际编程能力的考察 3.“八股文”在日常工作中的实用价值 3.1.在团队协作环境中进行有效沟…...
项目开发:@ControllerAdvice注解的基本应用
目录 简介基本用法全局异常处理全局拦截器全局数据绑定 注解参数1.value(): String[]2.basePackages(): String[]3.basePackageClasses(): Class<?>[]4.assignableTypes(): Class<?>[]5.annotations(): Class<? extends Annotation>[] 三.注解组成总结 简…...
Jmeter三种方式获取数组中多个数据并将其当做下个接口参数入参【附带JSON提取器和CSV格式化】
目录 一、传统方式-JOSN提取器获取接口返回值 1、接口调用获取返回值 2、添加JSON提取器 3、调试程序查看结果 4、添加循环控制器 5、设置count计数器 6、添加请求 7、执行请求 二、CSV参数化 1、将结果写入后置处理程序 2、设置循环处理器 3、添加CSV文件 4、设置…...
C++入门基础:C++中的循环语句
循环语句是编程语言中用来重复执行一段代码直到满足特定条件的一种控制结构。它们对于处理需要重复任务的场景非常有用,比如遍历数组、累加数值、重复执行某项操作直到满足条件等。 但是在使用循环语句的时候需要注意下哈,有时候一不小心会构成死循环或者…...