Golang 实现插入排序的方法示例(2种)

在Golang实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《Golang 实现插入排序的方法示例(2种)》，聊聊插入排序，希望可以帮助到正在努力赚钱的你。

再次研究了插入排序的概念：定义一个有序的数据序列a，将待排序的序列b中的数依次插入到a的合适位置，插入后仍然有序

总结其与冒泡、选择的区别在于，内部迭代的次数是逐渐增大的，二后两者随着排序进行迭代次数逐渐减少

尝试基于Go的实现：

插入排序都采用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] 

<p>注意：insertionSort()函数中的第二个参数为切片的指针，不然打印出来的的新数组为空<br></p>
<p>原因：虽然切片是指针传递，这是指切片内的各个元素是指针传递，对于切片本身仍是值传递<br></p>
<p>证明：</p>

<pre class="brush:plain;">
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)  0; j-- {
  if arr[j] 

<p>由于不用创建新的切片，不用进行插入操作，只需要交换操作，所以要较方法一速度快些<br></p>
<p>理论要掌握，实操不能落！以上关于《Golang 实现插入排序的方法示例(2种)》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！</p>