再次研究了插入排序的概念：定義一個有序的數據序列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] 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]
}
}
}
}
由于不用創建新的切片，不用進行插入操作，只需要交換操作，所以要較方法一速度快些
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:- Go語言排序算法之插入排序與生成隨機數詳解
- Go語言實現冒泡排序、選擇排序、快速排序及插入排序的方法
