前端之算法（一）

Augus

关注

发布于: 2 小时前

到此为止，我们的数据结构算是基本讲完了，接下来的篇章，想必不用我说，相信大家也猜到了，那不多哔哔，开启我们的新征程 —— 前端之算法。

算法

算法：一系列解决问题的清晰指令，就像是食谱一样。

数据结构与算法的关系

程序 = 数据结构 + 算法。
数据结构为算法提供服务，算法围绕数据结构操作。

排序和搜索

排序：把某个乱序的数组变成升序或者降序的数组。
搜索：找出数组中某个元素的下标。

JS 中的排序和搜索

JS 中的排序：数组的 sort 方法。
JS 中的搜索：数组的 indexOf 方法。

排序算法

冒泡排序
选择排序
插入排序
归并排序
快速排序

......

搜索算法

顺序搜索
二分搜索
......

介绍了这么多，也该开始我们的主题了，下面就让我来叨叨这个冒泡排序。

冒泡排序的思路

比较所有相邻的元素，如果第一个比第二个大，则交换它们。
一轮下来，可以保证最后一个数是最大的。
执行 n - 1 轮，就可以完成排序。

冒泡动画

实现

首先我们可以在 Array 的原型链上挂载一个 bubbleSort 方法。

Array.prototype.bubbleSort = function () {    console.log(this)}const arr = [5, 4, 3, 2, 1]arr.bubbleSort()// [ 5, 4, 3, 2, 1 ]

复制代码

这样数组就都可以调用这个方法了。
接下来然我们具体实现一下这个算法。

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

复制代码

冒泡排序的时间复杂度

两个嵌套循环
时间复杂度： O（n^2）

End ~~

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

Augus

关注

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

某摸鱼集团

发布

暂无评论

创作场景

前端之算法（一）

算法

数据结构与算法的关系

排序和搜索

JS 中的排序和搜索

排序算法

搜索算法

冒泡排序的思路

实现

冒泡排序的时间复杂度

Augus

评论