前端基础算法

对于前端初学者而言,这样的一个功能你做出来了那就很好,慢慢的,我们的工作年限越来越长,如果我们还继续那样做,这样,迟早会淘汰。这个时候,就需要对你的项目进行优化。之前讲到过对于react项目的优化。这更多是针对于单页应用的优化,避免首页时间加载过长,打包文件加载过大,是针对于打包后文件来说的。这篇文章主要是针对于算法相关的代码进行优化,从而是程序的运行速度更快,已达到程序的优化。

算法更多的是针对于数据的增删改查,或许你认为前端涉及不到,如果这样想,那你就错了。前端可能用的不多,但不会涉及不到,同时,了解算法,那么对于以后的职业道路也会有所帮助。

二分查找法

二分查找在进行查找有序数组中某一项数据的时候非常有用,可以加快程序的运行速度,尤其是在具有大量数据的时候。

二分查找的原理是从数组的中间开始查找,如果被查找对象刚好就是中间这一项,那直接退出查找。如果被查找对象大于中间,那么所需要的对象是在中间-最后这一区间,所以有针对于这一区间再次进行二分。如此下去,找到所需要的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 二分查找
* @param {Array} list 待查找的有序数组
* @param {Number} item 待查找的数据
*/
function binarySearch(list, item){
// 如果list不是数组返回list
if (!Array.isArray(list)) return list
// 定义查找的起始位置
let low = 0;
let high = list.length - 1;

while (low <= high) {
// 定义中间的位置
let mid = Math.floor((low + high) / 2)
let midValue = list[mid]

if ( midValue == item ) return mid

if (midValue < item){
low = mid + 1
}

if (midValue > item){
high = mid - 1
}
}

return -1
}

最后来看看一个具体的效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const arr = []
for (let i = 0; i < 10000; i++) {
arr.push(i)
}
const need = 6734
let res;

console.time("for")
for (let i = 0; i < arr.length; i++) {
const ele = arr[i];
if( ele === need ) {
res = i
break
}
}
console.log(res);
console.timeEnd("for")

console.time("binarySearch")
res = binarySearch(arr, need)
console.log(res)
console.timeEnd("binarySearch")

可以看到很明显二分查找比普通的循环遍历快了许多。

可视化链接

https://algorithm-visualizer.org/branch-and-bound/binary-search

时间复杂度 O(\log n)

选择排序

上面讲到的二分查找虽然性能很好,当时有一个必要的条件就是这个list需要是一个有序数组,否则使用二分查找则是不成立的。所以,对于一个无序的数组,我们首先就是需要把它重新排序。选择排序就是其中一种。

选择排序的原理是从数组中选出一个最大(小)的数,放在另一个数组的开始,然后从剩余数组中继续选择最大(小)的数进行操作,如此重复,直到数组重组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 选择排序
function selectSort(list){
if (!Array.isArray(list)) return list

// 定义一个数组存放排序后的数组
const arr = [];

for (let i = list.length - 1; i >= 0; i--) {
const smallestIndex = findSmallest(list)
arr.push(list.splice(smallestIndex, 1)[0])
}

return arr
}

// 寻找最小的数
function findSmallest(list){
let smallest = list[0]
let smallestIndex = 0

for (let i = 0; i < list.length; i++) {
const ele = list[i];
if (ele < smallest) {
smallest = ele
smallestIndex = i
}
}
return smallestIndex
}
文章作者: 踏浪
文章链接: https://www.lyt007.cn/技术/前端基础算法.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 踏浪 - 前端技术分享
支付宝
微信打赏