排序算法效率分析及總結(jié)

1、C語言主流的排序算法效率分析及總結(jié)班級：計科二班日期：2016-3-29星期二作者：XXX工作：算法搜集及程序組合，結(jié)論總結(jié)。同組者：劉文工作：程序測試，時間記錄以及程序演示這次我們組主要搜集了冒泡排序算法，簡單排序算法，直接插入排序算法，希爾排序算法，堆排序算法，快速排 序算法六種常見的排序算法，并對它們的運(yùn)行效率作了一個簡單的測試與分析。A冒泡排序算法思想簡單描述：在要排序的一組數(shù)中，對當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對相鄰的兩個數(shù)依次進(jìn)行比較和調(diào)整，讓較 大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。冒泡排 序是穩(wěn)定的。算法時間

2、復(fù)雜度：O(N2)下面我們來測試一下不同數(shù)據(jù)量的排序時間：這是200個亂序隨機(jī)數(shù)：冒泡排序運(yùn)行時間為 0.000000毫秒這是1000個亂序隨機(jī)數(shù)：冒泡排序運(yùn)行時間為 3.000000毫秒這是5000個亂序隨機(jī)數(shù)：冒泡排序運(yùn)行時間為 70.000000毫秒這是20000個亂序隨機(jī)數(shù)：冒泡排序運(yùn)行時間為 1464.000000毫秒從不同數(shù)據(jù)量的縱向分析來看，1，在冒泡排序算法里，隨著數(shù)據(jù)量的增加，其運(yùn)行時間也會越來越長。2，在兩百個數(shù)據(jù)的時候，其運(yùn)行時間少到忽略不計，即運(yùn)算瞬間完成。這說明冒泡排序在處理小數(shù)據(jù)量的時候還 是很給力的3，當(dāng)處理的數(shù)據(jù)量從 5000提到20000的時候，冒泡排序的運(yùn)行

3、時間發(fā)生了質(zhì)的增加。從幾十毫秒到幾千毫秒, 運(yùn)行時間大大增加，從這里可見，冒泡排序在處理稍微大的數(shù)據(jù)的時候便已經(jīng)顯現(xiàn)出了力不從心感，我個人感 覺已不大適用。B簡單選擇排序算法思想簡單描述：在要排序的一組數(shù)中，選岀最小的一個數(shù)與第一個位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個位置的 數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。選擇排序是不穩(wěn)定的。時間復(fù)雜度：O(N2)下面我們依然來測試一下簡單選擇排序在不同數(shù)據(jù)量的運(yùn)行時間：這是200個亂序隨機(jī)數(shù)：簡單選擇排序運(yùn)行時間：0.000000毫秒這是1000個亂序隨機(jī)數(shù)：簡單選擇排序運(yùn)行時間：2.000000毫秒這是5000個亂序隨機(jī)數(shù)

4、：簡單選擇排序運(yùn)行時間：44.000000毫秒這是20000個亂序隨機(jī)數(shù)：簡單選擇排序運(yùn)行時間：694.000000毫秒從不同數(shù)據(jù)量的縱向分析來看，1，其運(yùn)行時間隨著數(shù)據(jù)量的增加而增加2，簡單選擇排序同冒泡排序一樣，在處理像200個這樣的小數(shù)據(jù)量的時候，其運(yùn)行時間可以忽略不計，即瞬間完成3，當(dāng)數(shù)據(jù)量從5000提高到20000的時候，其運(yùn)行時間也是提高了幾十倍。C直接插入排序算法思想簡單描述：在要排序的一組數(shù)中，假設(shè)前面(n-1) n>=2個數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個數(shù)插到前面的有序數(shù)中，使得這 n個數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。直接插入排序是穩(wěn)定的。算法時間復(fù)

5、雜度：O(N2)下面我們來簡單測試一下直接插入排序在不同數(shù)據(jù)量下的運(yùn)行時間：這是200個亂序隨機(jī)數(shù)：直接插入排序運(yùn)行時間：0.000000毫秒這是1000個亂序隨機(jī)數(shù)：直接插入排序運(yùn)行時間：2.000000毫秒這是5000個亂序隨機(jī)數(shù)：直接插入排序運(yùn)行時間：42.000000毫秒這是20000個亂序隨機(jī)數(shù)：直接插入排序運(yùn)行時間：684.000000毫秒從不同數(shù)據(jù)量的縱向分析來看：直接插入排序在想200個這樣的小數(shù)據(jù)量的時候執(zhí)行非常快，效率高。當(dāng)數(shù)據(jù)量增加的20000的時候，運(yùn)行時間會猛增幾十倍，效率呈現(xiàn)下降趨勢。D希爾排序算法思想簡單描述：在直接插入排序算法中，每次插入一個數(shù)，使有序序列只增加

6、1個節(jié)點，并且對插入下一個數(shù)沒有提供任何幫助。如果比較相隔較遠(yuǎn)距離(稱為增量)的數(shù)，使得數(shù)移動時能跨過多個元素，則進(jìn)行一次比較就可能消除多個元素交換。算法先將要排序的一組數(shù)按某個增量d分成若干組，每組中記錄的下標(biāo)相差d.對每組中全部元素進(jìn)行排序，然后再用一個較小的增量對它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時，整個要排序的數(shù)被分成一組，排序完成。希爾排序是不穩(wěn)定的。希爾排序時間復(fù)雜度：O(N1.3)(平均)最好的 O(N)最差的O(N2)下面我們來簡單測試一下希爾排序在不同數(shù)據(jù)量的運(yùn)行時間情況：這是200個亂序隨機(jī)數(shù)：3 ' E:崔.于龍 JiWt-EtiLqXfMiMu.exr 戲

7、卓世華批庫訃鐘 希:T 排x：u：i：E . " J. s i *< + *4,-i小 ' i i-11. q17045364 妙01I4&& 11569 11638 1&3121247627S221E&34901?5I ='4'J3181185455351612171!ISQI5ES3的昶1260«1&I2I191-=|E9402B3S 5952 勺19235717 沁D1：誠:？3'卩 12.-!1: JMG2E6247465=53101B1133472537 28734fi! 3&1

8、5 305S6656 朋43 TOSS T296 7331 7464ld22? 10244 102701C660 1130613421 13&16 1 曲 86 14IS6 1436476)3113501144302?11E3ZQ 1535K IfiSE LEfill IFH 程 15MH 1&L7D lfi«£ 1BB16 1BEBB 1646£3 14723 14907 149S3 150560 17035 17062 17074 1?168 17394 17457 t?5TS 17643 17&36 19060 18】嗣 LB4-31

9、 18597 18767 1B&92 1939& 嚴(yán)叫 71 M61519I&B7 K7B2 1W32 30081 20149 20295 2D3L 20S90 20554 血盟 20630) 2064S 20736210D9 21064 21530 邊竝 21256 21284 31W2 21B0T 滋臨 52160 汀1雖 巧 撫:瘢 2S45 22S67 22604 32899 2EMS 23373 23412233 鑒2524.039 34337 2»4< 24W3 21921 24»S3 頭即E 25254 255P7 K324 2何

10、擁西昭E 37653 278®2S132 28310 28丹9 囲5憫 2®52 28854 凸U當(dāng) 29燈5 2933? 29338 258 29537 29650 E&7O6 298&0' 30159 3025430 20& S03©& 30421 3Q5J0 凹更30SZ2 31356 312£5 319 呂 10 旳 3197S 3193& 昭2Q 3ZP95 3222& 3E315 <：2i33 3 244i 32528_ 32569 32?10帝駅松庫運(yùn)昕時問0-«000

11、00丼 E 卄；& 日* flhys；1*3*+*+n”w工1"*¥< 卄 5L4Ji !：*, I昌泡排序*+* *+*+ 簡単埠繇備* 一 宜期畝Mt尉*+* 舄加不EWW儀卄 逍豐k序!沖"”屮耳齊半 快速排 豐掃呻IEtH1： 么出封卓電*<=*4+希爾排序運(yùn)心=11 - 退出冒卄¥*事*>寸耳行時間為：0.000000毫秒這是1000個亂序隨機(jī)數(shù)： 希爾排序的運(yùn)行時間：0.000000毫秒 這是5000個亂序隨機(jī)數(shù):S It僱蚊皿-«r"- XiU!43 JuStOU上迫3WJ07Jut273

12、9;J'JZz JUtlJ SIMM JUt4D孔”44:D672 亂也取 JHb-4 Sibyl :J仁生3U?323U'f：二加T対 30740 20745307T2 M 療閔勖刑自?ft762 50776 3073130735 307B53OS2S0&30 3 強(qiáng)巔?0313 3O3GIB曲陰 303813Q6S4 3QB93 3QWL 30肛330925 39937 3舊叩 30543 刃945 3QE巧 303309W 31QQQ 51C1510153彈231024 31&2531 DIE310&4 31Dffi 31072310123106?

13、 310&?含 1吋0 31092311 DO 3 Uc£ 訂Id白 SlUl 削'Li 31129 311K4 JllSi 911J+ JI 154 Ml站：11ol 3117- 31：:SO 31182 311?4 31201.121. 312JO .1234 J1J53 :. 12KD 31S7S 31S78 3128& aifNfi S13M 3L3D1 313H 313S4 313S 31332 31237 31353 313S4 313S? 313&3 313«3 2JJ7 L 期恥 31397 時赧 31416 31+1? 31

14、4QG 31443 31 苗4 3卻硏 314K 31169 3L4M 31472 31476 312 31 ID 31M1r-15.13t5?315223侔莎 <1F5?31硏2 汨血7 :嚇屆 ：1EI3157：P1&7E31FR?3155S16011'1310233&28 31636 3t65« 316歆 91669 31&72 31C?8 31&B1 316S5 313 3l£M 21996 316&? 317ft0 3tTDS 31709 31721 pL7a5 3I7M 31767 317®0 21

15、7BS 3L744 5176 3：17M 21A10 S1BM 2LE13 31814 31S27 3LE41 313Ei 3105 319M 3 1866 018?0 31K74 31876 318? S1S79 31B9131999 33900 3L9»3 3190ft 31 潮 3t»12 31914 31903 3LB42 31B44 3)963 319U 3L»3 3K76 31V7» 31935 31K8 33001 3200* 32011 X2O13 32O2E 320E7 33Q37 32MI 12M3 330 p 32073 32077

16、 320T?B 32097 叢陽7 33103 32113 32119 32127 32137 S2163 3E1GS 32174 321G1 321K2 32185 8213 k 3Z1E7 32150 32157322013221b 3221B 32225322263ZZ34 S224T3Z254 3Z2b3 32254N&4 3227i 323OL 32303衛(wèi)4 3_：314 3202? 8i32fc 328 (MM 理44亂擔(dān)5 ：2?託笑0 f剜掄縱 325 i 337?型品3論扯船鶉Lg 弗 913240432.7 託網(wǎng) 324U3211222112S2421314Z&g

17、t;3242132<31324443241 監(jiān)口 E 監(jiān)船 F 迎4 巧屈師牌4鮒 325QL 32512 冀函 3252& 33627 3231 3Z531 32常4 32546 32577 325TO 32PS6 3圖02 32W? 3K1Q 32&24 3 E62532631 理期 336 卸 32盟133期 3E&57335 32 昕 Q 呂 2563 緒訕 3J6723267 須 $陽耳茨 TT 32677326T3 32683 32702 327嗎 32?ub 32708 33710 32?14 32743 扯阿：;y_ 空 32751 32?b2 ：

18、63 32765+扎!t序運(yùn)彳祁衛(wèi)1 )0 DOO砒疋.；.墮 *=*2一 21隼埠更岸序”4=*“wr.宜農(nóng)區(qū)蜜崢"彳申丐半車洛垃按序普事耳時半工希爾排序的*#+(5., -5i*4*=*4+運(yùn)行時間：1.000000毫秒 這是20000個亂序隨機(jī)數(shù): 希爾排序的運(yùn)行時間：5.000000毫秒從不同數(shù)據(jù)量的縱向分析來看：從200個到20000量的隨機(jī)數(shù)，希爾排序運(yùn)行的時間都是非常快的，效率極高。20000個數(shù)據(jù)的時候也僅僅只是5毫秒，這說明希爾排序在處理大數(shù)據(jù)的能力上非常優(yōu)越。E堆排序算法思想簡單描述：堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進(jìn)。堆的定義如下：具有 n 個

19、元素的序列(h1,h2,.,hn),當(dāng)且僅當(dāng)滿足(hi>=h2i,hi>=2i+1 )或(hi<=h2i,hi<=2i+1)(i=1,2,.,n/2)時稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看岀，堆頂元素(即第一個元素)必為最大項。完全二叉樹可以很直觀地表示堆的結(jié)構(gòu)。堆頂為根，其它為左子樹、右子樹。初始時把要排序的數(shù)的序列看作是一棵順序存儲的二叉樹，調(diào)整它們的存儲順序，使之成為一個堆，這時堆的根節(jié)點的數(shù)最大。然后將根節(jié)點與堆的最后一個節(jié)點交換。然后對前面(n-1)個數(shù)重新調(diào)整使之成為堆。依此類推，直到只有兩個節(jié)點的堆，并對它們作交換，最后得到有n個節(jié)點的

20、有序序列。從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實現(xiàn)排序的函數(shù)。堆排序是不穩(wěn)定的。算法時間復(fù)雜度：O(nlog2n)。下面我們測試一下堆排序在不同數(shù)據(jù)量的運(yùn)行效果：這是200個亂序隨機(jī)數(shù)：堆排序運(yùn)行時間：0.000000毫秒這是1000個亂序隨機(jī)數(shù)：堆排序運(yùn)行時間：0.000000毫秒這是5000個亂序隨機(jī)數(shù)：堆排序運(yùn)行時間：1.000000毫秒這是20000個亂序隨機(jī)數(shù)：堆排序運(yùn)行時間：4.000000毫秒從不同數(shù)據(jù)量的縱向分析來看：堆排序不禁在處理小數(shù)據(jù)的時候效率非常高，就算處理幾萬個數(shù)據(jù)，也幾乎是瞬間完成。從200到20000個數(shù)據(jù)的運(yùn)行結(jié)果來看，堆排序在處理大數(shù)據(jù)的能力上還是很強(qiáng)的。F快速排序算法思想簡單描述：快速排序是對冒泡排序的