七大排序之冒泡排序

<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]);

    }
}

---

---

2. 借助布尔型标志位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)。