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

    • 最好：O(n)
    • 最坏：O(n^2)

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

    • 只需要一个额外空间用于数据交换

    原理
    直接插入排序（Straight Insertion Sort） 基本操作是：将一个记录插入到已经排好序的有序数据中，从而得到一个新的、记录数增加1的有序表。

    实现
    把待排序序列视为两部分：

    1. 一部分为有序序列，通常在排序开始之时将序列中的第一个数据视为一个有序序列；
    2. 另一部分为待排序序列，有序序列之后的数据视为待排序序列。

    3. 在排序开始之时，从序列头部到尾部逐个选取数据，与有序序列中的数据，按照从尾部到头部的顺序逐个比较，直到找到合适的位置，将数据插入其中。

      1. // 插入排序，降序排序
      2. func InsertSort(slice []int) []int {
      3.  if len(slice) < 2 {
      4.      return slice
      5.  }
      7.  for i := 1; i < len(slice); i++ {
      8.      tmp := slice[i]
      9.      j := i - 1
      10.      for ; j >= 0; j-- {
      11.          if tmp >= slice[j] {
      12.              break
      13.          }
      15.          slice[j+1] = slice[j]
      16.      }
      17.      slice[j+1] = tmp
      18.  }
      20.  return slice
      21. }