iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 17
1
Software Development

使用JavaScript學習資料結構與演算法系列 第 17

Day17-排序法系列(一)-氣泡排序法

氣泡排序法(Bubble Sort)是最容易理解和實作的排序演算法,但其時間複雜度在排序法當中算是最差的一個。主要觀念是從頭開始逐一比較相鄰兩筆資料,將較大值往後移動位置,直到最後,資料就會從最小值依序排到最大值。

此網頁有小動畫可以參考看看,非常淺顯易懂:
http://notepad.yehyeh.net/Content/Algorithm/Sort/Bubble/1.php

接著我們來實作吧!完成後會討論其時間複雜度~

最一開始我們建立一個bubbleSort()函式,接著在裡面寫兩個 for 迴圈,外層 for 是負責整個資料列的元素遍歷,確保所有資料都有做過排序,不過最後一個資料不需要作排序,因為當其他的資料都作好排序時,最後一個資料已經變成是排序順序中的最大或最小值了,因此 i 在 length - 1 的範圍作迴圈。

內層 for 則是將未排序的資料進行排序,因此 j 的範圍必須扣掉 已排序完成的資料數 (i) 並且減1

接著完成內層 for 的內容:
將兩個數作比較,前者較大就作交換,此時就完成bubble sort 了!

function bubbleSort(data) {
  const length = data.length;
  for (let i = 0; i < length - 1; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      let temp;
      // 前者較大就作交換
      if (data[j] > data[j + 1]) {
        temp = data[j + 1];
        data[j + 1] = data[j];
        data[j] = temp;
      }
      console.log(data);
    }
  }
}

bubbleSort([1, 234, -5, 78, -182, 45]);

透過內層 for 內的console.log(data);可以看到排序過程:

時間複雜度:

  • 最佳時間複雜度:Ο(n)
    當資料已經預先排序好的狀況
  • 平均時間複雜度:O(n^2)
    當目標資料排序正好和原本資料排序狀況相反,例如由大到小變成
  • 最差時間複雜度:O(n2)
    第n筆資料,平均比較(n-1)/2次

這次的完整程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day17-bubble-sort.js

明天將會介紹選擇排序 Selection Sort!


上一篇
Day16-演算法篇開始!介紹五個常用的演算法
下一篇
Day18-排序法系列(二)-選擇排序法
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言