前端之算法（二）选择和插入排序

Augus

关注

发布于: 4 小时前

昨天也就是上一章我们聊了算法，以及比较经典的算法之冒泡排序，今天我们接下来要介绍一下选择排序和插入排序。

选择排序

选择排序 和冒泡排序一样，性能相较下不是很好，但是实现简单。

选择排序的思路

找到数组中的最小值，选中它并将其放置在第一位。
接着找到第二小的值，选中它并将其放置在第二位。
以此类推，执行 N - 1 轮，完成排序。

选择排序的动画

如上动画：

红色就是当前循环中的最小元素。
绿色就是当前循环所在的元素。
黄色就是排序好的元素。

**[选择排序动画](https://visualgo.net/zh/sorting)**

实现

代码如下：

Array.prototype.selectionSort = function () {    for (let i = 0; i < this.length - 1; i++) {        let indexMin = i        for (let j = i; j < this.length; j++) {            if (this[j] < this[indexMin]) {                indexMin = j            }        }        if (indexMin !== i) {            const temp = this[i]            this[i] = this[indexMin]            this[indexMin] = temp        }    }
}const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]arr.selectionSort()console.log(arr);// [   2,  3,  4,  5, 15, 19,  26, 27, 36, 38, 44, 46,  47, 48, 50]

复制代码

选择排序的时间复杂度

两个嵌套循环。
时间复杂度：O(n^2)。

插入排序

插入排序和冒泡排序，选择排序的复杂度是一样的，但是在排序一些小型数组的时候，插入排序是更胜一筹的了。

插入排序的思路

从第二个数开始往前比。
比它大就往后排。
以此类推进行到最后一个数。

插入排序的动画

**[插入排序动画](https://visualgo.net/zh/sorting)**

红色就是拿出来的元素。
绿色就是当前比对的元素。
黄色就是排序好的元素。

实现

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 = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]arr.insertionSort()console.log(arr);//[   2,  3,  4,  5, 15, 19,  26, 27, 36, 38, 44, 46,  47, 48, 50]

复制代码

插入排序的时间复杂度

两个嵌套循环。
时间复杂度：O(n^2)。

End~~

发布于: 4 小时前阅读数: 3

Augus

关注

爱瞎搞的软件开发工程师 2021.06.10 加入

某摸鱼集团

发布

暂无评论

创作场景

前端之算法（二）选择和插入排序

选择排序

选择排序的思路

选择排序的动画

实现

选择排序的时间复杂度

插入排序

插入排序的思路

插入排序的动画

实现

插入排序的时间复杂度

Augus

评论