插入排序

什么是插入排序

插入排序会维护一个有序区,把元素一个个插入到有序的适当位置,直到所有元素有序为止。

假设有一组无序数组,插入排序会假定数组第一项属于有序区。

接着,它会从第二项开始,与前面的有序区的元素依次比较,根据数字大小在有序区找到合适的位置进行插入。

不断重复上述过程,最终会得到一个排序好的数组。

举个例子,假定待排序数组是[3, 5, 1, 4, 2]。

这些值将被插入排序算法按照下面的步骤进行排序。

  1. 假定数组第一项 3 已被排序,属于有序区,所以我们从数组第二个值 5 开始。3 比 5 小,所以 5 待在原位(数组的第二位)。此时,3 和 5 排序完毕,3和5属于有序区。

  2. 下一个待排序的值是 1(目前在数组的第三位)。5 比 1 大,所以 5 被 移至第三位去了。继续分析 1 是否应该被插入到第二位——1 比 3 大吗?不,所以 3 被移到第二位去了。因为 0 是第一个位置,所以 1 被插入第一位。1、3、5 三个数字已经排序,1,3和5属于有序区。

  3. 然后看下一个值待排序的值是4。4 比 5 小,所以 5 移动到索引 3 位置。4 比 3 大,所 以把 4 插入数组的位置 3 上。 此时,1,3,4,5属于有序区。

  4. 最后一个待插入的数字是 2(数组的位置 4)。5 比 2 大,所以 5 移动至索引 4。4 比 2 大, 所以 4 也得移动(位置 3)。3 也比 2 大,所以 3 还得移动。1 比 2 小,所以 2 插入到数组的第二个位置上。此时,1,2,3,4,5属于有序区。至此,数组已排序完成。

下面演示了图形化的插入排序过程:

插入排序

在排序小型数组时,此算法比选择排序和冒泡排序性能要好。

代码实现

插入排序代码并不复杂,所以实现起来也比较简单。

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
35
36
37
38
39
40
41
42
// 比较用的常量对象(保证代码优雅)
export const Compare = {
LESS_THAN: -1, // 如果第一个元素小于第二个元素,它就返回-1
BIGGER_THAN: 1, // 如果第一个元素大于第二个元素,它就返回1
EQUALS: 0 // 如果元素有相同的引用,它就返回 0
};
// 比较用的方法
export function defaultCompare(a, b) {
// 如果元素有相同的引用,它就返回 0
if (a === b) {
return Compare.EQUALS;
}
// 如果第一个元素小于第二个元素,它就返回-1,否之返回1
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
/**
* 插入排序
* 插入排序每次排一个数组项,以此方式构建最后的排序数组。
* @param {array} array 要进行排序的数组
* @param {function} compareFn // 比较用的方法,默认为defaultCompare
* @returns {array} 返回排序后的数组
*/
export const insertionSort = (array, compareFn = defaultCompare) => {
const { length } = array; // 声明一个名为length的变量,用来存储数组的长度
let temp;
// 主循环 迭代数组来给第 i 项找到正确的位置(假设下标0的元素已经排序好)
for (let i = 1; i < length; i++) {
let j = i; // 用 i 的值来初始化一个辅助变量
temp = array[i]; // 将其值存储在一个临时变量中(便于之后将其插入到正确的位置上)
// console.log('to be inserted ' + temp);
//次循环 找到正确的位置来插入项
while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) { // 只要变量j大于0(因为0下标已被假设排好序),并且数组前面的值比待比较的值大(也就是如果array[j - 1]比temp大)
// console.log('shift ' + array[j - 1]);
array[j] = array[j - 1]; // 我们就把这个值移到当前位置上
j--; // 并减小 j
}
// console.log('insert ' + temp);
array[j] = temp; // 最终,将该值插入到正确的位置上
}
// 返回排序后的数组
return array;
};

插入排序
https://sothx.com/2021/04/27/insertionSort/
作者
Sothx
发布于
2021年4月27日
许可协议