冒泡排序和快速排序的区别 排序 - 交换排序 - 冒泡排序（二）

排序 - 交换排序 - 冒泡排序（二）  

　　 算法分析

　　( )算法的最好时间复杂度

　　若文件的初始状态是正序的 一趟扫描即可完成排序 所需的关键字比较次数C和记录移动次数M均达到最小值

　　C min =n

　　M min =

　　冒泡排序最好的时间复杂度为O(n)

　　( )算法的最坏时间复杂度

　　若初始文件是反序的 需要进行n 趟排序 每趟排序要进行n i次关键字的比较( ≤i≤n ) 且每次比较都必须移动记录三次

　　来达到交换记录位置 在这种情况下 比较和移动次数均达到最大值

　　C max =n(n )/ =O(n )

　　M max = n(n )/ =O(n )

　　冒泡排序的最坏时间复杂度为O(n )

　　( )算法的平均时间复杂度为O(n )

　　虽然冒泡排序不一定要进行n 趟 但由于它的记录移动次数较多 故平均时间性能比直接插入排序要差得多

　　( )算法稳定性

　　冒泡排序是就地排序 且它是稳定的

　　 算法改进

　　上述的冒泡排序还可做如下的改进

　　( )记住最后一次交换发生位置lastExchange的冒泡排序

　　在每趟扫描中 记住最后一次交换发生的位置lastExchange (该位置之前的相邻记录均已有序) 下一趟排序开始时

　　R[ lastExchange ]是有序区 R[lastExchange n]是无序区 这样 一趟排序可能使当前有序区扩充多个记录 从而减少排

　　序的趟数 具体算法【参见习题】

　　( ) 改变扫描方向的冒泡排序

　　①冒泡排序的不对称性

　　能一趟扫描完成排序的情况

　　只有最轻的气泡位于R[n]的位置 其余的气泡均已排好序 那么也只需一趟扫描就可以完成排序

　　【例】对初始关键字序列 就仅需一趟扫描

　　需要n 趟扫描完成排序情况

　　当只有最重的气泡位于R[ ]的位置 其余的气泡均已排好序时 则仍需做n 趟扫描才能完成排序

　　【例】对初始关键字序列 就需七趟扫描

　　②造成不对称性的原因

　　每趟扫描仅能使最重气泡 下沉 一个位置 因此使位于顶端的最重气泡下沉到底部时 需做n 趟扫描

　　③改进不对称性的方法