什么是插入排序？

原文链接：https://note.noxussj.top/?source=helloworld

什么是插入排序（insertionSort）？

在数组中从左到右依次取一个数出来，然后把它放到合适的位置。从思想上可以分为有序区和无序区，有序区在左边代表已经排列好的元素。

算法步骤

1. 默认左边第一个元素已经在有序区了
2. 在无序区取一个数出来（第二个元素）
3. 遍历有序区元素，把取出来的元素放到合适的位置上
4. 以此类推，执行 n - 1 轮（无序区为空时）
5. 完成排序

动画演示链接

https://visualgo.net/zh/sorting

基础案例

• 时间复杂度：O (n ^ 2)
• 空间复杂度：O (1)

1Array.prototype.insertionSort = function () {
2    for (let i = 1; i < this.length; i++) {
3        const temp = this[i]
4
5        let j = i
6
7        while (j > 0) {
8            if (this[j - 1] > temp) {
9                this[j] = this[j - 1]
10            } else {
11                break
12            }
13
14            j--
15        }
16
17        this[j] = temp
18    }
19}
20
21const arr = [5, 4, 3, 2, 1]
22
23arr.insertionSort() // [1, 2, 3, 4, 5]

因为存在两个嵌套循环，所以时间复杂度是 O (n ^ 2)，而时间复杂度是 O (1)，因为没有使用线性增长的数据结构。