【DSA MOOC】起泡排序的原理及常数优化

根据学堂在线TsinghuaX: 30240184X 数据结构(2015秋)这门课的内容，对bubblesort做了一些总结。

1. bubblesort(起泡排序)，原理来自这样一个观察规律：若序列有序，则任意一对相邻元素顺序。其逆否命题为：若存在相邻元素逆序，则序列无序。

2. 利用这一原理，bubblesort按照逐步消除逆序对的思路来实现整体有序。

3. 实现：对序列进行若干趟扫描，每遇到相邻逆序对，交换之，直至不再存在逆序对。

4. 算法的正确性分析：

（1）不变性（问题已求解的部分扩大）：每一轮扫描交换，都会使当前未就位的元素中最大的那个就位（每次冒出一个最大的泡）

（2）单调性（问题未求解的规模递减）：每一轮扫描交换，都会使有序序列长度增1，无序序列长度减1，问题规模也因而减1

5. 实现为如下代码：

 1 void swap(int& a,int& b){
 2     int t=a;
 3     a=b;
 4     b=t;
 5 }
 6 
 7 void bubblesort(int a[],int n){
 8     bool sorted = false; //先假设尚未整体有序
 9     while(!sorted){ //进入循环体
10         sorted=true; //假设现在前n项已有序
11         for(int i=0; i<n-1; i++){ //进行一趟扫描交换（从0一直到n-1，判断每组相邻元素）
12             if(a[i] > a[i+1]){ 
13                 swap(a[i],a[i+1]);
14                 sorted = false; //这一趟有交换则还需要再一趟扫描
15             }
16         }
17         n--;//一趟扫描交换必然会冒出一个泡~所以后面已就位的元素可以不在下次的扫描范围内了
18     }    
19 }
20

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(n²)

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)

 1 //最朴素版
 2 void bubble(Rank lo, Rank hi) {
 3     while (++lo < hi){//从左至右扫描，修正相邻逆序对
 4         if (_elem[lo - 1]>_elem[lo]){
 5             swap(_elem[lo - 1], _elem[lo]);
 6         }
 7     }
 8 }
 9 void bubbleSort(Rank lo, Rank hi){
10     while (lo < hi) bubble(lo, hi--);//右界桩每次向左挪一位
11 }

第一次改进后是这样，这种改进很常见，能使最好情况变为为O(n)。

 1 bool bubble(Rank lo, Rank hi) {
 2     bool sorted=true;//增设sorted变量，记录此次扫描是否发生交换（未发生交换则sorted=true）
 3     while (++lo < hi){
 4         if (_elem[lo - 1]>_elem[lo]){
 5             sorted = false;
 6             swap(_elem[lo - 1], _elem[lo]);
 7         }
 8     }
 9     return sorted;//返回是否已有序
10 }
11 void bubbleSort(Rank lo, Rank hi){
12     while (!bubble(lo, hi--));//一趟扫描没有发生交换（检测结果为sorted）则排序完成
13 }

第二次改进后是这样，可以跳跃式地收缩区间，降低了平均情况常数因子

 1 Rank bubble(Rank lo, Rank hi) {
 2     Rank last=lo;//设置last变量，记录最后一次交换的位置
 3     while (++lo < hi){;}
 4 
 5             swap(_elem[lo - 1], _elem[lo]);
 6         if (_elem[lo - 1]>_elem[lo]){
 7             last = lo
 8         }
 9         return last;//last及以后的元素都已就位，不必再进行扫描
10 }
11 void bubbleSort(Rank lo, Rank hi){
12     while (lo<(hi=bubble(lo, hi--)));//将右界桩挪到最后一次last位置
13 }

第二次改进可用下图来描述