直接插入排序

直接插入排序原理：https://www.jianshu.com/p/d31cb21342ed

go代码实现：

package main

import (
    "fmt"
)

/*
插入排序：
1、从第一个元素开始，该元素可以认为已经被排序；
2、取出下一个元素，在已经排序的元素序列中从后向前扫描；
3、如果该元素（已排序）大于新元素，将该元素移到下一位置；
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5、将新元素插入到该位置后；
6、重复步骤2~5。
*/
func insertion_sort(a []int) {
    for i := 0; i < len(a); i++ {
        index := a[i]
        j := i - 1
        for ;j >= 0 && a[j] > index; j-- {
            a[j+1] = a[j]
        }
        a[j+1] = index
    }
}
func main() {
    a := []int{1,3,5,2,1}
    fmt.Println(a)
    insertion_sort(a)
    fmt.Println(a)
}

运行结果：

GOROOT=C:\Go #gosetup
GOPATH=F:\goPath #gosetup
C:\Go\bin\go.exe build -o C:\Users\windows10\AppData\Local\Temp\___go_build_insertion_sort_go.exe F:/code/test/insertion_sort/insertion_sort.go #gosetup
C:\Users\windows10\AppData\Local\Temp\___go_build_insertion_sort_go.exe #gosetup
[1 3 5 2 1]
[1 1 2 3 5]

Process finished with exit code 0