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