写点什么

跟着动画学 Go 数据结构之插入排序

作者:宇宙之一粟
  • 2021 年 12 月 17 日
  • 本文字数:825 字

    阅读完需:约 3 分钟

跟着动画学Go数据结构之插入排序

插入排序

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


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


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

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

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


Go 代码实现

package mainimport "fmt"func main() {    arrays := []int{6, 2, 5, 8, 9, 3, 1}    length := len(arrays)    insertionSort(arrays, length)    for i := 0; i < length; i++ {        fmt.Printf("%d ", arrays[i])    }}func insertionSort(unsorted []int, length int) {    for i := 0; i < length; i++ {        var insertElement = unsorted[i]        var insertPosition = i        for j := insertPosition - 1; j >= 0; j-- {            if insertElement < unsorted[j] {                unsorted[j+1] = unsorted[j]                insertPosition--            }        }        unsorted[insertPosition] = insertElement    }}
复制代码


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

总结

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


时间复杂度:算法的最坏时间复杂度为 ,如果输入的序列已经预排序,则时间复杂度最优情况为d 是反转的次数。


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


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


文章中数据结构可视化工具:​​https://visualgo.net/zh​

发布于: 21 小时前阅读数: 9
用户头像

宇宙古今无有穷期,一生不过须臾,当思奋争 2020.05.07 加入

混迹于江湖,江湖却没有我的影子 热爱技术,专注于后端全栈,轻易不换岗 拒绝内卷,工作于软件工程师,弹性不加班 热衷分享,执着于阅读写作,佛系不水文 各大平台同名 CSDN、51CTO、掘金、知乎、公众号、简书。。。

评论

发布
暂无评论
跟着动画学Go数据结构之插入排序