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

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

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

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

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

5、試一下直接插入排序在不同數(shù)據(jù)量下的運(yùn)行時(shí)間： 這是 200 個(gè)亂序隨機(jī)數(shù)：直接插入排序運(yùn)行時(shí)間：毫秒這是 1000 個(gè)亂序隨機(jī)數(shù)： 直接插入排序運(yùn)行時(shí)間：毫秒 這是 5000 個(gè)亂序隨機(jī)數(shù)： 直接插入排序運(yùn)行時(shí)間：毫秒 這是 20000 個(gè)亂序隨機(jī)數(shù)： 直接插入排序運(yùn)行時(shí)間：毫秒 從不同數(shù)據(jù)量的縱向分析來(lái) 看： 直接插入排序在想 200 個(gè)這樣的小數(shù)據(jù)量的時(shí)候執(zhí)行非?？?，效率高。當(dāng)數(shù)據(jù)量增加的 20000 的時(shí)候，運(yùn)行時(shí)間會(huì)猛增幾十倍，效率呈現(xiàn)下降趨勢(shì)。D 希爾排序算法思想簡(jiǎn)單描述：在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增加 1 個(gè)節(jié)點(diǎn)，并且對(duì)插入下一個(gè)數(shù)沒(méi)有提供任 何幫助。如果比

6、較相隔較遠(yuǎn)距離 (稱為增量 ) 的數(shù)，使得數(shù)移動(dòng)時(shí)能跨過(guò)多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1 時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。希爾排序是不穩(wěn)定的。希爾排序時(shí)間復(fù)雜度：0 (平均)最好的0(N)最差的0(N2) 下面我們來(lái)簡(jiǎn)單測(cè)試一下希爾排序在不同數(shù)據(jù)量的運(yùn)行時(shí)間情況： 這是 200 個(gè)亂序隨機(jī)數(shù)：希爾排序運(yùn)行時(shí)間為：毫秒這是1000個(gè)亂序隨機(jī)數(shù)：希爾排序的運(yùn)行時(shí)間：毫秒這是5000個(gè)亂序隨機(jī)數(shù)希爾排序的運(yùn)行時(shí)間：毫秒

7、 這是20000個(gè)亂序隨機(jī)數(shù)： 希爾排序的運(yùn)行時(shí)間：毫秒 從不同數(shù)據(jù)量的縱向分析來(lái)看:20000個(gè)數(shù)據(jù)的時(shí)候也僅僅只是5毫從200個(gè)到20000量的隨機(jī)數(shù)，希爾排序運(yùn)行的時(shí)間都是非?？斓?，效率極高 秒，這說(shuō)明希爾排序在處理大數(shù)據(jù)的能力上非常優(yōu)越。E 堆排序算法思想簡(jiǎn)單描述： 堆排序是一種樹形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。堆的定義如下：具有 n 個(gè)元素的序列 ( h1,h2,.,hn), 當(dāng)且僅當(dāng)滿足 ( hi>=h2i,hi>=2i+1 ) 或( hi<=h2i,hi<=2i+1 ) (i=1,2,.,n/2)時(shí)稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義

8、可以看岀，堆頂元素 ( 即第一個(gè)元素) 必為最大項(xiàng)。完全二叉樹可以很直觀地表示堆的結(jié)構(gòu)。堆頂為根，其它為左子樹、右子樹。初始時(shí)把 要排序的 數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹，調(diào)整它們的存儲(chǔ)順序，使之成為一個(gè)堆，這時(shí)堆的根節(jié) 點(diǎn)的數(shù)最大。然后 將根節(jié)點(diǎn)與堆的最后一個(gè)節(jié)點(diǎn)交換。然后對(duì)前面 (n-1) 個(gè)數(shù)重新調(diào)整使之成為堆。依此類 推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對(duì)它們作交換，最后得到有 n 個(gè)節(jié)點(diǎn)的有序序列。從算法描述來(lái)看，堆排 序需要兩個(gè)過(guò)程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成。一 是建堆的 滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。堆排序是不穩(wěn)定的。算

9、法時(shí)間復(fù)雜度： O(nlog2n) 。下面我們測(cè)試一下堆排序在不同數(shù)據(jù)量的運(yùn)行效果：這是 200 個(gè)亂序隨機(jī)數(shù)： 堆排序運(yùn)行時(shí)間：毫秒 這是 1000 個(gè)亂序隨機(jī)數(shù)： 堆排序運(yùn)行時(shí)間：毫秒 這是 5000 個(gè)亂序隨機(jī)數(shù)： 堆排序運(yùn)行時(shí)間：毫秒 這是 20000 個(gè)亂序隨機(jī)數(shù)： 堆排序運(yùn)行時(shí)間：毫秒 從不同數(shù)據(jù)量的縱向分析來(lái)看： 堆排序不禁在處理小數(shù)據(jù)的時(shí)候效率非常高，就算處理幾萬(wàn)個(gè)數(shù)據(jù)，也幾乎是瞬間完成。 從 200 到 20000 個(gè)數(shù)據(jù)的運(yùn)行結(jié)果來(lái)看，堆排序在處理大數(shù)據(jù)的能力上還是很強(qiáng)的。 F 快速排序 算法思想簡(jiǎn)單描述： 快速排序是對(duì)冒泡排序的一種本質(zhì)改進(jìn)。它的基本思想是通過(guò)一趟掃描后，

10、使得排序序列的長(zhǎng)度能大幅度 地減少。 在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長(zhǎng)度可能只減少 1?？焖倥判蛲ㄟ^(guò)一趟掃描， 就能確保某個(gè)數(shù) ( 以它為基準(zhǔn)點(diǎn)吧 )的左邊各數(shù)都比它小，右邊各數(shù)都比它大。 然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。顯然快速排序可以用遞 歸實(shí)現(xiàn)， 當(dāng)然也可以用?；膺f歸實(shí)現(xiàn)?？焖倥判蚴遣环€(wěn)定的。最理想情況算法時(shí)間復(fù)雜度： O(nlog2n) ，最壞 O(n2) 下面我們測(cè)試一下快速排序在不同數(shù)據(jù)量的運(yùn)行情況： 這是 200 個(gè)亂序隨機(jī)數(shù)：快速排序運(yùn)行時(shí)間毫秒算法。單選擇排這是 1000 個(gè)亂序隨機(jī)數(shù)： 快速排序運(yùn)行時(shí)間：毫秒 這是 5000 個(gè)亂序隨機(jī)數(shù)： 快速排序運(yùn)行時(shí)間毫秒 這是 20000 個(gè)亂序隨機(jī)數(shù)： 快速排序運(yùn)行時(shí)間毫秒 從不同數(shù)據(jù)量縱向分析來(lái)看： 隨著數(shù)據(jù)量的增加，快速排序運(yùn)行的時(shí)間也越來(lái)越長(zhǎng) 在處理小數(shù)據(jù)量的時(shí)候，快速排序效率非常高 在處理大數(shù)據(jù)的時(shí)候，運(yùn)行時(shí)間所花的也不是很長(zhǎng)，是可以接受的，個(gè)人認(rèn)為快速排序是一種比較平衡的 橫向分析這 6 種排序