前端经典算法-冒泡算法(ES6版)及优化

为啥要考算法？

1. 算法是通用技能，包含了诸多逻辑和相关的技术点，优秀的算法方案会体现出优秀的逻辑思维和和解决问题的能力。
2. 扎实的算法有助于我们在解决复杂问题时获得更优的解决方案。

算法的实现基于不同的语言有不同的形式，对于JavaScript来说，算法的实现也有很多种不同的方式，本文基于JS最新的ES6语法来实现，各位小伙伴在领略算法魅力的同时也能掌握到ES6的语法。

一、冒泡算法

冒泡算法，闻名而知其意，使用类似于水中气泡自下而上逐渐变大的原理（这个原理要是有不清楚的童鞋，可咨询物理老师压强问题，看看老师会不会把你打出shi来...）来对数组进行排序。

排序规则

1. 每次循环，比较当前位置项与下一个位置项的大小，如果当前项 > 后一项，则交换两者的位置。每次循环比较都能选择出一个最大值，放在末尾，剩余待筛选的比较项就减少一项。
2. 如果数组存在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语法结构

1. 函数定义时形参：[...arr]解构赋值和扩展运算符，为不影响原数组，使用该方式接收原数组元素
2. [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)

有想了解更多的朋友可以去https://www.jianshu.com/u/7e7ee1652bbf 看一下我前面的一些文章。