插入排序(Insertion Sort),一般也被称为直接插入排序。
插入排序的核心思想是局部有序。
其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中,最终得到的序列就是已经排序好的数据
例如:一个无序数组 3、1、7、5、2、4、9、6,将其升序的结果则如下:
一开始有序表中无数据,直接插入3
从第二个数开始,插入元素1,然后和有序表中记录3比较,1<3,所以插入到记录 3 的左侧
- 向有序表插入记录 7 时,同有序表中记录 3 进行比较,3<7,所以插入到记录 3 的右侧
- 向有序表中插入记录 5 时,同有序表中记录 7 进行比较,5<7,同时 5>3,所以插入到 3 和 7 中间
- 照此规律,依次将无序表中的记录 4,9 和 6插入到有序表中
在插入排序中,当待排序数组是有序时,是最优的情况,只需 当前数 跟 前一个数 比较一下就可以了,这时一共需要比较 N- 1
次,时间复杂度为 O(n)
最坏的情况是待排序数组是逆序的,此时需要比较次数最多,总次数记为:1 + 2 + 3 + … + (n-1) = n*(n-1)/2 =1/2 n² - 1/2n
,所以,插入排序最坏情况下的时间复杂度为 O(n²)
而选择排序无论多少个数据,时间复杂度都为 O(n²)
通过上面了解,可以看到插入排序是一种稳定的排序方式
# 1. 插入排序实现
将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置
如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面
function insertionSort(arr) {
const len = arr.length;
let preIndex, current;
//外层循环 从下标为1的元素开始循环
for (let i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
//内层循环 获取i位置的元素,和前面的数据进行比较
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 2. 应用场景
插入排序时间复杂度是 O(n²),适用于数据量不大,算法稳定性要求高,且数据局部或整体有序的数列排序