排序算法地時(shí)間性能比較

《排序算法地時(shí)間性能比較》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、實(shí)用文案排序算法的時(shí)間性能比較一、問題描述給出一組實(shí)驗(yàn)來比較下列排序算法的時(shí)間性能：快速排序、堆排序、冒泡排序二、基本要求（1）時(shí)間性能包括平均時(shí)間性能、最好情況下的時(shí)間性能、最差情況下的時(shí)間性能等。（2）實(shí)驗(yàn)數(shù)據(jù)應(yīng)具有說服力，包括：規(guī)模范圍要大（如從100到10000），數(shù)據(jù)的初始特性類型要多，因而需要具有隨機(jī)性；實(shí)驗(yàn)數(shù)據(jù)的組數(shù)要多，即同一規(guī)模的數(shù)組要多選幾種不同類型的數(shù)據(jù)來實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果要能以清晰的形式給出，如圖、表等。（3）算法所用時(shí)間必須是機(jī)器時(shí)間，也可以包括比較和交換元素的次數(shù)。（4）實(shí)驗(yàn)分析及其結(jié)果要能以清晰的方式來

2、描述，如數(shù)學(xué)公式或圖表等。（5）要給出實(shí)驗(yàn)的方案及其分析。三、工具/準(zhǔn)備工作MicrosoftVisualC++6.0軟件。四、分析與實(shí)現(xiàn)1.快速選擇排序這個(gè)是冒泡排序的一種改進(jìn)，他的基本思想就是在當(dāng)前無序區(qū)R【1….H】中任取一個(gè)數(shù)據(jù)元素的基準(zhǔn)用此基準(zhǔn)將當(dāng)前無序區(qū)劃分成左右二個(gè)較小的無序去區(qū)，R【1……i-1】和R【i+1…標(biāo)準(zhǔn)文檔實(shí)用文案..H】，且左邊的元素序子區(qū)中的數(shù)據(jù)元素均小于等于基數(shù)元素，右邊的元素序子區(qū)中的數(shù)據(jù)元素均大于等于基數(shù)元素。直到所有無序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?.堆排序堆排序?qū)嵸|(zhì)上就是具備有如下性質(zhì)

3、的完全二叉樹：樹中任一非子葉節(jié)點(diǎn)的關(guān)鍵字均大于等于其子孩子結(jié)點(diǎn)的關(guān)鍵字，它只要記錄一個(gè)大小的輔助空間，每個(gè)待排序的記錄只占有一個(gè)存儲空間，一般記錄數(shù)較小的。但對基數(shù)較大的文件還是很有效的，因?yàn)檫\(yùn)行時(shí)間主要是小號在建初始堆和調(diào)整建新堆時(shí)進(jìn)行的反復(fù)的篩選上的。3.冒泡排序這種排序的比較基本思想就是二二比較待排序的數(shù)據(jù)元素的大小，發(fā)現(xiàn)二個(gè)數(shù)據(jù)元素的次序相反時(shí)候，就進(jìn)行交換，知道沒有反序的數(shù)據(jù)為止。冒泡排序是一種一次比較出最小或最大值，然后將其放置序列的最后一位置，再將剩下的從打一個(gè)位置開始到N-1的位置進(jìn)行重復(fù)的操作。排序算法的時(shí)間空

4、間復(fù)雜度排序方法最壞情況平均情況最好情況快速排序O（nlogn）O(n2)O(1)堆排序O(nlogn)O(nlogn)O(n)冒泡排序O(n2)O(nlogn)O(n)程序代碼：#include#include#include標(biāo)準(zhǔn)文檔實(shí)用文案#defineMAXSIZE50typedefintKeyType;#defineMAXNUM100typedefstruct{KeyTypeKey;}RedType;RedTypeR[MAXNUM];typedefstruct{Red

5、Typer[MAXSIZE+1];intlength;}Sqlist;SqlistL,L0,L1,L2,L3,L4,L5,L6,L7;typedefSqlistHeadType;#defineRADIX10#defineMAX8#defineMAX_SPACE10000typedefintKeysType;typedefstruct{KeysTypeKeys[MAX];intnext;}SLCell;typedefstruct{標(biāo)準(zhǔn)文檔實(shí)用文案SLCellrl[MAX_SPACE];intKeynum;intrecnum;}SL

6、List;typedefintArrType[RADIX];intcompare[8];intchange[8];voidshuRu(SqlistL){inti=1,n;printf("請輸入你輸入的數(shù)據(jù)個(gè)數(shù):");scanf("%d",&n);printf("請依次的輸入各個(gè)數(shù)據(jù)值");L.length=n;for(;i<=L.length;i++){scanf("%d",&L.r[i]);}}voidshuChu(SqlistL){inti=1;printf("該順序存儲中的數(shù)據(jù)元素為：");for(;i

7、gth;i++){printf("%d",L.r[i]);}printf("%d",L.r[i]);標(biāo)準(zhǔn)文檔實(shí)用文案}//=======快速排序=========intpartition(SqlistL,intlow,inthigh){KeyTypepivotKey;L.r[0]=L.r[low];pivotKey=L.r[low].Key;change[4]++;while(low=pivotK

8、ey){--high;compare[4]++;}L.r[low]=L.r[high];change[4]++;compare[4]++;while(low