前言

虽然前端面试中很少会考到算法类的题目，但是你去大厂面试的时候就知道了，对基本算法的掌握对于从事计算机科学技术的我们来说，还是必不可少的，每天花上 10 分钟，了解一下基本算法概念以及前端的实现方式。

另外，掌握了一些基本的算法实现，对于我们日常开发来说，也是如虎添翼，能让我们的 js 业务逻辑更趋高效和流畅。

算法介绍

冒泡排序很简单，就是数组中的相邻元素，两两比较，数值或者 Unicode 码小的元素往前排。

具体实现指导如下：

1. 比较相邻两个元素，若前一个比后一个大，则交换位置；
2. 第一轮结束之后，最后一个元素的值是最大的；
3. 接着开始第二轮，但是不用再比较最后一个元素了；
4. 第一轮除外，以后的每一轮都比前一轮少比较一次；

具体实现

var bubbleSort = function (arr){  var i, j, m;  var len = arr.length;  if (len <= 1) {    return arr;  }  for (i=0; i
    
      arr[j+1]) {        m = arr[j];        arr[j] = arr[j+1];        arr[j+1] = m;      }    }  }  return arr;};复制代码
    

算法改进

如果数组原本的顺序就是冒泡的，又或者仅做完前面寥寥几次就已经达到效果了，那后续的比较工作就显得有些多余了，如何对以上算法进行改进？

我们可以在某一轮的循环比较结束后，如果没有发生任何的元素交换，则可以认为该数组已经达到预期效果，不必再继续下一轮的比较了。

var bubbleSort = function (arr){  var start = +new Date();  var i, j, m, noswap;  var len = arr.length;  if (len <= 1) {    return arr;  }  for (i=0; i
    
      arr[j+1]) {        m = arr[j];        arr[j] = arr[j+1];        arr[j+1] = m;        noswap = false;      }    }    if (noswap) {      break;    }  }  // 当 arr 的长度越长，时间差越明显  console.log(+new Date() - start);  return arr;};复制代码
    

时间度复杂度分析

分析时间复杂度就按最坏的情况来，即待排序表是完全逆序的情况。 假设数组中共有 n 个元素，第一轮需要比较 n-1 次，第二轮需要比较 n-2 次，第三轮需要比较 n-3 次，以此类推，最后一轮需要比较 1 次，共比较 n-1 轮，所以是个等差数列，运用等差数列求和公式，能计算出如下时间复杂度：

因此总的时间复杂度为 O(n²)。