3、one_turn
4、two_turn
5、three_turn
6、four_turn
7、five_turn
8、six_turn10101010101049999941088884997774888664777754666664555555通過上圖可以看出,冒泡法形象的描述來,4這個元素就像一個氣泡逐漸冒到上面來了。我們排序的有7個元素,最壞的情況全部倒序,4這個元素要冒上來需要6次。因此,n個元素,最壞的情況,需要
9、移動:1+2+3+...+(n-1)=1/2*n(n-1)次。倒序(最糟情況)第一輪:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交換3次)第二輪:7,10,9,8->7,10,8,9->7,8,10,9(交換2次)第一輪:7,8,10,9->7,8,9,10(交換1次)循環(huán)次數(shù):6次交換次數(shù):6次其他:第一輪:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交換2次)第二輪:7,8,10,9->7,8,10,9->7,8,10,9(交換0次)第一輪:7,8,10,9->7,8,9,10(交換1次)
10、循環(huán)次數(shù):6次交換次數(shù):3次上面我們給出了程序段,現(xiàn)在我們分析它:這里,影響我們算法性能的主要部分是循環(huán)和交換,顯然,次數(shù)越多,性能就越差。從上面的程序我們可以看出循環(huán)的次數(shù)是固定的,為1+2+...+n-1。寫成公式就是1/2*(n-1)*n。現(xiàn)在注意,我們給出O方法的定義:若存在一常量K和起點n0,使當n>=n0時,有f(n)<=K*g(n),則f(n)=O(g(n))。(呵呵,不要說沒學好數(shù)學呀,對于編程數(shù)學是非常重要的!?。。┈F(xiàn)在我們來看1/2*(n-1)*n,當K=1/2,n0=1,g(n)=n*n時,1/2*(n-1)*n<=1/2*n*n=K*g(
11、n)。所以f(n)=O(g(n))=O(n*n)。所以我們程序循環(huán)的復雜度為O(n*n)。再看交換。從程序后面所跟的表可以看到,兩種情況的循環(huán)相同,交換不同。其實交換本身同數(shù)據(jù)源的有序程度有極大的關(guān)系,當數(shù)據(jù)處于倒序的情況時,交換次數(shù)同循環(huán)一樣(每次循環(huán)判斷都會交換),復雜度為O(n*n)。當數(shù)據(jù)為正序,將不會有交換。復雜度為O(0)。亂序時處于中間狀態(tài)。正是由于這樣的原因,我們通常都是通過循環(huán)次數(shù)來對比算法。2.交換法:交換法的程序最清晰簡單,每次用當前的元素一一的同其后的元素比較并交換。#includevoidExchangeSort
12、(int*pData,intCount){intiTemp;for(inti=0;i13、one_t
14、urn
15、two_turn
16、three_turn
17、four_turn
18、five_turn
19、six_turn10987654910101010101088999997778888666677755555664444445從上面的算法來看,基本和冒泡法的效率一樣。倒序(最糟情況)第一輪:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交換3次)第二輪:7,10,9,8->7,9,10,8->7,8,10,9(交換2次)第一輪:7,8,10,9->7,8,9,10(交換1次)循環(huán)次數(shù):6次交換次數(shù):6次其他:第一輪:8,10,7,9->8,
20、10,7,9->7,10