目录
前言
插入排序
代码示例
1. 算法包
2. 插入排序代码
3. 模拟程序
4. 运行程序
5. 从大到小排序
插入排序的思想
循环细节
外层循环
内层循环
循环次数测试
假如 10 条数据进行排序
假如 20 条数据进行排序
假如 30 条数据进行排序
假设 5000 条数据，对比 冒泡、选择、快速、堆、归并
插入排序的适用场景
1. 小规模数据
2. 基本有序的数据
3. 稳定排序需求
4. 内存限制
前言
在实际场景中，选择合适的算法>排序算法对于提高程序的效率和性能至关重要，本节课主要讲解"插入排序"的适用场景及代码实现。
插入排序
插入排序(Insertion Sort) 是一种简单直观的算法>排序算法，它的工作原理是通过构建有序列表，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序(即只需用到 O(1) 的额外空间的排序)，因而在从后向前扫描过程中，找到排序位置后，需要将已排序元素逐步向后挪动，为新元素提供插入空间。
代码示例
下面我们使用Go语言实现一个插入排序：
1. 算法包
创建一个 pkg/algorithm.go
touch pkg/algorithm.go(如果看过上节课的选择排序，则已存在该文件，我们就不需要再创建了)
2. 插入排序代码
打开 pkg/algorithm.go 文件，代码如下
从小到大 排序
package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
...// InsertionSort 插入排序
func InsertionSort(arr []int) {for i := 0; i < len(arr); i++ {key := arr[i]j := i - 1// 将arr[i]插入到arr[0...i-1]已排序的序列中for j >= 0 && arr[j] > key {arr[j+1] = arr[j] // 元素后移j = j - 1}arr[j+1] = key // 插入key}
}
3. 模拟程序
打开 main.go 文件，代码如下：
package mainimport ("demo/pkg""fmt"
)func main() {// 定义一个切片，这里我们模拟 10 个元素arr := []int{456, 29, 3268, 537, 133, 772, 90, 2, 108, 299}fmt.Println("Original data:", arr) // 先打印原始数据pkg.InsertionSort(arr) // 调用插入排序fmt.Println("New data: ", arr) // 后打印排序后的数据
}
4. 运行程序
go run main.go
能发现， Original data 后打印的数据，正是我们代码中定义的切片数据，顺序也是一致的。
New Data 后打印的数据，则是经过插入排序后的数据，是从小到大的。
5. 从大到小排序
如果需要 从大到小 排序也是可以的，在代码里，将两个元素比较的 大于符号 改成 小于符号 即可。
修改 pkg/algorithm.go 文件：
package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
...// InsertionSort 插入排序
func InsertionSort(arr []int) {for i := 0; i < len(arr); i++ {key := arr[i]j := i - 1// 将arr[i]插入到arr[0...i-1]已排序的序列中for j >= 0 && arr[j] < key {arr[j+1] = arr[j] // 元素后移j = j - 1}arr[j+1] = key // 插入key}
}
只需要一丁点的代码即可
从 package pkg 算第一行，上面示例中在第十六行代码中，我们将 ">" 改成了 "<" ，这样就变成了 从大到小排序了
插入排序的思想
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素列表中从后向前扫描
- 如果该元素(已排序)大于新元素，将该元素移到下一个位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤 2 到 5
循环细节
外层循环
在外层循环中， for i := 0; i < len(arr); i++ ，循环变量 i 从 1 开始，直到切片 arr 的最后一个元素的前一个位置。这是因为第一个元素 (arr[0]) 默认是已排序的，所以我们从第二个元素 (arr[1]) 开始考虑如何将它插入到前面已排序的序列中
内层循环
内层循环的目的是为了找到新元素 (key) 在已排序序列中的正确位置，并将这个位置及之后的所有元素向后移动一位，为新元素腾出空间。内层循环的条件是 j >= 0 && arr[j] > key ，这意味着只要 j 没有越界，并且 arr[j] (已排序序列中的一个元素) 大于新元素 key，就执行元素的移动操作 (arr[j+1] = arr[j]) 和 j 的递减操作 (j = j - 1)。
当内层循环结束时，j + 1 就是新元素 key 应该插入的位置，因为此时 j 指向的是第一个不大于 key 的元素，或者 j 已经是 -1 (即已排序序列为空，或者 key 应该插入到序列的最前面)。然后，将 key 插入到这个位置 (arr[j+1] = key)
通过外层循环的不断迭代，整个切片 arr 将逐渐变成有序状态
循环次数测试
按照上面示例进行测试：
假如 10 条数据进行排序
外层循环了 9 次
内层循环了 27 次
总计循环了 36 次
假如 20 条数据进行排序
外层循环了 19 次
内层循环了 99 次
总计循环了 118 次
假如 30 条数据进行排序
外层循环了 29 次
内层循环了 216 次
总计循环了 245 次
...
相对于 冒泡排序 和 选择排序，插入排序的循环次数减少了许多。
在平均和最坏的情况下，冒泡排序和选择排序都是 O(n^2)，而插入排序在数据基本有序时可以达到 O(n)。所以在小规模数据或基本有序的数据时，插入排序通常表现较好。
假设 5000 条数据，对比 冒泡、选择、快速、堆、归并
- 冒泡排序：循环次数 12,502,499 次
- 选择排序：循环次数 12,502,499 次
- 插入排序：循环次数 6,323,958 次
- 快速排序：循环次数 74,236 次
- 堆排序：循环次数 59,589 次
- 归并排序：循环次数 60,288 次
插入排序的适用场景
1. 小规模数据
由于插入排序在数据规模较小的情况下，其时间复杂度为 O( n^2 )，但常数因子较小，因此实际运行效率并不低，特别是数据量很小 (如少于10个元素) 时，其效率甚至可能超过更复杂的算法>排序算法
2. 基本有序的数据
对于已经部分排序的数组，插入排序的效率很高，因为它只需要少量的元素移动。例如，在数组末尾插入一个元素，或者数组已经是基本有序的情况下，插入排序的性能会非常好
3. 稳定排序需求
插入排序是一种稳定的算法>排序算法，即相等元素的相对位置在排序前后不会改变。这在某些需要保持数据原有顺序的场合非常有用
4. 内存限制
由于插入排序是原地排序，它不需要额外的存储空间(除了几个变量外)，这对于内存受限的环境非常有利
