使用Golang怎么实现一个插入排序算法？相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。
插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序 取出下一个元素
在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后
将新元素插入到该位置后
重复步骤2~5
两种实现方式：1，新建切片； 2，在原切片中进行元素交换
方式一：新建切片
计算
安全
数据库
网络和加速
企业服务
package main
import "fmt"
func main() {
arr := []int{1, 0, 5, 7, 8, 5, 3, 6, 9, 2, 54, 33, 66}
newArr := []int{}
insertionSort(arr, &newArr)
fmt.Println(newArr)
}
/**
插入排序法：取原数组old中第一个值作为新数组中的第一个值，然后遍历old，将每个元素按照条件插入到新数组中
时间复杂度：O（n^2）
*/
func insertionSort(old []int, new *[]int) {
if len(*new) == len(old) {
return
}
current := len(*new)
*new = append(*new, old[current])
sort(*new)
insertionSort(old, new)
}
func sort(arr []int) {
for i := len(arr) - 1; i > 0; i-- {
if arr[i] < arr[i-1] {
arr[i], arr[i-1] = arr[i-1], arr[i]
}
}
}注意：insertionSort()函数中的第二个参数为切片的指针，不然打印出来的的新数组为空
原因：虽然切片是指针传递，这是指切片内的各个元素是指针传递，对于切片本身仍是值传递
证明：
package test
import (
"fmt"
"testing"
)
func TestSlice(t *testing.T) {
slice1 := []string{"zhang", "san"}
fmt.Printf("%p\n", &slice1)
fmt.Printf("%p\n", &slice1[1])
modify(slice1)
fmt.Println(slice1)
}
func modify(data []string) {
fmt.Printf("%p\n", &data)
fmt.Printf("%p\n", &data[1])
data[1] = "si"
}打印结果：
0xc0420e4680
0xc0420e46b0
0xc0420e46c0
0xc0420e46b0
[zhang si]
引申：Go 语言里的引用类型有如下几个：切片、映射、通道、接口和函数类型。当声明上述类型的变量时，创建的变量被称作标头（header）值。从技术细节上说，字符串也是一种引用类型。每个引用类型创建的标头值是包含一个指向底层数据结构的指针。因为标头值是为复制而设计的，所以永远不需要共享一个引用类型的值。标头值里包含一个指针，因此通过复制来传递一个引用类型的值的副本，本质上就是在共享底层数据结构
结论：不会对切片进行增加或删除操作时（也就是长度不会改变），切片作为参数在函数间的传递不需使用指针。但是如果切片需要进行增加或删除元素的操作，并且原函数需要调用更新后的切片，那么在原函数调用其它函数时，就需要用切片的指针作为参数。
方式二：在原切片中进行元素交换
func method2(arr []int) {
if len(arr) < 2 {
return
}
for i := 1; i < len(arr); i++ {
for j := i; j > 0; j-- {
if arr[j] < arr[j-1] {
arr[j], arr[j-1] = arr[j-1], arr[j]
}
}
}
}看完上述内容，你们掌握使用Golang怎么实现一个插入排序算法的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注亿速云行业资讯频道，感谢各位的阅读！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
