【DSA MOOC】起泡排序的原理及常數優化

根據學堂線上TsinghuaX: 30240184X 資料結構(2015秋)這門課的内容，對bubblesort做了一些總結。

1. bubblesort(起泡排序)，原理來自這樣一個觀察規律：若序列有序，則任意一對相鄰元素順序。其逆否命題為：若存在相鄰元素逆序，則序列無序。

2. 利用這一原理，bubblesort按照逐漸消除逆序對的思路來實作整體有序。

3. 實作：對序列進行若幹趟掃描，每遇到相鄰逆序對，交換之，直至不再存在逆序對。

4. 算法的正确性分析：

（1）不變性（問題已求解的部分擴大）：每一輪掃描交換，都會使目前未就位的元素中最大的那個就位（每次冒出一個最大的泡）

（2）單調性（問題未求解的規模遞減）：每一輪掃描交換，都會使有序序列長度增1，無序序列長度減1，問題規模也因而減1

5. 實作為如下代碼：

6. 複雜度分析：

（1）基本語句為第12行的if(a[i]>a[i+1])

（2）初始時，必然會進入第9行的while循環，然後進入第11行的for循環，基本語句被執行n-1次。

（3）最好情況是輸入完全有序，while循環隻進入一次，for循環執行n-1輪，是以基本語句相應地執行n-1次，T(n) = n-1=Ω(n)

（4）最壞情況是輸入完全逆序，while循環被執行n次；在第 i 輪while循環中，for循環執行 i 輪，基本語句也相應地執行 i 次。是以基本語句累加執行n(n-1)/2次，T(n)=n(n-1)/2=O(n2)

Vector一章，對bubblesort有兩次常數優化。

函數原型是這樣的：

　　void bubble(Rank lo, Rank hi);

　　void bubbleSort(Rank lo, Rank hi);

Rank即向量元素的秩，在此被定義為int型。lo和hi為待排序區間的左、右界樁。

外部通過調用 v.bubbleSort(lo, hi) 來給向量v的區間[lo,hi)排序，而bubbleSort調用bubble(lo,hi)實作對每個無序子區間的收縮。

最樸素的bubblesort大概是這樣，最好最壞平均情況都為O(n^2)

第一次改進後是這樣，這種改進很常見，能使最好情況變為為O(n)。

第二次改進後是這樣，可以跳躍式地收縮區間，降低了平均情況常數因子

第二次改進可用下圖來描述