說明

插入排序，同樣無需申請(qǐng)新的內(nèi)存地址。相對(duì)選擇排序算法運(yùn)行速度稍快。

邏輯

從第二個(gè)元素開始與前一個(gè)元素大小相比較，若小于上一個(gè)元素，則與之交換位置，位移后，并繼續(xù)與上一個(gè)元素比較。若大于等于上一個(gè)元素則此元素位置不再變動(dòng)，繼續(xù)對(duì)比下一個(gè)元素。

代碼

package arithmetic

import (
    "math"
)

//InterfaceSort 排序接口 選擇排序 插入排序
type InterfaceSort interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

//SortInsertion 插入排序
func SortInsertion(slice InterfaceSort) {

    if slice.Len() < 2 {
        return
    }

    for i := 1; i < slice.Len(); i++ {
        var j = i - 1
        for ; j >= 0; j-- {
            if slice.Less(j+1, j) { // slice[j+1] < slice[j]
                slice.Swap(j+1, j)
            } else {
                break
            }
        }
    }
}

代碼說明

面向?qū)ο髮?shí)現(xiàn)，結(jié)構(gòu)體實(shí)現(xiàn)相關(guān)接口即可調(diào)用該函數(shù)。

排序后的結(jié)果直接通過參數(shù)返回。

測(cè)試代碼

package  main

import (
    "AZframework/arithmetic"
    "fmt"
)

//IntSlice []int
type IntSlice []int

func (s IntSlice) Len() int           { return len(s) }
func (s IntSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }

func main() {
    var  sliceC = IntSlice{5, 5, 4, 3, 2, 1, 1}
    arithmetic.SortInsertion(sliceC)
        fmt.Printf("SortInsertion slice = %v \n", sliceC)
}

日志輸出

SortSelection slice = [1 1 2 3 4 5 5]