登录
首页 >  Golang >  Go教程

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

来源:脚本之家

时间:2022-12-30 21:50:02 132浏览 收藏

知识点掌握了,还需要不断练习才能熟练运用。下面golang学习网给大家带来一个Golang开发实战,手把手教大家学习《Go语言数据结构之插入排序示例详解》,在实现功能的过程中也带大家重新温习相关知识点,温故而知新,回头看看说不定又有不一样的感悟!

插入排序

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

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

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

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

动画演示

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

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

总结

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

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

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

以上就是《Go语言数据结构之插入排序示例详解》的详细内容,更多关于golang的资料请关注golang学习网公众号!

声明:本文转载于:脚本之家 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表