排序算法及應(yīng)用

課程名稱數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)項(xiàng)目編號(hào)1505P000201實(shí)驗(yàn)項(xiàng)目名稱排序算法及應(yīng)用實(shí)驗(yàn)學(xué)時(shí)2學(xué)時(shí)實(shí)驗(yàn)日期實(shí)驗(yàn)地點(diǎn)計(jì)算機(jī)應(yīng)用技術(shù)實(shí)驗(yàn)室指導(dǎo)教師班級(jí)姓名學(xué)號(hào)一、實(shí)驗(yàn)?zāi)康恼莆粘Ｓ玫呐判蚍椒?，深刻理解排序的定義和各種排序方法的特點(diǎn)。通過實(shí)驗(yàn)觀察不同方法的不同之處，記錄并分析各種排序方法的結(jié)果。二、實(shí)驗(yàn)環(huán)境硬件：每個(gè)學(xué)生需配備計(jì)算機(jī)一臺(tái)。操作系統(tǒng)：Windows；軟件：Windows操作系統(tǒng)+TurboC等；三、實(shí)驗(yàn)要求在教科書中，各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大概執(zhí)行時(shí)間。試通過隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵宇比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受。要求：理解及熟練運(yùn)用直接插入排序、快速排序、堆排序和歸并排序、哈希排序等內(nèi)部排序算法。通過計(jì)數(shù)統(tǒng)計(jì)各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)。分析算法的時(shí)間復(fù)雜度、空間復(fù)雜度及穩(wěn)定性等各項(xiàng)指標(biāo)。四、實(shí)驗(yàn)內(nèi)容在自己的U盤的“姓名+學(xué)號(hào)”文件夾中創(chuàng)建“實(shí)驗(yàn)16”文件夾，本次實(shí)驗(yàn)的所有程序和數(shù)據(jù)都要求存儲(chǔ)到本文件夾中。設(shè)計(jì)隨機(jī)數(shù)來(lái)測(cè)試排序算法運(yùn)行時(shí)間的程序，其中可以通過修改RANDNUM的值來(lái)更改測(cè)試的數(shù)據(jù)量。具體參考如下：#detineRANDNUM10000//隨機(jī)數(shù)的個(gè)數(shù)for（i=0;i<RANDNUM;i++）（//產(chǎn)生1萬(wàn)個(gè)隨機(jī)數(shù)iRandNum[i]=rand（）%RANDNUM;排序算法進(jìn)行測(cè)試（也和上一個(gè)實(shí)驗(yàn)結(jié)果進(jìn)行比較），記錄運(yùn)行時(shí)間;把需排序的數(shù)改為20000，進(jìn)行同樣測(cè)試，并比較測(cè)試結(jié)果。通過隨機(jī)的數(shù)據(jù)比較各算法的關(guān)鍵宇比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，取得直觀感受并分析算法各項(xiàng)性能指標(biāo)。（隨機(jī)數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生;至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換計(jì)為3次移動(dòng)））五、代碼如下#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<time.h>〃輔助函數(shù)，求數(shù)據(jù)的最大位數(shù)intmaxbit(intL[],intn)(intd=1,i=0;//保存最大的位數(shù)intp=10;for(i=0;i<n;i++)(while(L[i]>=p)(p*=10;d++;}}returnd;}〃基數(shù)排序voidradixsort(intL[],intlen)(intd=maxbit(L,len);long*tmp=(long*)malloc(len*sizeof(long));long*count=(long*)malloc(10*sizeof(long));;//計(jì)數(shù)器，10個(gè)桶l(fā)ongi,j,k;intradix=1;for(i=1;i<=d;i++)(〃進(jìn)行d次排序for(j=0;j<10;j++)//每次分配前清空計(jì)數(shù)器count[j]=0;for(j=0;j<len;j++)(〃統(tǒng)計(jì)每個(gè)桶中的記錄數(shù)k=(L[j]/radix)%10;count[k]++;}for(j=1;j<10;j++)//將tmp中的位置依次分配給每個(gè)桶count[j]=count[j-1]+count[j];for(j=len-1;j>=0;j--)(//將所有桶中記錄依次收集到tmp中k=(L[j]/radix)%10;count[k]--;tmp[count[k]]=L[j];}for(j=0;j<len;j++)//將臨時(shí)數(shù)組的內(nèi)容復(fù)制到L中L[j]=tmp[j];radix=radix*10;free(tmp);free(count);}intRandomInteger(longlow,longhigh)(longk;k=(long)(rand()%(high-low+1)+low);returnk;}voidzht_InsertSort(SqList*L)(/*對(duì)順序表L作直接插入排序。算法10.1*/ftime(&t1);inti,j,t;for(i=2;i<=(*L).length;++i)ifLT((*L).r[i].key,(*L).r[i-1].key)/*"<"，需將L.r[i]插入有序子表*/((*L).r[0]=(*L).r[i];/*復(fù)制為哨兵*/for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j)(*L).r[j+1]=(*L).r[j];/*記錄后移*/(*L).r[j+1]=(*L).r[0];/*插入到正確位置*/}ftime(&t2);t=(t2.time-t1.time)*1000+(litm);printf("直接插入排序用時(shí)%d毫秒\n",t);}voidzht_BInsertSort(SqList*L)(/*對(duì)順序表L作折半插入排序。算法10.2*/ftime(&t1);inti,j,m,low,high,t;for(i=2;i<=(*L).length;++i)((*L).r[0]=(*L).r[i];/*將L.r[i]暫存到L.r[0]*/low=1;high=i-1;while(low<=high)(/*在r[low..high]中折半查找有序插入的位置*/m=(low+high)/2;/*折半*/ifLT((*L).r[0].key,(*L).r[m].key)high=m-1;/*插入點(diǎn)在低半?yún)^(qū)*/elselow=m+1;/*插入點(diǎn)在高半?yún)^(qū)*/}for(j=i-1;j>=high+1;--j)(*L).r[j+1]=(*L).r[j];/*記錄后移*/(*L).r[high+1]=(*L).r[0];/*插入*/}ftime(&t2);t=(t2.time-t1.time)*1000+(litm);printf("折半插入排序用時(shí)%d毫秒\n",t);}intmain()(longi=0;long*L=(long*)malloc(10000*sizeof(long));clock_tstart,finish;doubleduration;srand((long)time(NULL));for(i=0;i<10000;i++)(L[i]=i;//RandomInteger(0,10000);}start=clock();radixsort(L,10000);finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;for(i=0;i<10000;i++)(printf("%7.2ld",L[i]);}printf("%5.4lfs”,duration);getchar();getchar();getchar();return0;}六、運(yùn)行結(jié)果截圖VD:\c語(yǔ)言儲(chǔ)伊題目\輸入100。膈誰(shuí)I對(duì)1皿0（］個(gè)數(shù)據(jù)進(jìn)行排序：蔓接拓?入排序用時(shí)54電秒I折半插入排序用時(shí)53亳秒2—路插入排序用時(shí)函0毫秒Processexitedafter7.024secondswithreturnvalue0E青按任意鍵繼續(xù)...七、實(shí)驗(yàn)總結(jié)與體會(huì)排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。直接插入排序：將一個(gè)記錄插入到已排序好的有序表中，從而得到一個(gè)新，記錄數(shù)增1的有序表。艮即先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹?。希爾排序：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。選擇排序：在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€(gè)數(shù)與第1個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最?。ɑ蛘咦畲螅┑呐c第2個(gè)位置的數(shù)交換，依次類推，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n個(gè)元素（最后一個(gè)數(shù)）比較為止。堆排序：初始時(shí)把要排序的n個(gè)