Sorting algorithm - Bubble sort

Bubble sort是最簡單好懂的排序方式，雖然頂多被拿來當範例教學而非實用，但對於新手入門瞭解排序演算法是個不錯的開始，排序的觀念很簡單，就是「兩相比較，前者大於後者時互換位置」(以排序成遞增為例)。

Bubble sort algorithm

圖解是很好的說明方式，因為由左而右兩相比較的關係，每做完一次循環，都可以將未排序數列中的最大值移到最右側，但是相對較小值則只會往左一格，造成如圖中「龜兔賽跑」的情形，這就是為什麼Bubble sort利於理解卻不夠有效率的原因。

<Complexity performance>

• Worst case: O(n²)
• Best case: O(n)
• Average case: O(n²)

---

<參考資料來源>
Wikipedia - Bubble sort