改进版冒泡排序：在一轮迭代中，如果没有发生交换的话，这就说明了待排序的元素已经是排序好的，可以直接退出迭代。最坏情况下时间复杂度为O(n)，平均复杂度也为O(n)。
  源代码如下：

template<typename T>
void bubbingSort(T* a,int length)
{
    for (bool sorted = false; sorted = !sorted; length--)//注意sorted的初始化为false后经过 != 运算为true
    {
        for (int i = 1; i < length; i++)//length--，待排序的规模逐渐减小
        {
            if (a[i - 1] > a[i])//小到大排序
            {
                T temp = a[i-1];
                a[i - 1] = a[i];
                a[i] = temp;
                sorted = false;//发生交换，就预示着要进行下一轮迭代
            }
        }
    }
}

分析
在冒泡排序中，数据的比较和移动是在相邻单元中进行的，每次交换只能上移或下移一个位置，*同时比较过的数据，在下一遍比较时，有可能再次被比较，产生冗余比较。因此，冒泡排序的总比较次数和移动次数较多。