阅读量:0
目录
前言
在实际场景中，选择合适的排序算法对于提高程序的效率和性能至关重要，本节课主要讲解"插入排序"的适用场景及代码实现。
插入排序
插入排序(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 main import ( "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. 内存限制
由于插入排序是原地排序，它不需要额外的存储空间(除了几个变量外)，这对于内存受限的环境非常有利
尽管插入排序在大数据集上表现不佳，但在上述场景下，它仍然是一种非常有用且简单的排序算法。
