數(shù)據(jù)結(jié)構(gòu)各種排序算法的時間性能-資料下載頁
2025-06-25 07:23本頁面
【正文】 輸入 等待輸入 輸出 插入排序算法對n個隨機(jī)數(shù)排序時間為 插入排序算法對n個隨機(jī)數(shù)交換次數(shù)為 冒泡排序算法對n個隨機(jī)數(shù)排序時間為 冒泡排序算法對n個隨機(jī)數(shù)交換次數(shù)為 堆排序算法對n個隨機(jī)數(shù)排序時間為 堆排序算法對n個隨機(jī)數(shù)交換次數(shù)為 合并排序算法對n個隨機(jī)數(shù)排序時間為 合并排序算法對n個隨機(jī)數(shù)交換次數(shù)為快速排序算法對n個隨機(jī)數(shù)排序時間為 快速排序算法對n個隨機(jī)數(shù)交換次數(shù)為 排序后，前50個有序元素為：五：實現(xiàn)圖1 控制臺程序?qū)嶒灲Y(jié)果：實驗分別實現(xiàn)插入排序、冒泡排序、堆排序、合并排序、快速排序，以不同規(guī)模（100，1000，2000，5000，10000，100000個數(shù)據(jù)）的隨機(jī)數(shù)作為測試數(shù)據(jù)集，實驗結(jié)果截圖如下：排序規(guī)模為100排序規(guī)模為：1000排序規(guī)模為：2000排序規(guī)模為：5000排序規(guī)模為：10000排序規(guī)模為：100000（六）算法性能分析在程序中我們根據(jù)數(shù)據(jù)規(guī)模的不同產(chǎn)生不同的隨機(jī)整型數(shù)組，然后分別讓不同的排序算法來進(jìn)行從小到大的排序。這里需要注意的是：每種排序算法在相同的輸入規(guī)模中原始無序數(shù)據(jù)都是一樣的。例如五種排序算法要對長度為100的無序數(shù)組進(jìn)行排序，它們所要排序的無序數(shù)組都是一樣的，我們以此來保證實驗的公正性。在這里我們認(rèn)為比較次數(shù)是排序算法的主要操作，因此我們在每個排序算法中加入計數(shù)器來記錄排序過程中的比較次數(shù)，以此來作為對算法性能分析的主要參數(shù)（排序時間作為輔助參數(shù)）。表1為在輸入規(guī)模分別為100，1000，2000，5000，10000，100000時各個算法的元素交換次數(shù)。表2為在輸入規(guī)模分別為100，1000，2000，5000，10000，100000時各個算法的排序時間。 排序規(guī)模（n） 算法10010002000500010000100000插入排序27822462559832116266052248708162509250617冒泡排序26842420119631585956790224520141127169842堆排序100016480370631060262319032985016合并排序555871919432553011204091536596快速排序5991037723702714311528791946925表1 排序算法比較次數(shù)性能比較 排序規(guī)模（n） 算法10010002000500010000100000插入排序16694冒泡排序堆排序合并排序快速排序表2 排序算法排序時間比較（單位ms）為了直觀起見，根據(jù)實驗數(shù)據(jù)畫出各種排序算法在不同輸入規(guī)模下交換次數(shù)的變化趨勢圖如圖2所示：圖2排序算法交換次數(shù)趨勢圖由上圖我們基本上看出插入排序和冒泡排序的比較次數(shù)隨輸入規(guī)模的呈非線性增長，而后三種排序方法——堆排序，合并排序，快速排序的比較次數(shù)隨輸入規(guī)模的增長基本呈線性變化趨勢。根據(jù)實驗數(shù)據(jù)畫出各種排序算法在不同輸入規(guī)模下交換次數(shù)的變化趨勢圖如圖3所示：圖3排序算法排序時間趨勢圖（單位：ms）實驗結(jié)果與我們對這五種算法的性能理論分析基本吻合：插入排序與冒泡排序的時間復(fù)雜度為O(n*n)，而后三種排序算法的時間復(fù)雜度為O(nlogn)。圖4還顯示出雖然冒泡排序和插入排序的時間復(fù)雜度相同，但插入排序的性能仍然比冒泡排序好，尤其在排序時間方面。（七）結(jié)論最后得出結(jié)論：時間性能上，快速排序 堆排序 合并排序 插入排序 冒泡排序交換次數(shù)上，合并排序 快速排序 堆排序 冒泡排序 插入排序(八)心得 作為拿來復(fù)習(xí)的一個報告還是蠻有成就感的，但是輸入1000000個數(shù)據(jù)的時候等得太久，實在等不出結(jié)果，而且放入值太大不方便作圖，于是就不參與數(shù)據(jù)分析，但是估計結(jié)果應(yīng)該相同。以前不懂排序只會用冒泡，因為冒泡排序是接觸編程的第一個排序，印象很深刻，而且?guī)缀醪粫缅e，當(dāng)數(shù)據(jù)比較大時它的弊端就真的出現(xiàn)了。本以為這個實驗還是比較好做的，排序幾乎都會，連助教都說一句你這個選題太沒難度了。但是平心而論，真正實現(xiàn)起來還真是問題多多，首先是怎么樣調(diào)用時間的問題，這也是第一個先想的問題，本來打算就只比較交換次數(shù)和比較次數(shù)的，但是這些其實沒有比時間更直觀的反應(yīng)排序的效率。尋找半天無果本來都打算放棄了，結(jié)果竟然有一個回復(fù)貼說QueryPerformanceCounter函數(shù)，于是就發(fā)現(xiàn)這個問題可以解決了。結(jié)果是想象的有點偏差，沒想到堆排序的速度也能這么快，合并排序的次數(shù)會那么少。本以為快速排序就是萬能的了，看來想多了?；蛟S以后在研究算法方面的確需要好好分析效率，數(shù)據(jù)結(jié)構(gòu)的確是一門很有用的學(xué)科，以后不能丟棄。
化學(xué)相關(guān)推薦
鄂ICP備17016276號-1