|
算法分析 ()算法的最好时间复杂度 若文件的初始状态是正序的一趟扫描即可完成排序所需的关键字比较次数C和记录移动次数M均达到最小值 C min =n M min = 冒泡排序最好的时间复杂度为O(n) ()算法的最坏时间复杂度 若初始文件是反序的需要进行n趟排序每趟排序要进行ni次关键字的比较(≤i≤n)且每次比较都必须移动记录三次 来达到交换记录位置在这种情况下比较和移动次数均达到最大值 C max =n(n)/=O(n ) M max =n(n)/=O(n ) 冒泡排序的最坏时间复杂度为O(n ) ()算法的平均时间复杂度为O(n ) 虽然冒泡排序不一定要进行n趟但由于它的记录移动次数较多故平均时间性能比直接插入排序要差得多 ()算法稳定性 冒泡排序是就地排序且它是稳定的 算法改进 上述的冒泡排序还可做如下的改进 ()记住最后一次交换发生位置lastExchange的冒泡排序 在每趟扫描中记住最后一次交换发生的位置lastExchange(该位置之前的相邻记录均已有序)下一趟排序开始时 R[lastExchange]是有序区R[lastExchangen]是无序区这样一趟排序可能使当前有序区扩充多个记录从而减少排 序的趟数具体算法【参见习题】 () 改变扫描方向的冒泡排序 ①冒泡排序的不对称性 能一趟扫描完成排序的情况 只有最轻的气泡位于R[n]的位置其余的气泡均已排好序那么也只需一趟扫描就可以完成排序 【例】对初始关键字序列就仅需一趟扫描 需要n趟扫描完成排序情况 当只有最重的气泡位于R[]的位置其余的气泡均已排好序时则仍需做n趟扫描才能完成排序 【例】对初始关键字序列就需七趟扫描 ②造成不对称性的原因 每趟扫描仅能使最重气泡下沉一个位置因此使位于顶端的最重气泡下沉到底部时需做n趟扫描 ③改进不对称性的方法 在排序过程中交替改变扫描方向可改进不对称性具体算法【参见习题】 |
