根据学堂在线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(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)
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 }
第二次改进可用下图来描述
