排序 - 交换排序 - 冒泡排序（二）
算法分析
( )算法的最好时间复杂度
若文件的初始状态是正序的 一趟扫描即可完成排序 所需的关键字比较次数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 趟扫描
③改进不对称性的方法
lishixinzhi/Article/program/sjjg/201311/23796
