數(shù)據(jù)結(jié)構(gòu)排序算法綜合試驗(yàn)

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)排序算法綜合試驗(yàn)排序算法綜合試驗(yàn)

：

一、試驗(yàn)?zāi)康?/p>

通過上機(jī)來體驗(yàn)和把握課本的有關(guān)基本知識，加深對排序算法的認(rèn)識。

二、試驗(yàn)要求

1．實(shí)現(xiàn)基本排序方法：直接插入、希爾、直接選擇、冒泡、快速、堆、二路歸并；2．每種基本排序方法盡量給出多種實(shí)現(xiàn)（包括改進(jìn)）；3．給出試驗(yàn)結(jié)果：

445

（1）隨機(jī)生成若干個隨機(jī)數(shù)進(jìn)行排序（如n＝10，2＊10，10，?等），記錄每個排序的時間花費(fèi)（絕對時間？規(guī)律時間（關(guān)鍵字比較次數(shù)，移動次數(shù)）？）。

4

（2）分別給出正序和反序的初始序列進(jìn)行排序（如n＝10），檢驗(yàn)算法對初始序列的敏感程度。

（3）給出試驗(yàn)結(jié)果、原因分析、結(jié)論等（如改進(jìn)效果明顯或不明顯的原因？算法的實(shí)際時間增長速度如何？繁雜性相當(dāng)?shù)乃惴ㄖg快慢如何？等等）。（4）所有試驗(yàn)結(jié)果匯集成一張表。

三、幾種排序算法

1、直接插入排序1.1原理

在排序過程中，每次都將無序區(qū)中第1條記錄插入到有序區(qū)中適當(dāng)位置，使其仍保持有序。初始時，取第1條記錄為有序區(qū)，其他記錄為無序區(qū)。隨著排序過程的進(jìn)行，有序區(qū)不斷擴(kuò)大，無序區(qū)不斷縮小。最終無序區(qū)為空，有序區(qū)包含了全部記錄，排序終止。

1.2算法

1.2.1帶監(jiān)視哨

//直接插入排序，帶監(jiān)視哨(并不改變關(guān)鍵字次數(shù))voidInsertSort1(listR,intn){inti,j;

for(i=2;i=R[i-1].key)continue;

//R[i]大于有序區(qū)最終一個記錄，則本趟不需插入MPP,R[0]=R[i];//R[0]是監(jiān)視哨j=i-1;

do{//查找R[i]的插入位置MPP,R[j+1]=R[j];j--;//記錄后移，繼續(xù)向前探尋}while(CPP,R[0].key=R[i-1].key)continue;

MPP,x=R[i];//待排記錄暫存到xj=i-1;

do{//順序比較和移動MPP,R[j+1]=R[j];j--;

}while(j>=1MPP,R[j+1]=x;//插入R[i]}}

1.2.3改進(jìn)：在查找插入位置時采用二分查找，即二分插入排序voidInsertSort3(listR，intn){inti，j，low，high，mid;for(i=2;i=R[i-1].key)continue;//R[i]大于有序區(qū)最終一個記錄，不需插入MPP，R[0]=R[i];low=1;high=i-1;while(low=high+1;j--)MPP，R[j+1]=R[j];//記錄后移MPP，R[high+1]=R[0];}}

2、希爾排序2.1原理

將數(shù)據(jù)表分成若干組，所有相隔為某個“增量〞的記錄為一組，在各組內(nèi)進(jìn)行直接插入排序；初始時增量d1較大，分組較多（每組的記錄數(shù)少），以后增量逐漸減少，分組減少（每組的記錄數(shù)增多），直到最終增量為1（d1>d2>...>dt=1），所有記錄為同一組，再整體進(jìn)行一次直接插入排序。

2.2算法

voidShellSort(listR，intn){inth，i，j，k;for(h=n/2;h>=1;h=h/2){for(i=1;i=R[j-h].key)continue;//R[j]大于有序區(qū)最終一個記錄，

則不需要插入MPP，R[0]=R[j];//R[0]保存待插入記錄，但不是監(jiān)視哨k=j-h;//待插記錄的前一個記錄do{//查找正確的插入位置MPP，R[k+h]=R[k];k=k-h;//后移記錄，繼續(xù)向前探尋}while(k>0MPP，R[k+h]=R[0];//插入R[j]}}if(h==1)break;}}

3、直接選擇排序3.1原理

首先，所有記錄組成初始無序區(qū)R[1]~R[n]，從中選出最小的記錄，與無序區(qū)第一個記錄R[1]交換；新的無序區(qū)為R[2]~R[n]，從中再選出最小的記錄，與無序區(qū)第一個記錄R[2]交換；類似，第i趟排序時R[1]~R[i-1]是有序區(qū)，無序區(qū)為R[i]~R[n]，從中選出最小的記錄，將它與無序區(qū)第一個記錄R[i]交換，R[1]~R[i]為新的有序區(qū)。由于沒糖排序都使有序區(qū)中增加一個記錄，所以，進(jìn)行n-1趟排序后，整個數(shù)據(jù)表就全部有序了。

3.2算法

voidSelectSort(listR，intn){inti，j，k;for(i=1;i=i+1;j--)//從下向上掃描

if(CPP，R[j].keyR[j+1].key){//交換記錄flag=1;

MP3，x=R[j];R[j]=R[j+1];R[j+1]=x;//交換}

if(!flag)break;//本趟未交換過記錄，排序終止}}

4.3.3改進(jìn)：雙向冒泡排序，每趟排序同時使輕氣泡向上“漂泊〞，重氣泡向下“漂泊〞voidBubbleSort3(listR，intn){//雙向冒泡排序inti，j，k，flag;rectypex;i=1;j=n;while(i=i+1;k--)//從下向上掃描if(CPP，R[k].keyR[k+1].key){//交換記錄flag=1;MP3，x=R[k];R[k]=R[k+1];R[k+1]=x;}if(!flag)break;j--;}

}

5、快速排序5.1原理

在數(shù)據(jù)表中任取一個作為“基準(zhǔn)〞，將其余記錄分為兩組，第一組找那個個記錄均小于或等于基準(zhǔn)，其次組中個記錄均大于或等于基準(zhǔn)，而基準(zhǔn)就排在這兩組中間（這也是該記錄的最終位置），這稱為一趟快速排序（或一次劃分）。對所分的兩組記錄分別重復(fù)上述方法，直到每組只有1個記錄為止。

5.2算法

5.2.1一趟劃分算法

intPartition(listR，intp，intq){//對R[p]到R[q]劃分，返回基準(zhǔn)位置inti，j;rectypex;//輔助量(可用R[0]代替)

i=p;j=q;MPP，x=R[p];//x存基準(zhǔn)(無序區(qū)第一個記錄)do{

while((CPP，R[j].key>=x.key)//從右向左掃描(取消=變快)if(i=t)return;//只有一個記錄或無記錄時無需排序i=Partition(R，s，t);//對R[s]到R[t]做劃分QuickSort1(R，s，i-1);//遞歸處理左區(qū)間QuickSort1(R，i+1，t);//遞歸處理右區(qū)間}

6、堆排序6.1原理

將待排序的記錄序列建成一個堆，并借助于堆的性質(zhì)進(jìn)行的排序方法就是堆排序。它的原理：將原始的n個記錄序列建成一個大根堆，稱為初始堆，然后將它的根和最終的元素交換，除此之外的n-1個記錄序列再重復(fù)上面的操作，直到記錄序列為一個遞增的序列。因此，堆排序的操作分為建立初始堆和用堆進(jìn)行排序兩步操作。

6.2算法

6.2.1建立初始堆算法

非遞歸算法

voidSift1(listR，intp，intq)//堆范圍為R[p]~R[q]，調(diào)整R[p]為堆{intj;

MPP，R[0]=R[p];//R[0]作輔助量j=2*p;while(j=R[j].key)break;//跟結(jié)點(diǎn)鍵值大于孩子結(jié)點(diǎn)，已經(jīng)是堆，調(diào)整終止MPP，R[p]=R[j];//將R[j]換到雙親位置上p=j;//修改當(dāng)前被調(diào)整結(jié)點(diǎn)j=2*p;//j指向R[p]的左孩子}MPP，R[p]=R[0];}

遞歸算法

voidSift2(listR，intp，intq)//堆范圍為R[p]~R[q]，調(diào)整R[p]為堆{intj;if(p>=q)return;//只有一個元素j=2*p;if(j>q)return;if(j=R[j].key)return;//根結(jié)點(diǎn)關(guān)鍵字已最大MPP，R[0]=R[j];//交換R[j]和R[p]，R[0]作輔助量MPP，R[j]=R[p];MPP，R[p]=R[0];Sift2(R，j，q);}

6.2.2堆排序算法

voidHeapSort(listR，intn)//堆排序主程序{inti;for(i=n/2;i>=1;i--)Sift1(R，i，n);//建初始堆for(i=n;i>=2;i--){//進(jìn)行n-1趟堆排序MPP，R[0]=R[1];//堆頂和當(dāng)前堆底交換，R[0]作輔助量MPP，R[1]=R[i];MPP，R[i]=R[0];Sift1(R，1，i-1);}

7、二路歸并排序7.1原理

將待排序記錄R[0]到R[n-1]看成n個長度為1的有序子序列區(qū)，從第一個子序列開始，

把相鄰的子序列兩兩歸并，便得到[n/2]（取整數(shù)）個長度為2或1有序的子序列。然后再把這[n/2]個有序的子序列利用上面的方法兩兩歸并，如此反復(fù)，直到最終得到一個長度為n的有序序列。

7.2算法

7.2.1一趟歸并算法

voidMerge(listR，listR1，intlow，intmid，inthigh){

//合并R的兩個子表：R[low]~R[mid]、R[mid+1]~R[high]，結(jié)果在R1中inti，j，k;i=low;j=mid+1;k=low;

while(i#include#include#include

#defineCPPC++#defineMPPM++#defineMP2M+=2#defineMP3M+=3

constintd=3;constintr=10;

constintmaxsize=100000;//數(shù)據(jù)表容量typedefintdatatype;typedefstruct{intf,e;}queue;

typedefstruct{

datatypekey;//關(guān)鍵字域datatypekey1[d];intnext;

}rectype;//記錄類型

typedefrectypelist[maxsize+2];//數(shù)據(jù)表類型，0號單元不用

__int64C,M;//比較和移動次數(shù)

voidcheck(listR,intn){//檢驗(yàn)排序結(jié)果inti;

for(i=2;i=R[i-1].key)continue;

//R[i]大于有序區(qū)最終一個記錄，則本趟不需插入MPP,R[0]=R[i];//R[0]是監(jiān)視哨j=i-1;

do{//查找R[i]的插入位置MPP,R[j+1]=R[j];j--;//記錄后移，繼續(xù)向前探尋}while(CPP,R[0].key=R[i-1].key)continue;

MPP,x=R[i];//待排記錄暫存到xj=i-1;

do{//順序比較和移動MPP,R[j+1]=R[j];j--;

}while(j>=1MPP,R[j+1]=x;//插入R[i]}}

voidShellInsert(listR,intn,inth){inti,j,k;for(i=1;i=R[j-h].key)continue;MPP,R[0]=R[j];k=j-h;

do{MPP,R[k+h]=R[k];k=k-h;}while(CPP,k>0MPP,R[k+h]=R[0];}}

voidShellSort(listR,intn)//希爾排序{inth=n/2;while(h>=1)//各趟插入排序{ShellInsert(R,n,h);h=h/2;//縮小增量}}

//上升法冒泡排序

voidBubbleSort1(listR,intn){

inti,j,flag;rectypex;//x為輔助量(可用R[0]代替)for(i=1;i=i+1;j--)//從下向上掃描if(CPP,R[j].keyR[j+1].key){//交換記錄flag=1;

MP3,x=R[j];R[j]=R[j+1];R[j+1]=x;//交換}

if(!flag)break;//本趟未交換過記錄，排序終止}}

//快速排序，遞歸算法

intPartition(listR,intp,intq){//對R[p]到R[q]劃分，返回基準(zhǔn)位置inti,j;rectypex;//輔助量(可用R[0]代替)

i=p;j=q;MPP,x=R[p];//x存基準(zhǔn)(無序區(qū)第一個記錄)do{

while((CPP,R[j].key>=x.key)//從右向左掃描(取消=變快)if(i=t)return;//只有一個記錄或無記錄時無需排序i=Partition(R,s,t);//對R[s]到R[t]做劃分QuickSort1(R,s,i-1);//遞歸處理左區(qū)間QuickSort1(R,i+1,t);//遞歸處理右區(qū)間}

//歸并排序

voidMerge(listR,listR1,intlow,intmid,inthigh){

//合并R的兩個子表：R[low]~R[mid]、R[mid+1]~R[high]，結(jié)果在R1中inti,j,k;i=low;j=mid+1;k=low;

while(i=R[j].key)break;R[i]=R[j];i=j;j=2*i;}R[i]=R[0];}

voidHeapSort(listR,intn)//堆排序主程序{inti;for(i=n/2;i>=1;i--)Sift(R,i,n);for(i=n;i>=2;i--){MP3,R[0]=R[1];R[1]=R[i];R[i]=R[0];Sift(R,1,i-1);}}

//選擇排序

voidSelectSort(listR,intn){inti,j,k;for(i=1;i=0)x=x1;elsex=x1+M;returnx;}

intmain(){

rectype*R,*R1,*S;//R1用于歸并排序的輔助存儲，S用于保存初始排序數(shù)據(jù)R=newlist;if(R==NULL){cout>choice;switch(choice){case11:

t1=clock();

InsertSort1(R,n);t2=clock();break;case12:

t1=clock();

InsertSort2(R,n);t2=clock();break;case21:

\\n\\\\n\\\\n\\\\n\\\\n\\\\n\\\\n\\\\n\t1=clock();

BubbleSort1(R,n);t2=clock();break;case22:

t1=clock();

BubbleSort2(R,n);t2=clock();break;case31:

t1=clock();

QuickSort1(R,1,n);t2=clock();break;case41:

t1=clock();

MergeSort(R,R1,n);t2=clock();break;case51:

t1=clock();HeapSort(R,n);t2=clock();break;case61:

t1=clock();

SelectSort(R,n);t2=clock();break;case71:

t1=clock();ShellSort(R,n);t2=clock();break;default:;}

check(R,n);//disp(R,n);

cout

五、試驗(yàn)結(jié)果與分析

1、試驗(yàn)結(jié)：

試驗(yàn)數(shù)據(jù)結(jié)果匯總表：

CPU內(nèi)存主板AMDA6-3420MAPUwithRadeon(tm)HDGraphics四核姓名李宇7.48GB華碩K53TK學(xué)號202331190310班級電信4班電mailliandyu2023@163.com操作系統(tǒng)Windows8專業(yè)版(Build9200),64-bit編譯軟C-free5.0件10^42*10^410^52*10^510^62*10^610^72*10^10^810^57正序逆序24.87100.12500.C4583直接插入40.99(帶監(jiān)視哨）t(時間)0.4041.665324.87100.12500.C4583直接插入40.46(無監(jiān)視哨）t0.3881.586849.99199.94999.冒泡（上C058594升）129.1t1.2555.0884549.99199.94999.C04678128.6冒泡（下降）t1.2465.198710.1700.3662速（遞歸）9995.6166.4329995.6166.07519999.9517.74119999.9>5min>5min>5min堆排序(非遞歸)二路歸并Ct選擇排序C522.9>5min4.79625.8157.66320.8647.446256865411.250.0030.0070.0390.0830.460.9955.50210.1230.2671.5663.33318.7139.43224.0468.06836151.056619020614.090.0030.0080.0490.0990.5071.1846.45640.0290.0590.2990.599997997997997000015.1033.630.0040.010.0690.1370.9472.189840.0770.1681.0102.15588222.4t63>5min9.71071.01167.91089.2471.C048731573828.8565.22希爾排序t0.0050.0140.1090.2441.824.24344當(dāng)數(shù)據(jù)表容量為10^8時系統(tǒng)出現(xiàn)問題。524506555.620.5132.05940.2660.6084.3417116765

2、試驗(yàn)分析2.1直接插入排序該算法雖然簡單，但效率不高。由匯總表的數(shù)據(jù)可以看出，若初始數(shù)據(jù)為正序，總的關(guān)鍵字比較次數(shù)為最小，并且總的移動次數(shù)為0；若初始數(shù)據(jù)為逆序，總的比較次數(shù)達(dá)到最大值O（n2）；所以，算法對初始序列的敏感程度很大。由于該算法的時間繁雜度為O（n2），所以其對大規(guī)模的數(shù)據(jù)排序的效率很低，改進(jìn)后的二分插入算法并沒有改變總的比較次數(shù)，只是總的時間變小了，效率有所改進(jìn)。

2.2冒泡排序若初始數(shù)據(jù)為正序，則一趟掃描就可以完成排序，關(guān)鍵字的比較次數(shù)為n-1，沒有移動次數(shù)，即在最好的狀況下，冒泡排序的時間繁雜度為O（n）；若初始數(shù)據(jù)為逆序，則比較次數(shù)和移動次數(shù)均達(dá)到最大值，最壞時間繁雜度為O（n2）。由匯總表可看出，該算法對于數(shù)據(jù)量大的排序的效率是很低的，使用改進(jìn)的雙向冒泡法進(jìn)行排序時，效率有所改進(jìn)，但仍為O（n2）。

2.3快速排序由匯總表中的正序和逆序數(shù)據(jù)可以看出，該算法對基本有序的初始記錄進(jìn)行排序的效率是很低的，其對初始序列的敏感程度大?？焖倥判虻钠骄鶗r間繁雜度約為1.39nlog2n，而且在所有排序方法當(dāng)中的速度是最快的，特別是在處理大規(guī)模無序數(shù)據(jù)時，其優(yōu)勢更為明顯。

2.4二路歸并由匯總表可以看出，算法對初始序列的敏感程度