DIV CSS 佈局教程網

JavaScript 冒泡排序及雙向冒泡排序實作
編輯:JavaScript基礎知識     

冒泡排序是最容易寫 also 最容易理解 的排序演算法:反覆比較相鄰元素,把較大的往後推,每一輪都能把當前最大值「浮」到末端,因此得名。本文在基本版本之外,再實現雙向冒泡(雞尾酒排序)與一個變體,並說明它們的改善思路。

一、基本冒泡排序

這裡用「交換」而非建立暫存陣列的方式進行,透過加減法避免額外變數(實務上建議直接用暫存變數,可讀性更好也更不易溢位):

var ls = [98, 13, 6, 25, 38, 36, 30, 44, 38, 80, 61, 28, 47, 34, 95, 18, 85, 58,
          89, 85, 42, 61, 74, 35, 13, 14, 80, 7, 10, 44, 10, 47, 13, 11, 52, 25,
          24, 48, 34, 12, 88, 80, 33, 8, 80, 45, 64, 52, 79, 77];

for (var i = 0; i < ls.length; i++) {
  for (var j = i + 1; j < ls.length; j++) {
    if (ls[i] > ls[j]) {
      ls[i] = ls[i] + ls[j];
      ls[j] = ls[i] - ls[j];
      ls[i] = ls[i] - ls[j];
    }
  }
}

這個寫法讓每一輪確定第 i 個位置的最小值,本質上與選擇排序更接近;若要體現經典冒泡的「相鄰比較」,內層應寫成 for (var j = 0; j < ls.length - 1 - i; j++) 並比較 ls[j] 與 ls[j+1]。

二、雙向冒泡排序

基本冒泡每一輪只能固定一個元素,若最小的元素恰好在末尾,它需要走完整趟才能到位,效率很差。雙向冒泡(又稱雞尾酒排序)的改進是:一輪之內先由左向右把最大值推到右端,再由右向左把最小值推回左端,兩端同時收斂。

var ls = [6, 13, 98, 25, 38, 36, 30, 44, 38, 80, 61, 28, 47, 34, 95, 18, 85, 58,
          89, 85, 42, 61, 74, 35, 13, 14, 80, 7, 10, 44, 10, 47, 13, 11, 52, 25,
          24, 48, 34, 12, 88, 80, 33, 8, 80, 45, 64, 52, 79, 77];

var lent = ls.length;

for (var i = 0; i < ls.length; i++) {
  for (var j = i + 1; j < ls.length - i; j++) {
    // 由右向左:把較小的往左推
    if (ls[lent - 1 - i] < ls[lent - j]) {
      ls[lent - 1 - i] = ls[lent - 1 - i] + ls[lent - j];
      ls[lent - j] = ls[lent - 1 - i] - ls[lent - j];
      ls[lent - 1 - i] = ls[lent - 1 - i] - ls[lent - j];
    }

    // 由左向右:把較大的往右推
    if (ls[i] > ls[j]) {
      ls[i] = ls[i] + ls[j];
      ls[j] = ls[i] - ls[j];
      ls[i] = ls[i] - ls[j];
    }
  }
}

注意上述程式碼中的 lent 是刻意保留的變數名,實際使用時建議改為更具描述性的 len。核心改進在於內層迴圈的邊界 ls.length - i:每完成一輪,右側已就位的元素就不再參與比較。

三、雙向冒泡的變體

以下版本嘗試在每一輪中同時處理「當前最小值」「當前最大值」「倒數第二小」「順數第二大」四個位置,以減少迴圈趟數:

var ls = [98, 13, 6, 25, 38, 36, 30, 44, 38, 80, 61, 28, 47, 34, 95, 18, 85, 58,
          89, 85, 42, 61, 74, 35, 13, 14, 80, 7, 10, 44, 10, 47, 13, 11, 52, 25,
          24, 48, 34, 12, 88, 80, 33, 8, 80, 45, 64, 52, 79, 77];

var lent = ls.length;

for (var i = 0; i < ls.length; i++) {
  for (var j = i * 2; j < ls.length - 2 * i; j++) {

    // 保持內層第一個數為本輪最小
    if (ls[i * 2] > ls[j + 1]) {
      ls[i * 2] = ls[i * 2] + ls[j + 1];
      ls[j + 1] = ls[i * 2] - ls[j + 1];
      ls[i * 2] = ls[i * 2] - ls[j + 1];
    }

    // 保持內層倒數第一個數為本輪最大
    if (ls[lent - i * 2 - 1] < ls[lent - j - 1]) {
      ls[lent - i * 2 - 1] = ls[lent - i * 2 - 1] + ls[lent - j - 1];
      ls[lent - j - 1] = ls[lent - i * 2 - 1] - ls[lent - j - 1];
      ls[lent - i * 2 - 1] = ls[lent - i * 2 - 1] - ls[lent - j - 1];
    }

    // 倒數第二個位置
    if (ls[lent - 2 - i * 2] < ls[lent - j - 1]) {
      ls[lent - 2 - i * 2] = ls[lent - 2 - i * 2] + ls[lent - j - 1];
      ls[lent - j - 1] = ls[lent - 2 - i * 2] - ls[lent - j - 1];
      ls[lent - 2 - i * 2] = ls[lent - 2 - i * 2] - ls[lent - j - 1];
    }

    // 順數第二個位置
    if (ls[i * 2 + 1] > ls[j + 1]) {
      ls[i * 2 + 1] = ls[i * 2 + 1] + ls[j + 1];
      ls[j + 1] = ls[i * 2 + 1] - ls[j + 1];
      ls[i * 2 + 1] = ls[i * 2 + 1] - ls[j + 1];
    }
  }
}

四、評價與建議

冒泡排序的平均與最壞時間複雜度都是 O(n²),空間複雜度 O(1),且是穩定排序。雙向冒泡在「最小元素位於尾端」這類特定分布上能少走一半路程,實測通常比單向版本快,但數量級並未改變。

上面三段程式碼刻意示範了以加減法交換、以及多重索引運算的寫法,這是為了貼近原始思路;在實際專案中更推薦:

  • 用暫存變數交換,避免大數相加造成溢位或精度損失。
  • 加入「本輪是否發生交換」的旗標,若某輪完全沒有交換即可提前結束——這對接近有序的資料效果顯著。
  • 把索引計算簡化為 left/right 兩個邊界變數,並在每輪結束時向內收縮,程式碼會比 lent - i * 2 - 1 這類表達式清楚得多。

需要處理大量資料時,請直接改用快速排序、合併排序或堆排序等 O(n log n) 的演算法;冒泡排序的價值主要在教學與極小規模資料。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved