插入排序

实现原理

插入排序的原理是:我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。
插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
整体流程如下图所示:

动图演示

Insertion Sort

示例代码

插入排序也比较简单,对应的 Go 实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package main

import "fmt"

func insertionSort(nums []int) []int {
if len(nums) <= 1 {
return nums
}

for i := 0; i < len(nums); i++ {
// 每次从未排序区间取一个数据 value
value := nums[i]
// 在已排序区间找到插入位置
j := i - 1
for ; j >= 0; j-- {
// 如果比 value 大后移
if nums[j] > value {
nums[j+1] = nums[j]
} else {
break
}
}
// 插入数据 value
nums[j+1] = value
}

return nums
}

func main() {
nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
nums = insertionSort(nums)
fmt.Println(nums)
}

运行上述代码,打印结果如下:

性能分析

我们来看下插入排序的性能和稳定性:

  • 插入排序需要两个嵌套的循环,时间复杂度是$O(n^2)$;
  • 没有额外的存储空间,是原地排序算法;
  • 不涉及相等元素位置交换,是稳定的排序算法。

插入排序的时间复杂度和冒泡排序一样,也不是很理想,但是插入排序不涉及数据交换,从更细粒度来区分,性能要略优于冒泡排序。


插入排序
https://www.chendujin.com/posts/96555fb2.html
作者
托马斯
发布于
2022年4月22日
许可协议