<BubbleSort>
基本思想：在[lo,hi]区间内，从左往右，依次对相邻元素进行比较，若逆序，交换两元素位置（稳定排序），直至各元素有序；
1.蛮力算法，不能及时提前退出，总是必须做n-1趟扫描交换
void BubbleSort0(int a[],int lo,int hi)
{
if(hi-lo<1) return;
int n=hi-lo+1;
while(n--)//在尚未确认全局有序前，逐趟进行扫描交换
{
for(int i=lo;i<lo+n-1;i++)
if(a[i]>a[i+1])Swap(a[i],a[i+1]);
}
}
- 借助布尔型标志位sorted，可及时提前退出，而不致总是蛮力地做n - 1趟扫描交换;
[若该趟未发生扫描交换，说明前序列已有序]
void BubbleSort1(int a[],int lo,int hi)
{
if(hi-lo<1) return;
int n=hi-lo+1;
bool sorted=false; //整体排序标志，首先假定尚未排序
while(!sorted)
{
sorted=true;//假定已经进行排序
for(int i=lo+1;i<lo+n-1;i++)
if(a[i-1]>a[i])
{
sorted=false;
Swap(a[i-1],a[i]);
}
n--;
}
}
完成的扫描交换趟数=实际发生元素交换的扫描交换趟数+1
但，对尾部有序（或接近有序）的输入，算法依然亦步亦趋地收敛，导致元素比较次数过多
3.借助整数last尽快地收缩待排序区间：既可提前退出，更可减少每趟（及所有）扫描交换中元素比较操作
【若尾端元素已有序，通过last将排序区间长度改变至无序区间的长度，若发生交换=无序=last前移，当last=lo时排序完成】
对尾部有序（或接近有序）的输入，算法收敛的速度大大提高
元素交换的次数仅取决于输入序列，与前两个版本相同
void BubbleSort2(int a[],int lo,int hi)
{
if(hi-lo<1) return;
int n=hi-lo+1;
int last;
for(;lo<n;n=last) //控制排序区间长度，n慢慢收缩至lo之前的位置，每次last标记的是
{
for(int i=lo;i<lo+n-1;i++)
{
if(a[i]>a[i+1])
{
Swap(a[i],a[i+1]);
last=i;
}
}
}
}
复杂度分析：
时间复杂度：
最好情况：（改进后的冒泡排序）本身有序，没有数据交换，只有n次比较，复杂度为O(n)；
最坏情况：排序表逆序，此时需比较1+2+3+...+(n-1)=n(n-1)/2次，同时需要作等数量级的记录移动，因此总的时间复杂度为O(n^2)。
