前言
随着前端的飞速发展，前端业务开发给前端工程师提出了更高的要求，因而算法题也越来越高频次的出现在前端面试中。有很多的小伙伴找胡哥苦诉，在前端实际开发中（除了涉及游戏开发方面），算法使用有很多吗？大厂的面试是故意要自我标榜下吗？其实不然，考核算法还是相当有必要的，来来来，让胡哥给你拯救世界的理由，哦，不，是考核算法的理由。
为啥要考算法？
- 算法是通用技能，包含了诸多逻辑和相关的技术点，优秀的算法方案会体现出优秀的逻辑思维和和解决问题的能力。
- 扎实的算法有助于我们在解决复杂问题时获得更优的解决方案。
算法的实现基于不同的语言有不同的形式，对于JavaScript来说，算法的实现也有很多种不同的方式，本文基于JS最新的ES6语法来实现，各位小伙伴在领略算法魅力的同时也能掌握到ES6的语法。
一、冒泡算法
冒泡算法，闻名而知其意，使用类似于水中气泡自下而上逐渐变大的原理（这个原理要是有不清楚的童鞋，可咨询物理老师压强问题，看看老师会不会把你打出shi来…）来对数组进行排序。
排序规则
- 每次循环，比较当前位置项与下一个位置项的大小，如果当前项 > 后一项，则交换两者的位置。每次循环比较都能选择出一个最大值，放在末尾，剩余待筛选的比较项就减少一项。
- 如果数组存在n项，那么需要循环执行筛选的次数为n次
二、冒泡算法代码实现
function bubbleSort ([...arr]) {
for (let i = 0; i < arr.length; i++) {
// 第j和j+1项比较，故j的最大值为 = 最大长度 - 1 - 减去已经执行筛选的轮数i
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换数组元素的位置
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
}
}
}
return arr
}
let arr = [4, 3, 2, 1]
// 输出排序结果
let sortArr = bubbleSort(arr)
console.log(sortArr) // [1, 2, 3, 4]
// 输出原数组
console.log(arr) // [4, 3, 2, 1]
ES6语法结构
- 函数定义时形参：[…arr]
解构赋值和扩展运算符，为不影响原数组，使用该方式接收原数组元素 - [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]表达式
利用数组的解构赋值，交换两个位置的值 [a, b] = [b, a] 这样就不必借助于第三个变量来交换值
三、冒泡算法优化
使用上面的方式来实现冒泡算法排序时，时间平均复杂度为O(n^2)，那最坏的情况是什么呢？传入的数组完全是逆序的，即[4, 3, 2, 1]。但是如果传入的数组[1, 2, 3, 4]是完全正序的呢？如果还按该方式，那在执行时是性能浪费的，那该如何优化呢？
优化方案
如果数组是完全顺序的，那就说明在执行一次循环比较时，没有数组元素被交换位置，所以我们来设置一个标志flag，初始化为true，如果存在交换则赋值为false。在一次循环后，如果标志为true，则表示为无交换，已经是完全顺序了，则可以break停止外层循环了。下面我们来看下代码实现。
function bubbleSort ([...arr]) {
for (let i = 0; i < arr.length; i++) {
// 设置标记，标记当前轮筛选时是否有交换位置元素，默认为true，如果有交换设置为false
let flag = true
// 第j和j+1项比较，故j的最大值为 最大长度 - 1 - 减去已经执行筛选的轮数i
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换数组元素的位置
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
// 有交换位置，设置标记为false
flag = false
}
}
// 如果当前轮比较时没有交换位置，说明已经排序完成了
if (flag) {
break
}
}
return arr
}
let arr = [1, 2, 3, 4]
// 输出排序结果
let sortArr = bubbleSort(arr)
console.log(sortArr) // [1, 2, 3, 4]
// 输出原数组
console.log(arr) // [1, 2, 3, 4]
此时在完成排序时，只执行了一次循环，此刻的时间复杂度为O(n)
后记
以上就是胡哥今天给大家分享的内容，喜欢的小伙伴记得收藏、转发,关注“胡哥有话说”，学习前端不迷路。推荐给更多小伙伴呦，欢迎多多留言交流…
胡哥有话说，一个有技术，有情怀的胡哥！现任京东前端攻城狮一枚。
胡哥有话说，专注于大前端技术领域，分享前端系统架构，框架实现原理，最新最高效的技术实践！