文档介绍：: .
冒泡排序算法的改进
冯泽明(20132932)，郭华垠(20132935)，王煜(2013295可能在中间的某一趟排序完后就终止，但总的比较次数仍为0(/2).所以算法的平均时间复杂度为0(/2)。因此，这种算法最好的时间复杂度为0(n)。平均，最坏时刻复杂度为0(/2)。
三、第二种改进：记录最后一次交换位置
在冒泡排序的每趟扫描中，记住最后一次交换发生的位置lastexchange也能有所帮助。因为该位置之前的相邻记录已经有序，故下一趟排序开始的时候，0到lastexchange已经是有序的了，lastexchange到n-1是无序区。，而非递减1，以此减少排序趟数。
这种算法代码如下：
template<classT>doubleImproveBubble2(T*myArray,intn){clock_tstart_time=clock();intm=n-1,k,j;boolisSorted=false;while(m>0){for(k=j=0;j<m&&!isSorted;j++){if(myArray[j]>myArray[j+1]){Swap(myArray[j],myArray[j+1]);k=j;/*记录每次交换的位置*/isSorted=false;/*如果是没有排序，就重新设定标志*/}}m=k;/*记录最后一个交换的位置*/
}
clock_tend_time=clock();
return(double)(end_time-start_time)/CLOCKS_PER_SEC;
}
(从小到大)-1和0。即算法最好的时间复杂度为O(n);若初始记录是反序(从大到小)的则需要进行n--。在这情况下比较和移动次数达到最大值：
比较次数：Cmax=n(n-1)/2
移动次数Mmax=3n(n-1)/2因此，这种办法的最坏时间复杂度也为O(n"2)。，从而减少了比较的次数，但总的比较次数仍为O(n”2).所以算法的平均时间复杂度为O(n"2)。(n)。平均，最坏时刻复杂度为O(n”2)。
四、第三种改进：双向扫描，提高效率
若记录的初始状态为：只有最轻的气泡位于d[n]的位置(或者最重的气泡位于d[0]位置).-1趟扫描。实际上只需一趟扫描就可以完成排序。所以对于这种不对称的情况。可对冒泡排序又作一次改进。，再从上扫到下，来回地进行扫描，这样就得到双向冒泡排序算法。
代码如下：
template<classT>doubleImproveBubble3(T*myArray,intn){
clock_tstart_time=clock()