算法：插入排序

算法：插入排序

算法演进

将数组看作两个数组，前一部分为有序数组（已排好序），后一部分为无序数组（待排序）。

以[10, 20, 5, 0]数组为例。

[10 20 5 0]
第 1 次排序 [10 20 5 0]
第 2 次排序 [5 10 20 0]
第 3 次排序 [0 5 10 20]

第一步

将[10]看作有序数组，[20, 5, 0]看作无序数组，无序数组的元素20与它的前一位（有序数组的末位元素）比较。若比前一位大则将20看作有序数组的末位元素；若比前一位小则与20的前一位的前一位比较，以此类推。

第二步

将[10, 20]看作有序数组，[5, 0]看作无序数组，进行类似第一步的比较操作。

第三步

将[5, 10, 20]看作有序数组，[0]看作无序数组，进行类似第一步的比较操作，将0插入到有序数组的最前面。

func InsertSortEvolution() {
    arr := []int{10, 20, 5, 0}

    // 将 [10] 看作有序数组，[20, 5, 0] 看作无序数组
    insertVal := arr[1]
    j := 1 - 1
    for j >= 0 && insertVal < arr[j] {
        arr[j+1] = arr[j]
        j--
    }
    arr[j+1] = insertVal
    log.Println("第1次排序", arr)

    // 将 [10, 20] 看作有序数组，[5, 0] 看作无序数组
    insertVal = arr[2]
    j = 2 - 1
    for j >= 0 && insertVal < arr[j] {
        arr[j+1] = arr[j]
        j--
    }
    arr[j+1] = insertVal
    log.Println(arr)
    log.Println("第2次排序", arr)

    // 将 [5, 10, 20] 看作有序数组，[0] 看作无序数组
    insertVal = arr[3]
    j = 3 - 1
    for j >= 0 && insertVal < arr[j] {
        arr[j+1] = arr[j]
        j--
    }
    arr[j+1] = insertVal
    log.Println(arr)
    log.Println("第3次排序", arr)
}

插入排序代码

arr := []int{10, 20, 5, 0}
log.Println(arr)
for i := 1; i < len(arr); i++ {
    j := i
    insertVal := arr[i] // 一定要使用临时变量接收，如果在循环中用 arr[i]获取，其实值已经变为移动后的值了
    // 当前元素与前一个元素相比
    for j-1 >= 0 && insertVal < arr[j-1] {
        arr[j] = arr[j-1]
        j--
    }
    arr[j] = insertVal
    log.Println("第", i, "次排序", arr)
}