计数排序
来源:dev.to
时间:2024-07-21 08:27:45 416浏览 收藏
Golang小白一枚,正在不断学习积累知识,现将学习到的知识记录一下,也是将我的所得分享给大家!而今天这篇文章《计数排序》带大家来了解一下##content_title##,希望对大家的知识积累有所帮助,从而弥补自己的不足,助力实战开发!
这是用于整数数组或以整数为键的结构的排序算法。当整数范围与输入大小相同时特别有用。
主要思想是确定整数出现的频率,并用它来确定排序顺序。
举个例子:假设我们得到数组 {1,3,1,2}.
首先确定此输入的整数范围,最大值和最小值,1 和 3。
接下来创建一个数组,称之为 counts 数组,即整数范围的大小+1,因此在本例中为 3 (3-1+1)。
迭代输入数组,增加相应条目的计数。给定输入值的计数将放置在 counts[value - min] 处。对于给定的输入,counts[0] 将保存值 1 的计数。
这会产生计数数组:{2,1,1}
现在确定累计计数,本质上是 counts[i] = counts[i-1]+counts[i]。
这会产生累积计数数组:{2,3,4}
为排序后的输入创建输出数组。
现在,以相反的顺序迭代输入。
在每一步中,检索输入数组中值的累积计数。该值将被放置在与检索到的计数 - 1 相对应的输出数组索引处。然后递减累积计数值。
在第一步中,检索值 2 且累积计数为 3。该值应放置在输出中的索引 2 (3-1) 处。
在下一次迭代中,值1,累计计数2;所以这个“1”被放置在输出的索引 1 (2-1) 处。
继续,数值3,累计次数4;将其放置在输出的索引 3 处。
最后第二次值为1,累计计数为1(因为第一次看到计数就减1了);所以这个'1'被放置在输出的索引0处。
,了解反向迭代如何保留相等元素的顺序,从而使排序“稳定”
排序后的数组为 {1,1,2,3}
func CountingSort(in []int) []int { // find the min/max values min := slices.Min(in) max := slices.Max(in) // create the count array counts := make([]int, max-min+1) for _, v := range in { counts[v-min]++ } // determine cumulative counts for i := 1; i < len(counts); i++ { counts[i] = counts[i-1] + counts[i] } // create the output array out := make([]int, len(in)) for i := range in { v := in[len(in)-1-i] out[counts[v-min]-1] = v counts[v-min]-- } return out }
可以提高效率吗?请在下面留下您的意见和建议。
谢谢!
这篇文章以及本系列所有文章的代码可以在这里找到
文中关于的知识介绍,希望对你的学习有所帮助!若是受益匪浅,那就动动鼠标收藏这篇《计数排序》文章吧,也可关注golang学习网公众号了解相关技术文章。
-
505 收藏
-
502 收藏
-
501 收藏
-
501 收藏
-
501 收藏
-
171 收藏
-
471 收藏
-
491 收藏
-
381 收藏
-
253 收藏
-
362 收藏
-
363 收藏
-
229 收藏
-
297 收藏
-
220 收藏
-
142 收藏
-
283 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 立即学习 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 立即学习 508次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 立即学习 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 立即学习 484次学习