良许Linux教程网 干货合集 详解Go语言数据结构之插入排序

详解Go语言数据结构之插入排序

插入排序(InsertionSort),一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增 1 的有序。

插入排序

插入排序,英文名(insertion sort)是一种简单且有效的比较排序算法。

思想: 在每次迭代过程中算法随机地从输入序列中移除一个元素,并将改元素插入待排序序列的正确位置。重复该过程,直到所有输入元素都被选择一次,排序结束。

插入排序有点像小时候我们抓扑克牌的方式,如果抓起一张牌,我们放在手里;抓起第二张的时候,会跟手里的第一张牌进行比较,比手里的第一张牌小放在左边,否则,放在右边。

因此,对所有的牌重复这样的操作,所以每一次都是插入最正确的排序顺序,直到牌抓完为止。

Go语言数据结构之插入排序示例Go语言数据结构之插入排序示例

动画演示

假设我们需要从小到大进行排序,动画演示如下:

Go语言数据结构之插入排序示例Go语言数据结构之插入排序示例

Go 代码实现

package main
import "fmt"
func main() {
   arrays := []int{6, 2, 5, 8, 9, 3, 1}
   length := len(arrays)
   insertionSort(arrays, length)
   for i := 0; i "%d ", arrays[i])
   }
}
func insertionSort(unsorted []int, length int) {
   for i := 0; i for j := insertPosition - 1; j >= 0; j-- {
           if insertElement 

运行结果:

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\main.go"
1 2 3 5 6 8 9

总结

插入排序实现简单,理解也较容易,数据量较少时效率高,算法的实际运行效率优于选择排序和冒泡排序。

Go语言数据结构之插入排序示例Go语言数据结构之插入排序示例

空间复杂度: 空间复杂度为 O(1),即不输入借助其他的辅助空间。

稳定性: 插入排序是稳定的排序算法,在键值相同时它能够保持输入数据的原有次序。

以上就是良许教程网为各位朋友分享的Linu系统相关内容。想要了解更多Linux相关知识记得关注公众号“良许Linux”,或扫描下方二维码进行关注,更多干货等着你 !

137e00002230ad9f26e78-265x300
本文由 良许Linux教程网 发布,可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。
良许

作者: 良许

良许,世界500强企业Linux开发工程师,公众号【良许Linux】的作者,全网拥有超30W粉丝。个人标签:创业者,CSDN学院讲师,副业达人,流量玩家,摄影爱好者。
上一篇
下一篇

发表评论

联系我们

联系我们

公众号:良许Linux

在线咨询: QQ交谈

邮箱: yychuyu@163.com

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部