Golang 實(shí)現(xiàn)插入排序的方法示例(2種)

再次研究了插入排序的概念：定義一個(gè)有序的數(shù)據(jù)序列a，將待排序的序列b中的數(shù)依次插入到a的合適位置，插入后仍然有序

總結(jié)其與冒泡、選擇的區(qū)別在于，內(nèi)部迭代的次數(shù)是逐漸增大的，二后兩者隨著排序進(jìn)行迭代次數(shù)逐漸減少

嘗試基于Go的實(shí)現(xiàn)：

插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：

• 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序 取出下一個(gè)元素
• 在已經(jīng)排序的元素序列中從后向前掃描
• 如果該元素（已排序）大于新元素，將該元素移到下一位置
• 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置 將新元素插入到該位置后
• 將新元素插入到該位置后
• 重復(fù)步驟2~5

兩種實(shí)現(xiàn)方式：1，新建切片； 2，在原切片中進(jìn)行元素交換

方式一：新建切片

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

/**
插入排序法：取原數(shù)組old中第一個(gè)值作為新數(shù)組中的第一個(gè)值，然后遍歷old，將每個(gè)元素按照條件插入到新數(shù)組中
時(shí)間復(fù)雜度：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()函數(shù)中的第二個(gè)參數(shù)為切片的指針，不然打印出來的的新數(shù)組為空

原因：雖然切片是指針傳遞，這是指切片內(nèi)的各個(gè)元素是指針傳遞，對(duì)于切片本身仍是值傳遞

證明：

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

打印結(jié)果：

0xc0420e4680
0xc0420e46b0
0xc0420e46c0
0xc0420e46b0
[zhang si]

引申：Go 語言里的引用類型有如下幾個(gè)：切片、映射、通道、接口和函數(shù)類型。當(dāng)聲明上述類型的變量時(shí)，創(chuàng)建的變量被稱作標(biāo)頭（header）值。從技術(shù)細(xì)節(jié)上說，字符串也是一種引用類型。每個(gè)引用類型創(chuàng)建的標(biāo)頭值是包含一個(gè)指向底層數(shù)據(jù)結(jié)構(gòu)的指針。因?yàn)闃?biāo)頭值是為復(fù)制而設(shè)計(jì)的，所以永遠(yuǎn)不需要共享一個(gè)引用類型的值。標(biāo)頭值里包含一個(gè)指針，因此通過復(fù)制來傳遞一個(gè)引用類型的值的副本，本質(zhì)上就是在共享底層數(shù)據(jù)結(jié)構(gòu)

結(jié)論：不會(huì)對(duì)切片進(jìn)行增加或刪除操作時(shí)（也就是長(zhǎng)度不會(huì)改變），切片作為參數(shù)在函數(shù)間的傳遞不需使用指針。但是如果切片需要進(jìn)行增加或刪除元素的操作，并且原函數(shù)需要調(diào)用更新后的切片，那么在原函數(shù)調(diào)用其它函數(shù)時(shí)，就需要用切片的指針作為參數(shù)。

方式二：在原切片中進(jìn)行元素交換

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

由于不用創(chuàng)建新的切片，不用進(jìn)行插入操作，只需要交換操作，所以要較方法一速度快些

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。