JS-冒泡排序

從開始排序演算法之前，我們先創建一個方法用來生成原數組（指要被排序的數組）

function ArrayList() {
  var array = []; // {1}
  this.insert = function(item) {  // {2}
    array.push(item);
}
  this.toString = function() {  // {3}
    return array.join();
}

ArrayList是一個簡單的數據結構，它將項儲存在數組中(行 { 1 })。只需要向ArrayList里插入一個insert方法來向數據結構中添加元素(行{ 2 }），用array.push方法像數組中添加元素,最後用join方法來拼接數組中的所有元素來生成一個單一的字元串，方便在瀏覽器的控制台列印結果。

冒泡排序：時間複雜度為O(n^2)

比較任意兩個相鄰的項,如果第一個比第二個大,則交換它們,元素向上移動至正確的順序,就好像氣泡升至錶面上一樣。

冒泡排序是排序演算法中最簡單的，然而，從運行事件的角度來看，冒泡排序是最差的一個, 首先我們來講解一下思路吧:

function ArrayList() {
  var array = []
  this.insert = function(item) {
    array.push(item)
  }
  this.toString = function() {
    return array.join()
  }

  /**
   * 冒泡排序
   */
  this.bubbleSort = function() {
    var length = array.length;　　　　　　　　　　　　　　　　　　　　　　　　　//{1}
    for (var i = 0; i < length; i++) {   　　　　　　　　　　　　　　　　　　//{2}
      for (var j = 0; j < length - 1; j++) {　　　　　　　　　　　　　　　　//{3}　　　　　　
        if (array[j] > array[j + 1]) {　　　　　　　　　　　　　　　　　　　　//{4}
          [array[j], array[j + 1]] = [array[j + 1], array[j]];　　　　　//{5}
        }
      }
    }
  }
}

這裡為了讓大家熟悉面向對象開發,所以選用了在構造函數里擴展方法的形式來編寫代碼

首先如行{ 1 }, 先聲明一個名為length的變數,用來儲存數組的長度;

接著如行{ 2 }, 從數組的第一位迭代至最後一位,他控制了在數組中經過多少輪排序(應該是數組中每項都經過一輪,輪數和數組的長度一致);

然後如行{ 3 }, 內迴圈從第一位迭代至倒數第二位, 因為內迴圈就不用和自己比較了直接與下一項比較, 所以遍歷會少一位。

再如行{ 4 }, 內迴圈進行當前項與下一項的比較,如果當前項比下一項大,則交換它們 ( 如行{ 5 } )。

行{ 5 } 用到了ES6的解構賦值, 也可以封裝一個函數來實現交換數組中的元素

如下:

function swap(array, index1, index2) {
  var aux = array[index1];
  array[index2] = array[index1];
  array[index1] = aux;          
}

*改進:

比如: 當外迴圈i=0; 第一個元素經過內迴圈找到了自己的對應位置, 那麼i=1時, 就不必再去迴圈它了, 但上面的代碼, 內迴圈還是把所有的項都遍歷一遍, 顯然是需要改進的。

this.modifiedBubbleSort = function() {
    var length = array.length;　　　　　　　　　　　　　　　　　　　　　　　　　//{1}
    for (var i = 0; i < length; i++) {   　　　　　　　　　　　　　　　　　　 //{2}
      for (var j = 0; j < length - 1 - i; j++) {　　　　　　　　　　　　　　//{3}　　　　　　
        if (array[j] > array[j + 1]) {　　　　　　　　　　　　　　　　　　　　//{4}
          swap(array, j, j+1)　　　　　　　　　　　　　　　　　　　　　　　　　 //{5}
        }
      }
    }
  }

在行{ 3 }中, 我們把內迴圈遍歷的條件改了, 這樣內迴圈把外迴圈已經跑過的輪數去掉了, 就可以避免內迴圈中所有不必要的比較。

好了, 冒泡排序今天就介紹到這裡, 最好畫畫圖好好理解, 比較一下改進與改進之前的演算法, 加深理解。

有問題可以評論呦~