fbpx

氣泡排序法 Bubble Sort

其實氣泡排序法算是最容易理解的排序法,也常作為初學者入門學習的演算法,相信經過前兩篇較為複雜的快速排序法、合併排序法後,可以快速理解氣泡排序法的內容與實作方法。

氣泡排序法定義

氣泡排序法的過程會從陣列最左邊開始將元素兩兩比較,每一輪都會把最大的數值移動到陣列末端,這個行為就好像氣泡不斷從底部冒出一樣,因此被稱作氣泡排序法。

氣泡排序法的實作步驟如下:

  1. 比較相鄰的兩個元素,若前面的元素較大就進行交換。
  2. 重複進行1的動作直到最後面,最後一個元素將會是最大值。
  3. 重複進行1,2的動作,每次比較到上一輪的最後一個元素。
  4. 重複進行以上動作直到沒有元素需要比較。

把文章一開始示意圖的第一部份拆過來看,一開始把陣列的第一個元素跟第二個元素比較,如果前面的元素比後者大,就將兩元素交換,如果前者元素比後者小,就不做調整。這邊因為 5 比 1 大,因此將兩元素交換,接著看第二個元素跟第三個元素,依此類推,最後會將陣列中最大的元素放到陣列最後頭,接著重複以上步驟,直到所有元素都經過排列,排序才結束。

時間複雜度

因為實作會使用到雙重迴圈,因此平均時間複雜度為 O(n²)

平均: O(n^2)

空間複雜度

因為沒有額外建立其他資料結構,因此空間複雜度為:

O(1)

程式碼範例

function bubbleSort(array) {    const length = array.length;    for (let i = 0; i < length; i++) {        for (let j = 0; j < length; j++) {            if(array[j] > array[j+1]) {                let temp = array[j]                array[j] = array[j+1];                array[j+1] = temp;            }        }    }}

這邊使用了雙層的迴圈,內層迴圈實作了文章上面提到的步驟 1、步驟 2,外層迴圈則實作步驟3 ,確保所有元素都能經過排序。

結語

因為學會快速排序法與合併排序法後,氣泡排序法其實相較起來簡單許多,因此本篇文章主要目的為記住氣泡排序法的定義,並沒有花太多時間在講解程式範例。

不過透過這篇文章,我們可以了解演算法沒有所謂絕對的優劣好壞,即使氣泡排序法時間複雜度為 O(n²),較合併排序法與快速排序法都沒有效率,但它的空間複雜度 O(1) 卻比合併排序法的 O(n)、快速排序法的 O(log(n)) 更有效率,因此演算法的使用主要還是依照使用時機與情況來做取捨,也許這個狀況適合使用時間複雜度低的演算法 A,另一個狀況卻適合使用較不佔記憶體空間的演算法 B 喔!

下篇一次講解 選擇排序 (Selection Sort) 與插入排序 (Insertion Sort) 兩個同樣屬於較為簡單的排序法,並把排序的主題做個完結,準備進到下個主題囉!


好文轉自作者莫力全《JS 學資料結構與演算法 (排序篇) — 氣泡排序法 Bubble Sort》如果妳喜歡他的文章,歡迎回到原文看更多:)