Bubble Sort

　　依然是一種最簡單基本、容易理解的排序演算法。
基本概念：由左而右，依序兩兩前後記錄相比較，若前者>後者，則swap(前，後)，每一回合後，當時之最大值會升至最高位置。
若某回合完全沒有進行swap，則表示sort完成。

Principle

通常不會使用額外的數列記錄已排序好的數列。

不需將數列分成兩部分，只需兩兩做比較再swap。

Complexity

Time complexity:

Best case:O(n)。
情況為input data恰巧由小->大呈現。
(只需n-1次比較，且無swap發生)
Worst case:O(n²)。
情況為input data恰巧由大->小呈現。
(若n筆，則需swap n-1, n-2,...,1次 =>n(n-1)/2次)
Average case:O(n²)。
T(n)=T(n-1)+c*n,T(1)=0
T(n)=c*(n+2)(n-1)/2 => O(n²)。

Space complexity:
　　O(1)。

運算流程

比較相鄰的元素，若前面的元素比較大就進行交換。
重複進行1往最右端，最後一個元素將會是最大值。
重複以上動作1->2每次比較到上一輪的最後一個元素。
重複以上動作1->2->3直到沒有swap發生。

Stable vs. Unstable sort

Stable。
ex: Input:...,5,...,5*,...
因5 !> 5* 所以不會swap。

簡易code

BubbleSort(list,n)
{ for i=1 to (n-1) do
　{ f=0; //f表有無發生swap，0:無，1:有
　　for j=1 to (n-i) do
　　{
　　　if list[j]>list[j+1] then
　　　　{ swap(list[j],list[j+1])
　　　　　　f=1;
　　　　}
　　 if(f==0) then exit;　　
　　}
　}
}