淺解前端必須掌握的算法（一）：冒泡排序

前言

雖然前端面試中很少會考到算法類的題目，但是你去大廠面試的時候就知道了，對基本算法的掌握對于從事計算機科學技術的我們來說，還是必不可少的，每天花上 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<len-1; i++) {
    for (j=0; j<len-i-1; j++) {
      if (arr[j] > 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<len-1; i++) {
    noswap = true;
    for (j=0; j<len-i-1; j++) {
      if (arr[j] > 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²)

。

作者：程式猿何大叔

連結：https://juejin.im/post/5b2c51f46fb9a00e5d7986f6

來源：掘金

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。