(1)Go实现选择、冒泡、插入排序

（1）选择排序（Selection sort）
工作原理是每一次从待排序的 [数据元素] 中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完

// 选择排序
func SelectionSort(s []int)[]int {
    length := len(s)
    for i := 0; i < length; i++ {
        // 寻找 [i : length] 区间里的最小值
        for j := i + 1; j < length; j++ {
            if s[i] > s[j] {
                s[i], s[j] = s[j], s[i]
            }
        }
    }
    return s
}

（2）冒泡排序（Bubble Sort）
工作原理是重复走访过要排序 [数据元素]，依次比较两个相邻的元素，（如从小到大）左边的元素大于右边的元素，则两者交换位置，之后比较右，右右边元素，依此重复，直到没有相邻元素需要交换，即排序完成。
这个名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

// 冒泡排序: 基本版本,从0开始,对比相邻2个元素,如果,大的放右边,之后对比右,和右右..依次往复
func BubbleSort(arrs []int) {
    length := len(arrs)
    for i := 0; i < length; i++ {
        for j := 1; j < length-i; j++ {
            if arrs[j] < arrs[j-1] {
                arrs[j], arrs[j-1] = arrs[j-1], arrs[j]
            }
        }
    }
}

（3）插入排序（Insertion sort）
工作原理是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
如从小到大排序 arrs[ 1，6，0，5，9] 为例：
1）将第1个元素看成排好序的有序序列，对比第arrs[0]，arrs[1]元素大小，若arrs[0]>arrs[1]，则两者交换位置，这里1<6，不用改变位置
2）前两个元素为有序序列，对比arrs[1], arrs[2]元素大小，0<6,改变位置-->[1,0,6,5,9]，再对比arrs[0],arrs[1]元素大小，这里0<1，交换位置-->[0,1,6,5,9]，后续的依此类推

// 插入排序1
func InsertionSort1(s []int) []int {
    length := len(s)
    for i := 1; i < length; i++ {
        // 寻找元素s[i]合适的插入位置
        for j := i; j > 0 && s[j] < s[j-1]; j-- {
            // 如果 s [j] >= s [j-1],说明 s[j]比s[j-1]以及之前的元素都大，
            // s[i]已经到了合适的位置可以提前结束循环
            s[j], s[j-1] = s[j-1], s[j]
        }
    }
    return s
}

插入排序的改善，改善思路是减少元素位置交换的次数，每次将要插入的元素值s[i]取出来，
比如buf:=s[i]对比buf,s[i-1]大小，若s[i-1]大，则令s[i]=s[s-1]，之后对比buf,s[i-2]大小，
若s[i-2]大，则令s[i-1]=s[i-2],直到buf>s[j],则说明s[j+1]位置为当前buf应当插入的位置，
执行s[n+1]=buf，实现如下：
// 插入排序2：改善版本
func InsertionSort2(s []int) []int {
    length := len(s)
    for i := 1; i < length; i++ {
        buf := s[i]
        j := 0
        for j = i; j > 0 && s[j-1] > buf; j-- {
            s[j] = s[j-1]
        }
        s[j] = buf
    }
    return s
}

性能测试
func main() {
    const count = 10
    nums2 := [count]int{}
    for i := 0; i < count; i++ {
        nums2[i] = rand.Intn(count)
    }

    fmt.Println("初始数据:", nums2)
    fmt.Println("----")
    for i := 0; i < 4; i++ {
        nums3 := nums2
        nums := nums3[:]
        t := time.Now()
        switch i {
        case 0:
            fmt.Println("选择排序", sort.SelectionSort(nums))
        case 1:
            fmt.Println("冒泡排序", sort.BubbleSort(nums))
        case 2:
            fmt.Println("插入排序1", sort.InsertionSort1(nums))
        case 3:
            fmt.Println("插入排序2", sort.InsertionSort2(nums))
        }
        fmt.Println("花费时间:", t.Sub(time.Now()))
        fmt.Println("----")
    }
}
测试结果：
初始数据: [1 7 7 9 1 8 5 0 6 0]
----
选择排序 [0 0 1 1 5 6 7 7 8 9]
花费时间: -5.53µs
----
冒泡排序 [0 0 1 1 5 6 7 7 8 9]
花费时间: -4.029µs
----
插入排序1 [0 0 1 1 5 6 7 7 8 9]
花费时间: -3.45µs
----
插入排序2 [0 0 1 1 5 6 7 7 8 9]
花费时间: -3.423µs

加大数量，继续测试
    const count = 10000
    nums2 := [count]int{}
    for i := 0; i < count; i++ {
        nums2[i] = rand.Intn(count)
    }

    fmt.Println("----")
    for i := 0; i < 4; i++ {
        nums3 := nums2
        nums := nums3[:]
        t := time.Now()
        switch i {
        case 0:
            sort.SelectionSort(nums)
            fmt.Printf("选择排序")
        case 1:
            //sort.BubbleSort(nums)
            fmt.Printf("冒泡排序")
        case 2:
            sort.InsertionSort1(nums)
            fmt.Printf("插入排序1")
        case 3:
            sort.InsertionSort2(nums)
            fmt.Printf("插入排序2")
        }
        fmt.Println("花费时间:", t.Sub(time.Now()))
        fmt.Println("----")
    }
测试结果：
选择排序花费时间: -167.830966ms
----
冒泡排序花费时间: -3.931µs
----
插入排序1花费时间: -30.558033ms
----
插入排序2花费时间: -25.94522ms
以上3种排序，时间复杂度都为O(n^2)
结论：插入排序的性能明显优于选择排序和冒泡排序，另外对内存地址修改较少的插入排序
速度相对快一点。
另外由于插入排序可以提前结束内循环，在排序相对有序的数据时，插入排序有很大的优势，
时间复杂度接近O(n)