插入排序
Golang 实现
package main
import "fmt"
func main() {
arr2 := [] int16{6, 5, 3, 1, 8, 7, 2, 4}
sortByInsertSort := insertSort(arr2)
fmt.Println(sortByInsertSort)
}
func insertSort(arr []int16) []int16 {
length := len(arr)
for i := 1; i < length; i++ {
if arr[i] < arr[i-1] {
j := 0 //more wide
tag := arr[i] //sign
for j = i - 1; j >= 0 && arr[j] > tag; j-- { // members back to move
arr[j+1] = arr[j]
}
arr[j+1] = tag //insert
}
}
return arr
}
新建一个xxx.go的文件,复制代码,go run xxx.go
图解
Complexity 复杂度
Name | Best | Average | Worst | Memory | Stable | Comments |
---|---|---|---|---|---|---|
Insertion sort | n | n2 | n2 | 1 | Yes |