數(shù)據(jù)結(jié)構(gòu)各種排序算法的時(shí)間性能(完整版)
【正文】 排序后，前50個(gè)有序元素為：五：實(shí)現(xiàn)圖1 控制臺(tái)程序?qū)嶒?yàn)結(jié)果：實(shí)驗(yàn)分別實(shí)現(xiàn)插入排序、冒泡排序、堆排序、合并排序、快速排序，以不同規(guī)模（100，1000，2000，5000，10000，100000個(gè)數(shù)據(jù)）的隨機(jī)數(shù)作為測(cè)試數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果截圖如下：排序規(guī)模為100排序規(guī)模為：1000排序規(guī)模為：2000排序規(guī)模為：5000排序規(guī)模為：10000排序規(guī)模為：100000（六）算法性能分析在程序中我們根據(jù)數(shù)據(jù)規(guī)模的不同產(chǎn)生不同的隨機(jī)整型數(shù)組，然后分別讓不同的排序算法來(lái)進(jìn)行從小到大的排序。圖4還顯示出雖然冒泡排序和插入排序的時(shí)間復(fù)雜度相同，但插入排序的性能仍然比冒泡排序好，尤其在排序時(shí)間方面?；蛟S以后在研究算法方面的確需要好好分析效率，數(shù)據(jù)結(jié)構(gòu)的確是一門(mén)很有用的學(xué)科，以后不能丟棄。但是平心而論，真正實(shí)現(xiàn)起來(lái)還真是問(wèn)題多多，首先是怎么樣調(diào)用時(shí)間的問(wèn)題，這也是第一個(gè)先想的問(wèn)題，本來(lái)打算就只比較交換次數(shù)和比較次數(shù)的，但是這些其實(shí)沒(méi)有比時(shí)間更直觀的反應(yīng)排序的效率。表1為在輸入規(guī)模分別為100，1000，2000，5000，10000，100000時(shí)各個(gè)算法的元素交換次數(shù)。堆排序的最壞時(shí)間復(fù)雜度為O(nlogn)。最壞情況(非遞增)下，最多比較i次，因此需要的比較次數(shù)是：所以，時(shí)間復(fù)雜度為O(n2)。}9返回當(dāng)前的值。int rightLength() const{ return listSize fence。void prev() { if (fence != 0) fence。 listSize = fence = 0。 } } s[p]=key。 } for(i=p。 while(pr) { for(i=r。 if(left right){ i=(left + right)/2。//計(jì)算時(shí)間差，d的單位為ms. cout堆排序算法對(duì)thisRanNum個(gè)隨機(jī)數(shù)排序時(shí)間為為d ms.endl。 for(i=0。 LARGE_INTEGER Freg。 } else if(i=m/2) thisSortNum++。 s[i]=s[2*i]。amp。 } } } QueryPerformanceCounter(amp。 for(unsigned long int i=0。 LARGE_INTEGER Freg。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上飄浮。 s[j]=temp。i++) { j=i。 QueryPerformanceFrequency(amp。 }}（3）插入排序：插入排序的思想是將一組無(wú)序的元素分別插入一個(gè)已經(jīng)有序的的數(shù)組里，并保證插入后的數(shù)組也是有序的。a[low]=pivotkey) ++low。int partition(int a[],int low,int high){//快速排序中的一趟 int pivotkey。 } coutendl。如此下去，直到堆為空。 int rightLength() const = 0。) = 0。一、需求分析 (1) 輸入的形式和輸入值的范圍：本程序要求實(shí)現(xiàn)各種算法的時(shí)間性能的比較，由于需要比較的數(shù)目較大，不能手動(dòng)輸入，于是采用系統(tǒng)生成隨機(jī)數(shù)。 HUNAN UNIVERSITY課程實(shí)習(xí)報(bào)告題 目： 排序算法的時(shí)間性能 學(xué)生姓名 學(xué)生學(xué)號(hào) 專業(yè)班級(jí) 指導(dǎo)老師 李曉鴻 完 成 日 期 設(shè)計(jì)一組實(shí)驗(yàn)來(lái)比較下列排序算法的時(shí)間性能 快速排序、堆排序、希爾排序、冒泡排序、歸并排序(其他排序也可以作為比較的對(duì)象） 要求 (1)時(shí)間性能包括平均時(shí)間性能、最好情況下的時(shí)間性能、最差情況下的時(shí)間性能等。用戶輸入隨機(jī)數(shù)的個(gè)數(shù)n，然后調(diào)用隨機(jī)事件函數(shù)產(chǎn)生n個(gè)隨機(jī)數(shù)，對(duì)這些隨機(jī)數(shù)進(jìn)行排序。 lbool remove(Elemamp。 bool setPos(int pos) = 0。到最后結(jié)束時(shí)，就排出了一個(gè)由小到大排列的數(shù)組。 return ra。 //作為樞軸來(lái)使用 pivotkey=a[low]。 a[high]=a[low]。當(dāng)所有無(wú)序組的元素都插入完畢時(shí)，一個(gè)有序數(shù)組構(gòu)造完成。Freg)。 temp=s[i]。 } QueryPerformanceCounter(amp。如此反復(fù)進(jìn)行，直到最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。 LARGE_INTEGER Count1,Count2。i(thisRanNum)。Count2)。n[i]=n[2*i+1]。 s[2*i]=ma。}void Sort::heapCreat(unsig
化學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1