介绍

插入式排序属于内部排序法（内存中），是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

插入排序法思想

插入排序（Insertion Sorting）的基本思想是：把n个待排序的无素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表无素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

有一部分数据始终是有序的，这就是比冒泡排序、选择排序效率高的原因
image.png

代码

  1. // 插入排序
  3. package main
  5. import "fmt"
  7. func insertSort(arr *[5]int) {
  9.     for i := 1; i < len(arr); i++ {
  10.         insertVal := arr[i]  // 要进行插入的值
  11.         insertIndex := i - 1 // 插入位置的前一个下标
  13.         // 从大到小
  14.         for insertIndex >= 0 && arr[insertIndex] < insertVal {
  15.             arr[insertIndex+1] = arr[insertIndex] // 数据后移
  16.             insertIndex--
  17.         }
  19.         // 插入
  20.         if insertIndex+1 != i {
  21.             arr[insertIndex+1] = insertVal
  22.         }
  23.         fmt.Printf("第 %v 次插入排序：%v \n", i, arr)
  24.     }
  26.     /* insertVal := arr[1]
  27.     insertIndex := 1 - 1 // 插入位置的前一个下标
  29.     // 从大到小
  30.     for insertIndex >= 0 && arr[insertIndex] < insertVal {
  31.         arr[insertIndex+1] = arr[insertIndex] // 数据后移
  32.         insertIndex--
  33.     }
  35.     // 插入
  36.     if insertIndex+1 != 1 {
  37.         arr[insertIndex+1] = insertVal
  38.     }
  39.     fmt.Printf("第 %v 次插入排序：%v \n", 1, arr)
  41.     insertVal = arr[2]
  42.     insertIndex = 2 - 1
  44.     // 从大到小
  45.     for insertIndex >= 0 && arr[insertIndex] < insertVal {
  46.         arr[insertIndex+1] = arr[insertIndex]
  47.         insertIndex--
  48.     }
  50.     // 插入
  51.     if insertIndex+1 != 2 {
  52.         arr[insertIndex+1] = insertVal
  53.     }
  54.     fmt.Printf("第 %v 次插入排序：%v \n", 2, arr)
  56.     insertVal = arr[3]
  57.     insertIndex = 3 - 1
  59.     // 从大到小
  60.     for insertIndex >= 0 && arr[insertIndex] < insertVal {
  61.         arr[insertIndex+1] = arr[insertIndex]
  62.         insertIndex--
  63.     }
  65.     // 插入
  66.     if insertIndex+1 != 3 {
  67.         arr[insertIndex+1] = insertVal
  68.     }
  69.     fmt.Printf("第 %v 次插入排序：%v \n", 3, arr)
  71.     insertVal = arr[4]
  72.     insertIndex = 4 - 1
  74.     // 从大到小
  75.     for insertIndex >= 0 && arr[insertIndex] < insertVal {
  76.         arr[insertIndex+1] = arr[insertIndex]
  77.         insertIndex--
  78.     }
  80.     // 插入
  81.     if insertIndex+1 != 4 {
  82.         arr[insertIndex+1] = insertVal
  83.     }
  84.     fmt.Printf("第 %v 次插入排序：%v \n", 4, arr) */
  85. }
  87. func main() {
  88.     arr := [5]int{23, 0, 12, 56, 34}
  89.     fmt.Println("arr = ", arr)
  90.     insertSort(&arr)
  91.     fmt.Println("排序后：", arr)
  92. }