介绍

插入排序是一种简单直观的排序算法，它的基本思想是将数组分为已排序部分和未排序部分，逐步将未排序部分的元素插入到已排序部分的正确位置。

插入排序的具体步骤如下：

从数组的第二个元素开始，将其作为当前元素。
将当前元素与已排序部分的元素进行比较，从右到左逐个比较，直到找到合适的插入位置。
将当前元素插入到找到的插入位置，同时将已排序部分中的元素向右移动一个位置。
重复步骤 2 和 3，直到所有元素都被插入到已排序部分。

代码实现

package main

import "fmt"

func insertSort(a []int) {
    for i := 0; i < len(a); i++ {
        for j := i; j > 0; j-- {
            if a[j] < a[j-1] {
                a[j], a[j-1] = a[j-1], a[j]
            }
        }
        fmt.Println(a)
    }
    fmt.Println(a)
}

func main() {
    insertSort([]int{5, 3, 1, 4, 2, 6})
}

[5 3 1 4 2 6]
[3 5 1 4 2 6]
[1 3 5 4 2 6]
[1 3 4 5 2 6]
[1 2 3 4 5 6]
[1 2 3 4 5 6]

[1 2 3 4 5 6]

代码解释

• 变量 i 是外层循环的索引，它用于指示当前要插入的元素的位置。外层循环从数组的第一个元素开始，逐步遍历到最后一个元素。在每一次迭代中，i 指示了当前待插入元素的位置。

• 变量 j 是内层循环的索引，它用于比较当前待插入元素与已排序部分的元素。内层循环从 i 开始，逐步向前遍历已排序部分的元素，直到找到待插入元素的正确位置。在每一次迭代中，j 指示了当前比较的元素位置。

复杂度

• 最好情况下：当输入数组已经是有序的情况下，插入排序的时间复杂度可以达到最好情况。在这种情况下，内层循环不需要进行任何交换操作，仅进行比较操作，因此内层循环的执行次数为常量级。外层循环需要遍历整个数组，因此时间复杂度为 O(n)。所以在最好情况下，插入排序的时间复杂度是 O(n)。

• 最坏情况下：当输入数组是逆序排列时，插入排序的时间复杂度达到最坏情况。在这种情况下，每个新元素都必须与已排序部分的所有元素进行比较，并且需要进行交换操作，内层循环的执行次数达到最大。因此，内层循环的执行次数是 1+2+3+…+(n-1)，即等差数列求和，结果近似为 n^2/2。外层循环需要遍历整个数组，因此时间复杂度仍为 O(n)。所以在最坏情况下，插入排序的时间复杂度是 O(n^2)。

• 平均情况下：插入排序的平均情况时间复杂度也是 O(n^2)。这是因为在平均情况下，每个新元素需要与已排序部分的一半元素进行比较，内层循环的执行次数大致为 n^2/4。虽然平均情况下比最坏情况要好，但仍保持二次时间复杂度。

• 插入排序的空间复杂度是 O(1)。这是因为在排序过程中，只使用了常量级的额外空间来存储少量的临时变量，与输入规模无关。

插入排序的时间复杂度与输入数组的初始顺序有很大关系。当输入数组已经是有序或接近有序时，插入排序的性能会较好。但当输入数组是逆序排列或随机排列时，插入排序的性能会较差。