前端需要掌握的算法之——插入排序（Insertion sort）

[jnoodle]

Bad programmers worry about the code. Good programmers worry about data structures and their relationships. —— Linus Torvalds

插入排序（Insertion sort） 就是每一步都将一个待排序的元素，按照它的大小，插入到已经排序的元素中的适当位置，一直重复，直到全部待排序的元素插入完毕。

具体步骤如下（假设是从小到大排序）：

1. 将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列
2. 从后向前依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置

插入排序算法复杂度是：O(n²)。

• 最坏时间复杂度 O(n²)
• 最优时间复杂度 O(n)
• 平均时间复杂度 O(n²)
• 最坏空间复杂度 总共 O(n)，需要辅助空间 O(1)

上代码：

// 随机生成一个乱序数组
let arr = Array.from(new Array(10), () => ~~(Math.random() * 100))

console.log('Source array is [ %s ]\n', arr.join(', '))

// 插入排序
function insertionSort(arr) {
    const len = arr.length
    let step = 1;
    // i 为未排序序列 index，j 为已排序序列 index，起始 arr[0] 作为已排序序列，所以 i 从 1 开始
    for (let i = 1; i < len; i++) {
        // 选取 arr[i] 作为待排序元素，从右到左依次与左侧的已排序序列比较
        let insertItem = arr[i]
        for (let j = i - 1; j >= -1; j--) {
            // j === -1 代表已经比较到第一个元素，都没有发现更小的，则需要插入到最前端
            // 这里采用直接插入的方式，也可以选择依次交换的方式
            if (j === -1 || arr[j] < insertItem) {
                if (j + 1 !== i) {
                    // 把元素从 i 插入到 j + 1 位置
                    arr.splice(j + 1, 0, insertItem); // 插入元素
                    arr.splice(i + 1, 1); // 删除元素
                }
                console.log('Step %d: [ %s ] (insert %s from %d to %d, %s)', step++, arr.join(', '), insertItem, i, j + 1, j + 1 !== i ? 'Moved' : 'No move')
                break;
            }
        }
    }
    console.log('\nSorted array is [ %s ]', arr.join(', '))
}

insertionSort(arr)

结果：

Source array is [ 38, 12, 34, 65, 10, 47, 51, 55, 27, 11 ]

Step 1: [ 12, 38, 34, 65, 10, 47, 51, 55, 27, 11 ] (insert 12 from 1 to 0, Moved)
Step 2: [ 12, 34, 38, 65, 10, 47, 51, 55, 27, 11 ] (insert 34 from 2 to 1, Moved)
Step 3: [ 12, 34, 38, 65, 10, 47, 51, 55, 27, 11 ] (insert 65 from 3 to 3, No move)
Step 4: [ 10, 12, 34, 38, 65, 47, 51, 55, 27, 11 ] (insert 10 from 4 to 0, Moved)
Step 5: [ 10, 12, 34, 38, 47, 65, 51, 55, 27, 11 ] (insert 47 from 5 to 4, Moved)
Step 6: [ 10, 12, 34, 38, 47, 51, 65, 55, 27, 11 ] (insert 51 from 6 to 5, Moved)
Step 7: [ 10, 12, 34, 38, 47, 51, 55, 65, 27, 11 ] (insert 55 from 7 to 6, Moved)
Step 8: [ 10, 12, 27, 34, 38, 47, 51, 55, 65, 11 ] (insert 27 from 8 to 2, Moved)
Step 9: [ 10, 11, 12, 27, 34, 38, 47, 51, 55, 65 ] (insert 11 from 9 to 1, Moved)

Sorted array is [ 10, 11, 12, 27, 34, 38, 47, 51, 55, 65 ]

注意：这里采用直接插入的方式，也可以选择依次交换的方式，代码相对会简单一点。