改进版冒泡排序：在一轮迭代中，如果没有发生交换的话，这就说明了待排序的元素已经是排序好的，可以直接退出迭代。最坏情况下时间复杂度为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;//发生交换，就预示着要进行下一轮迭代
}
}
}
}
分析
在冒泡排序中，数据的比较和移动是在相邻单元中进行的，每次交换只能上移或下移一个位置，*同时比较过的数据，在下一遍比较时，有可能再次被比较，产生冗余比较。因此，冒泡排序的总比较次数和移动次数较多。
