<BubbleSort>
基本思想：在[lo,hi]區(qū)間內(nèi)盼理，從左往右间涵，依次對相鄰元素進行比較，若逆序榜揖，交換兩元素位置（穩(wěn)定排序）勾哩，直至各元素有序抗蠢；
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]);
}
}
- 借助布爾型標(biāo)志位sorted，可及時提前退出潜叛，而不致總是蠻力地做n - 1趟掃描交換;
[若該趟未發(fā)生掃描交換秽褒，說明前序列已有序]
void BubbleSort1(int a[],int lo,int hi)
{
if(hi-lo<1) return;
int n=hi-lo+1;
bool sorted=false; //整體排序標(biāo)志，首先假定尚未排序
while(!sorted)
{
sorted=true;//假定已經(jīng)進行排序
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--;
}
}
完成的掃描交換趟數(shù)=實際發(fā)生元素交換的掃描交換趟數(shù)+1
但威兜，對尾部有序（或接近有序）的輸入销斟，算法依然亦步亦趨地收斂，導(dǎo)致元素比較次數(shù)過多
3.借助整數(shù)last盡快地收縮待排序區(qū)間：既可提前退出椒舵，更可減少每趟（及所有）掃描交換中元素比較操作
【若尾端元素已有序蚂踊，通過last將排序區(qū)間長度改變至無序區(qū)間的長度，若發(fā)生交換=無序=last前移笔宿，當(dāng)last=lo時排序完成】
對尾部有序（或接近有序）的輸入犁钟，算法收斂的速度大大提高
元素交換的次數(shù)僅取決于輸入序列，與前兩個版本相同
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) //控制排序區(qū)間長度泼橘，n慢慢收縮至lo之前的位置涝动，每次last標(biāo)記的是
{
for(int i=lo;i<lo+n-1;i++)
{
if(a[i]>a[i+1])
{
Swap(a[i],a[i+1]);
last=i;
}
}
}
}
復(fù)雜度分析：
時間復(fù)雜度：
最好情況：（改進后的冒泡排序）本身有序，沒有數(shù)據(jù)交換炬灭，只有n次比較醋粟，復(fù)雜度為O(n)；
最壞情況：排序表逆序重归，此時需比較1+2+3+...+(n-1)=n(n-1)/2次昔穴，同時需要作等數(shù)量級的記錄移動，因此總的時間復(fù)雜度為O(n^2)提前。
