經(jīng)典c++編程實例.pdf

《經(jīng)典c++編程實例.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、1.冒泡法：這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因為它的工作看來象是冒泡：#includevoidBubbleSort(int*pData,intCount){intiTemp;for(inti=1;i=i;j--){if(pData[j]

2、eSort(data,7);for(inti=0;i<7;i++)cout<

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;i

13、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