说明
插入排序，同样无需申请新的内存地址。相对选择排序算法运行速度稍快。
逻辑
从第二个元素开始与前一个元素大小相比较，若小于上一个元素，则与之交换位置，位移后，并继续与上一个元素比较。若大于等于上一个元素则此元素位置不再变动，继续对比下一个元素。
代码
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
}
}
}
}
代码说明
面向对象实现，结构体实现相关接口即可调用该函数。
排序后的结果直接通过参数返回。
测试代码
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]
