冒泡排序

算法描述

1. 比較相鄰元素，如果前一個(gè)比后一個(gè)大，那么就交換位置。
2. 對每一個(gè)相鄰的元素進(jìn)行相同的操作，從開始到最后，最終排到最后的是最大的元素。
3. 因?yàn)橐呀?jīng)確定最后的元素是最大的，所以去除最后一個(gè)元素，對前面的所有元素再進(jìn)行上述操作。
4. 循環(huán)1~3

算法實(shí)現(xiàn)

算法優(yōu)化

問題：多余的比較

解決：記錄每一趟最后一次交換的位置。

問題：每一趟的結(jié)果只有一個(gè)最大值效率低

解決：每一趟既找最大值也找最小值

耗時(shí)對比：

第二種優(yōu)化效率最好。

算法分析

• 最佳情況：最終順序與初始順序相同。 if語句比較n-1次。 時(shí)間復(fù)雜度：T(n) = O(n)
• 最差情況：最終順序與初始順序相反。 if語句比較次數(shù)：n-1+n-2+……+1 時(shí)間復(fù)雜度：T(n) = n(n-1)/2 = O(n2)
• 平均復(fù)雜度：T(n) = O(n2)