插入排序—— 稳点！！！

动态图：

插入排序.gif

一、概念：

  原理：如果数组进行循环得到a，若a比a前面的一个数小(大)，则a就与前面数交换位置（相当于a向前面移动一位），若移动后a任然比前面一个数小(大)，则再向前移动一位……

二、基本操作（步骤）：

package main

import (
    "fmt"
    "math/rand"
    "time"
)

//1.
const (
    num      = 100000
    rangeNum = 100000
)

func main() {
    // fmt.Println(time.Now().Unix() , time.Now().UnixNano())
    randSeed := rand.New(rand.NewSource(time.Now().Unix() + time.Now().UnixNano()))
    var buf []int
    for i := 0; i < num; i++ {
        buf = append(buf, randSeed.Intn(rangeNum))
    }
    t := time.Now()
    // 插入排序
     charu(buf)
    fmt.Println(time.Since(t))  //求排序时间，与t := time.Now()配合
}
// 插入排序
func charu(buf []int) {
    times := 0
    for i := 1; i < len(buf); i++ {
        for j := i; j > 0; j-- {
            if buf[j] < buf[j-1] {
                times++
                tmp := buf[j-1]
                buf[j-1] = buf[j]
                buf[j] = tmp
            } else {
                break
            }
        }
    }
    fmt.Println("charu times: ", times)
}

三、时间复杂度与排序稳定性

时间复杂度： O(n^2)

平均时间复杂度：O(n²)
最好时间复杂度：O(n)
最坏时间复杂度：O(n²)
如果排序的数据是随机的，根据概率相同原则，平均⽐比较和移动的次数应为n²/4次，得出直接插
⼊入排序的时间复杂度为O(n²)。在同样的时间复杂度中直接插⼊入排序要优于选择排序和冒泡排序

空间复杂度：O(1)

稳定性：稳定