數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目利用隨機函數(shù)產(chǎn)生 3000030000 個隨機整數(shù),利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸弁排序等排序方法進行排序,統(tǒng)計每一種排序上機所花費的時間,弁和理論上時間進行比照分析.指導教師設(shè)計題目利用隨機函數(shù)產(chǎn)生30000個隨機整數(shù),利用插入排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進行排序,統(tǒng)計每一種排序上機所花費的時間,并和理論上時間進行比照分析.算法設(shè)計的思想1 .簡單項選擇擇排序操作方法：第一趟,從n個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換；第二趟,從第二個記錄開始的n-1個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；

2、如此,第i趟,那么從第i個記錄開始的n-i+1個記錄中選出關(guān)鍵碼最小的記錄與第i個記錄交換,直到整個序列按關(guān)鍵碼有序.【效率分析】空間效率：僅用了一個輔助單元.時間效率：簡單項選擇擇排序中,所需進行記錄移動的操作次數(shù)較小,其最小值為0,最大值為3(n-1).然而,無論記錄的初始排列如何,所需進行的關(guān)鍵字之間的比擬次數(shù)相同,均為n(n-1)/2.因此,總的時間復雜度也是O(n2).2 .直接插入排序設(shè)有n個記錄,存放在數(shù)組r中,重新安排記錄在數(shù)組中的存放順序,使得按關(guān)鍵碼有序.即r1.keyr2.keyrn.key先來看看向有序表中插入一個記錄的方法：設(shè)1j&n,r1.keyr2.keyr1.k

3、ey,將rj插入,重新安排存放順序,使得r1.keyr2.keytj,tk=1；2 .按步長序列個數(shù)k,對序列進行k趟排序；3 .每趟排序,根據(jù)對應的步長ti,將待排序列分割成假設(shè)干長度為m的子序列,分別對各子表進行直接插入排序.僅步長因子為1時,整個序列作為一個表來處理,表長度即為整個序列的長度.希爾排序時效分析很難,關(guān)鍵碼的比擬次數(shù)與記錄移動次數(shù)依賴于步長因子序列的選取,特定情況下可以準確估算出關(guān)鍵碼的比擬次數(shù)和記錄的移動次數(shù).目前還沒有人給出選取最好的步長因子序列的方法.步長因子序列可以有各種取法,有取奇數(shù)的,也有取質(zhì)數(shù)的,但需要注意：步長因子中除1外沒有公因子,且最后一個步長因子必須為

4、1.希爾排序方法是一個不穩(wěn)定的排序方法.4冒泡排序冒泡排序方法：對n個記錄的表,第一趟冒泡得到一個關(guān)鍵碼最大的記錄rn,第二趟冒泡對n-1個記錄的表,再得到一個關(guān)鍵碼最大的記錄rn-1,如此重復,直到n個記錄按關(guān)鍵碼有序的表.【效率分析】空間效率：僅用了一個輔助單元.時間效率：總共要進行n-1趟冒泡,對j個記錄的表進行一趟冒泡需要j-1次關(guān)鍵碼比擬.移動次數(shù)：最好情況下：待排序列已有序,不需移動.5快速排序快速排序是通過比擬關(guān)鍵碼、交換記錄,以某個記錄為界(該記錄稱為支點),將待排序列分成兩局部.其中,一局部所有記錄的關(guān)鍵碼大于等于支點記錄的關(guān)鍵碼,另一局部所有記錄的關(guān)鍵碼小于支點記錄的關(guān)鍵碼

5、.我們將待排序列按關(guān)鍵碼以支點記錄分成兩局部的過程,稱為一次劃分.對各局部不斷劃分,直到整個序列按關(guān)鍵碼有序.【效率分析】空間效率：快速排序是遞歸的,每層遞歸調(diào)用時的指針和參數(shù)均要用棧來存放,遞歸調(diào)用層次數(shù)與上述二叉樹的深度一致.因而,存儲開銷在理想情況下為O(log2n),即樹的高度；在最壞情況下,即二叉樹是一個單鏈,為O(n).時間效率：在n個記錄的待排序列中,一次劃分需要約n次關(guān)鍵碼比擬,時效為O(n),假設(shè)設(shè)T(n)為對n個記錄的待排序列進行快速排序所需時間.理想情況下：每次劃分,正好將分成兩個等長的子序列,那么T(n)cn+2T(n/2)c是一個常數(shù)cn+2(cn/2+2T(n/4)

6、=2cn+4T(n/4)2cn+4(cn/4+T(n/8)=3cn+8T(n/8)cnlog2n+nT(1)=O(nlog2n)最壞情況下：即每次劃分,只得到一個子序列,時效為O(n2).快速排序是通常被認為在同數(shù)量級(O(nlog2n)的排序方法中平均性能最好的.但假設(shè)初始序列按關(guān)鍵碼有序或根本有序時,快排序反而蛻化為冒泡排序.為改良之,通常以“三者取中法來選取支點記錄,即將排序區(qū)間的兩個端點與中點三個記錄關(guān)鍵碼居中的調(diào)整為支點記錄.快速排序是一個不穩(wěn)定的排序方法.6 6 .堆排序堆排序的時間,主要由建立初始堆和反復重建堆這兩局部的時間開銷構(gòu)成,它們均是通過調(diào)用Heapify實現(xiàn)的.堆排序的

7、最壞時間復雜度為O(nlogn)o堆序的平均性能較接近于最壞性能.由于建初始堆所需的比擬次數(shù)較多,所以堆排序不適宜于記錄數(shù)較少的文件.堆排序是就地排序,輔助空間為O(1),它是不穩(wěn)定的排序方法.7 7 .歸弁排序歸并操作的工作原理如下：申請空間,使其大小為兩個已經(jīng)排序序列之和,該空間用來存放合并后的序列,設(shè)定兩個指針,最初位置分別為兩個已經(jīng)排序序列的起始位置.比擬兩個指針所指向的元素,選擇相對小的元素放入到合并空間,并移動指針到下一位置.重復步驟3直到某一指針到達序列尾,將另一序列剩下的所有元素直接復制到合并序列尾.速度僅次于快速排序,但較穩(wěn)定.歸并排序的時間復雜度為O(nlogn).三、算法

8、設(shè)計分析程序總體采用分塊化設(shè)計,每種排序的函數(shù)都以其相應的名字保存,在主程序調(diào)用時用#include#include“*cpp*cpp調(diào)用.這樣的總體布局將各個功能隔離開來,每個模塊負責每個模塊的功能,使得程序的布局簡單明了且子程序只有在被調(diào)用時才會運行大大節(jié)約系統(tǒng)資源減少了運算時間.同時由于功能的隔離使得程序的擴展性大大提升,無論程序?qū)⒁魏胃膭訒r,都會方便很多.源代碼“.cpp.cpp保存,其他子函數(shù)分別保存,以下是主函數(shù)的代碼.#include#include#include#include快速排序.cpp#include堆排序.cpp#include直接插入排序.cpp#include

9、選擇排序.cpp#include冒泡排序.cpp#include希爾排序.cpp#include歸并排序.cppusingnamespacestd;intmain()clock_tstart,finish;inti,time1,time2,time3,time4,time5,time6,time7;inta30000,b30000;srand(time(0);for(i=0;i30000;i+)ai=rand();cout*n;coutt選擇排序n;cout*n;for(i=0;i30000;i+)bi=ai;start=clock();choices_sort(b);finish=clock

10、();time1=finish-start;printf(選擇排序耗時%d毫秒!nnn,time1);cout*n;coutt直接插入排序n;cout*n;for(i=0;i30000;i+)bi=ai;start=clock();direct(b);finish=clock();time2=finish-start;printf(直接插入排序耗時%d毫秒!nnn,time2);cout*n;coutt堆排序n;cout*n;for(i=0;i30000;i+)bi=ai;start=clock();heap_sort(b,30000);finish=clock();time3=finish-

11、start;printf(堆排序耗時%d毫秒!nnn,time3);cout*n;coutt快速排序n;cout*n;for(i=0;i30000;i+)bi=ai;start=clock();sort(b,0,29999);finish=clock();time4=finish-start;printf(快速排序耗時%d毫秒!nnn,time4);cout*n;coutt冒泡排序n;cout*n;for(i=0;i30000;i+)bi=ai;start=clock();bubble_sort(b);finish=clock();time5=finish-start;printf(冒泡排序耗

12、時%d毫秒!nnn,time5);cout*n;coutt希爾排序n;cout*n;for(i=0;i30000;i+)bi=ai;start=clock();shellsort(b,30000);finish=clock();time6=finish-start;printf(希爾排序耗時%d毫秒!nnn,time6);cout*n;coutt歸并排序n;cout*n;for(i=0;i30000;i+)bi=ai;start=clock();MergeSort(b,0,29999);finish=clock();time7=finish-start;printf(歸并排序耗時%d毫秒!nn

13、n,time7);getch();return0;以下是直接插入排序的函數(shù),以“直接插入排序.cpp.cpp保存#include#includeusingnamespacestd;voiddirect(inta)inti,j,w;for(i=0;i=0;j-)if(aj=aj+1)w=aj;aj=aj+1;aj+1=w;以下是選擇排序的函數(shù),以“選擇排序.cpp.cpp保存#include#includeusingnamespacestd;voidchoices_sort(inta)inti,j,k,t;for(i=0;i30000;i+)k=i;for(j=i+1;jaj)k=j;t=ai;

14、ai=ak;ak=t;以下是冒泡排序的函數(shù),以“冒泡排序.cpp.cpp保存#include#includeusingnamespacestd;voidbubble_sort(inta)inti,j,w;for(i=0;i30000;i+)for(j=0;jaj+1)w=aj;aj=aj+1;aj+1=w;以下是希爾排序的函數(shù),以“希爾排序.cpp.cpp保存#include#include#includeusingnamespacestd;voidshellsort(inta,intn)intd,i,j,temp;for(d=n/2;d=1;d=d/2)for(i=d;i=0)&(ajtem

15、p);j=j-d)aj+d=aj;aj+d=temp;以下是快速排序的函數(shù),以“快速排序.cpp.cpp保存#include#includeusingnamespacestd;voidsort(inta,intx,inty)intxx=x,yy=y;intk=ax;if(x=y)return;while(xx!=yy)while(xx=k)yy-;axx=ayy;while(xxyy&axx=k)xx+;ayy=axx;axx=k;sort(a,x,xx-1);sort(a,xx+1,y);以下是堆排序的函數(shù),以“堆排序#include#include#includeusingnamespac

16、estd;voidsift(int*x,intn,ints)intt,k,j;t=*(x+s);k=s;j=2*k+1;while(jn)if(jn-1&*(x+j)*(x+j+1)就繼續(xù)下一輪比擬,否那么調(diào)整.*/j+;if(t=0;i-)sift(x,n,i);for(k=n-1;k=1;k-)t=*(x+0);*(x+0)=*(x+k);*(x+k)=t;sift(x,k,0);以下是歸并排序的函數(shù),以“歸并排序.cpp.cpp保存#include#includeusingnamespacestd;voidMerge(int*R,intlow,intm,inthigh)inti=low,

17、j=m+1,p=0;int*R1;R1=(int*)malloc(high-low+1)*sizeof(int);if(!R1)return;while(i=m&j=high)R1p+=(Ri=Rj)?Ri+:Rj+;while(i=m)R1p+=Ri+;while(j=high)R1p+=Rj+;for(p=0,i=low;i=high;p+,i+)Ri=R1p;voidMergeSort(intR,intlow,inthigh)intmid;/*開始元素放到它正確位/*初始建堆*/*堆頂放到最后*/*剩下的數(shù)再建堆*/if(lowhigh)mid=(low+high)/2;MergeSor

18、t(R,low,mid);MergeSort(R,mid+1,high);Merge(R,low,mid,high);五、運行結(jié)果分析直接排序排序所用時間冒泡排序所用時間選擇排序所用時間快速排序所用時間堆排序所用時間歸弁排序希爾排序直接排序冒泡排序選擇排序快速排序堆排序歸陽卜序希爾排序理論時問O(nxn)O(nxn)O(nxn)O(nLogn)O(nLogn)O(nLogn)O(nLogn)上機時問4563豪秒4884豪秒1953豪秒6豪秒9毫秒秒16豪秒12毫秒通過實驗數(shù)據(jù),可以看出 O(nLogn)O(nLogn)的幾種排序算法確實比 O(nxn)O(nxn)的算法要快很多.快速排序確實是最快的.比同級的歸并排序和堆排