北郵數(shù)據(jù)結(jié)構(gòu)第四次試驗(yàn)題目一排序

本文格式為Word版，下載可任意編輯——北郵數(shù)據(jù)結(jié)構(gòu)第四次試驗(yàn)題目一排序北京郵電大學(xué)信息與通信工程學(xué)院

數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報告

試驗(yàn)名稱：試驗(yàn)四排序（題目1）

姓名：

班級：

班內(nèi)序號：

學(xué)號：

第1頁

北京郵電大學(xué)信息與通信工程學(xué)院

1．試驗(yàn)要求

試驗(yàn)?zāi)康模簩W(xué)習(xí)、實(shí)現(xiàn)、對比各種排序算法，把握各種排序算法的優(yōu)劣，以及各種算法使用的狀況。試驗(yàn)內(nèi)容：使用簡單數(shù)組實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法：

1、插入排序2、希爾排序3、冒泡排序4、快速排序5、簡單項選擇擇排序要求：

1、測試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)

2、對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)（其中關(guān)鍵字交換計為3次移動）。

3、對2的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的時間繁雜度。

編寫測試main()函數(shù)測試線性表的正確性。

2.程序分析

2.1存儲結(jié)構(gòu)

程序采用的存儲機(jī)構(gòu)是順序存儲，如下圖所示：a[0]

a[1]a[2]a[3]a[4]a[5]a[6]a[7]2.2關(guān)鍵算法分析

2.2.1插入排序

插入排序的基本方法是尋覓一個指定元素在待排序元素中的位置，然后插入。一趟直接插入排序的C++描述過程如下：

①將待插入紀(jì)錄賦值給哨兵r[0]：r[0]=r[i];

②從后向前進(jìn)行順序查找：for(j=i-1;r[0]=1;d=d/2)//以d為增量在子序列中進(jìn)行插入排序{

for(inti=d+1;i0j=j-d)//每隔d個記錄，進(jìn)行一次比較和移動，d=1

時即是最終一趟直接插入排序

{r[j+d]=r[j];comp++;move++;}

第3頁

北京郵電大學(xué)信息與通信工程學(xué)院

comp++;//比較計數(shù)器++

r[j+d]=r[0];move++;//移動計數(shù)器++

}

comp++;//比較計數(shù)器++

}}

coutr[i+1])//相鄰元素比較{

2r[0]=r[i];r[i]=r[i+1];

r[i+1]=r[0];//若逆序，則交換move+=3;pos=i;

第4頁

北京郵電大學(xué)信息與通信工程學(xué)院

}comp++;}

comp++;}

cout北京郵電大學(xué)信息與通信工程學(xué)院

}

{i++;Ecomp++;}Ecomp++;//從左邊開始找到第一個大于軸值的數(shù)r[j]=r[i];Emove++;}

r[i]=pivot;Emove++;returni;

//完整快速排序

voidQSort(intr[],inti,intj)//遞歸直到序列有序{

staticconstintn=j;if(i

第9頁

北京郵電大學(xué)信息與通信工程學(xué)院

#includeusingnamespacestd;//直接插入排序

voidInsertSort(intr[],intn){intcomp=0;//比較次數(shù)計數(shù)器intmove=0;//移動次數(shù)計數(shù)器for(inti=2;i=1;d=d/2)//以d為增量在子序列中進(jìn)行插入排序{for(inti=d+1;i0j=j-d)//每隔d個記錄，進(jìn)行一次比較和移動，d=1時即是最終一趟直接插入排序

{r[j+d]=r[j];comp++;move++;}comp++;//比較計數(shù)器++r[j+d]=r[0];move++;//移動計數(shù)器++}comp++;//比較計數(shù)器++

第10頁

北京郵電大學(xué)信息與通信工程學(xué)院

}}coutr[i+1])//相鄰元素比較{r[0]=r[i];r[i]=r[i+1];r[i+1