前言
随着前端的飞速发展，前端业务开发给前端工程师提出了更高的要求，因而算法题也越来越高频次的出现在前端面试中。有很多的小伙伴找胡哥苦诉，在前端实际开发中（除了涉及游戏开发方面），算法使用有很多吗？大厂的面试是故意要自我标榜下吗？其实不然，考核算法还是相当有必要的，来来来，让胡哥给你拯救世界的理由，哦，不，是考核算法的理由。
为啥要考算法？
- 算法是通用技能，包含了诸多逻辑和相关的技术点，优秀的算法方案会体现出优秀的逻辑思维和和解决问题的能力。
- 扎实的算法有助于我们在解决复杂问题时获得更优的解决方案。
算法的实现基于不同的语言有不同的形式，对于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)
