关于前端:插入排序算法

插入排序

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

什么是插入排序（insertionSort）？

在数组中从左到右顺次取一个数进去，而后把它放到适合的地位。从思维上能够分为有序区和无序区，有序区在右边代表曾经排列好的元素。

算法步骤

1. 默认右边第一个元素曾经在有序区了
2. 在无序区取一个数进去（第二个元素）
3. 遍历有序区元素，把取出来的元素放到适合的地位上
4. 以此类推，执行 n – 1 轮（无序区为空时）
5. 实现排序

动画演示链接

https://visualgo.net/zh/sorting

根底案例

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

    Array.prototype.insertionSort = function () {for (let i = 1; i < this.length; i++) {const temp = this[i]
    
            let j = i
    
            while (j > 0) {if (this[j - 1] > temp) {this[j] = this[j - 1]
                } else {break}
    
                j--
            }
    
            this[j] = temp
        }
    }
    
    const arr = [5, 4, 3, 2, 1]
    
    arr.insertionSort() // [1, 2, 3, 4, 5]

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

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