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

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

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

題目利用隨機(jī)函數(shù)產(chǎn)生30000個(gè)隨機(jī)整數(shù)，利用插入排序、

希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序

等排序方法進(jìn)行排序，統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間，并和

理論上時(shí)間進(jìn)行對(duì)比分析。

學(xué)

名

生姓

號(hào)

學(xué)

院

學(xué)

業(yè)

專

指導(dǎo)教師

年月目

一、設(shè)計(jì)題目

利用隨機(jī)函數(shù)產(chǎn)生30000個(gè)隨機(jī)整數(shù)，利用插入排序、起泡排序、快

速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，統(tǒng)計(jì)每

一種排序上機(jī)所花費(fèi)的時(shí)間，并和理論上時(shí)間進(jìn)行對(duì)比分析。

二、算法設(shè)計(jì)的思想

1.簡(jiǎn)單選擇排序

操作方法：第一趟，從n個(gè)記錄中找出關(guān)鍵碼最小的記錄與第一個(gè)記錄交換；第

二趟，從第二個(gè)記錄開始的n-1個(gè)記錄中再選出關(guān)鍵碼最小的記錄與第二個(gè)記錄

交換；如此，第i趟，則從第i個(gè)記錄開始的n-i+1個(gè)記錄中選出關(guān)鍵碼最小的

記錄與第i個(gè)記錄交換，直到整個(gè)序列按關(guān)鍵碼有序。

【效率分析】

空間效率：僅用了一個(gè)輔助單元。

時(shí)間效率：簡(jiǎn)單選擇排序中，所需進(jìn)行記錄移動(dòng)的操作次數(shù)較小，其最小值為0,

最大值為3(n-l)o然而，無論記錄的初始排列如何，所需進(jìn)行的關(guān)鍵字之間的

比較次數(shù)相同，均為n(n-l)/2o因此，總的時(shí)間復(fù)雜度也是O(n2)o

2.直接插入排序

設(shè)有n個(gè)記錄，存放在數(shù)組r中，重新安排記錄在數(shù)組中的存放順序，使得按關(guān)

鍵碼有序。即r[1].key^r[2].key.......Wr[n].key

先來看看向有序表中插入一個(gè)記錄的方法：

設(shè)IcjWn,r[l].keyWr[2].keyW.......<rfj-l].key,將r[j]插入,重新安排存放

順序，使得r[l].key^r[2].key^.......Wr[j].key,得到新的有序表，記錄數(shù)增1。

【效率分析】

空間效率：僅用了一個(gè)輔助單元。

1文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

時(shí)間效率：向有序表中逐個(gè)插入記錄的操作，進(jìn)行了n-l趟，每趟操作分為比較

關(guān)鍵碼和移動(dòng)記錄，而比較的次數(shù)和移動(dòng)記錄的次數(shù)取決于待排序列按關(guān)鍵碼的

初始排列。

最好情況下：即待排序列已按關(guān)鍵碼有序，每趟操作只需1次比較2次移動(dòng)。

總比較次數(shù)=n-l次

總移動(dòng)次數(shù)=2(n-l)次

最壞情況下：即第j趟操作，插入記錄需要同前面的j個(gè)記錄進(jìn)行j次關(guān)鍵碼比

較，移動(dòng)記錄的次數(shù)為j+2次。

平均情況下：即第j趟操作，插入記錄大約同前面的j/2個(gè)記錄進(jìn)行關(guān)鍵碼比較，

移動(dòng)記錄的次數(shù)為j/2+2次。

由此，直接插入排序的時(shí)間復(fù)雜度為O(n2)。是一個(gè)穩(wěn)定的排序方法

3.希爾排序(Shell'sSort)

直接插入排序算法簡(jiǎn)單，在n值較小時(shí)，效率比較高，在n值很大時(shí)，若序列按

關(guān)鍵碼基本有序，效率依然較高，其時(shí)間效率可提高到0(n)。希爾排序即是從

這兩點(diǎn)出發(fā)，給出插入排序的改進(jìn)方法。

希爾排序方法：

1.選擇一個(gè)步長(zhǎng)序列tl,t2,???,tk,其中ti>tj,tk=l；

2.按步長(zhǎng)序列個(gè)數(shù)k,對(duì)序列進(jìn)行k趟排序；

3.每趟排序，根據(jù)對(duì)應(yīng)的步長(zhǎng)ti,將待排序列分割成若干長(zhǎng)度為m的子序列，

分別對(duì)各子表進(jìn)行直接插入排序。僅步長(zhǎng)因子為1時(shí)，整個(gè)序列作為一個(gè)表來處

理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

希爾排序時(shí)效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動(dòng)次數(shù)依賴于步長(zhǎng)因子序列的

選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動(dòng)次數(shù)。目前還沒

有人給出選取最好的步長(zhǎng)因子序列的方法。步長(zhǎng)因子序列可以有各種取法，有取

奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：步長(zhǎng)因子中除1外沒有公因子，且最后一

個(gè)步長(zhǎng)因子必須為k希爾排序方法是一個(gè)不穩(wěn)定的排序方法。4.冒

泡排序

冒泡排序方法：對(duì)n個(gè)記錄的表，第一趟冒泡得到一個(gè)關(guān)鍵碼最大的記錄r[n],

第二趟冒泡對(duì)n-l個(gè)記錄的表，再得到一個(gè)關(guān)鍵碼最大的記錄rfn-1],如此重復(fù)，

直到n個(gè)記錄按關(guān)鍵碼有序的表。

【效率分析】

空間效率：僅用了一個(gè)輔助單元。

時(shí)間效率：總共要進(jìn)行n-l趟冒泡，對(duì)j個(gè)記錄的表進(jìn)行一趟冒泡需要j-1次關(guān)

鍵碼比較。

移動(dòng)次數(shù)：

最好情況下：待排序列已有序，不需移動(dòng)。

5.快速排序

快速排序是通過比較關(guān)鍵碼、交換記錄，以某個(gè)記錄為界(該記錄稱為支點(diǎn))，將

待排序列分成兩部分。其中，一部分所有記錄的關(guān)鍵碼大于等于支點(diǎn)記錄的關(guān)鍵

碼，另一部分所有記錄的關(guān)鍵碼小于支點(diǎn)記錄的關(guān)鍵碼。我們將待排序列按關(guān)鍵

碼以支點(diǎn)記錄分成兩部分的過程，稱為一次劃分。對(duì)各部分不斷劃分，直到整個(gè)序

列按關(guān)鍵碼有序。

【效率分析】

空間效率：快速排序是遞歸的，每層遞歸調(diào)用時(shí)的指針和參數(shù)均要用棧來存放，

2文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

遞歸調(diào)用層次數(shù)與上述二叉樹的深度一致。因而，存儲(chǔ)開銷在理想情況下為

O(log2n),即樹的高度；在最壞情況下，即二叉樹是一個(gè)單鏈，為0(n)。

時(shí)間效率：在n個(gè)記錄的待排序列中，一次劃分需要約n次關(guān)鍵碼比較，時(shí)效為

0(n),若設(shè)T(n)為對(duì)n個(gè)記錄的待排序列進(jìn)行快速排序所需時(shí)間。

理想情況下：每次劃分，正好將分成兩個(gè)等長(zhǎng)的子序列，則

T(n)Wcn+2T(n/2)c是一個(gè)常數(shù)

Wcn+2(cn/2+2T(n/4))=2cn+4T(n/4)

W2cn+4(cn/4+T(n/8))=3cn+8T(n/8)

???

Wcnlog2n+nT(1)=O(nlog2n)

最壞情況下：即每次劃分，只得到一個(gè)子序列，時(shí)效為O(n2)o

快速排序是通常被認(rèn)為在同數(shù)量級(jí)(O(nlog2n))的排序方法中平均性能最好的。

但若初始序列按關(guān)鍵碼有序或基本有序時(shí)，快排序反而蛻化為冒泡排序。為改進(jìn)

之，通常以“三者取中法”來選取支點(diǎn)記錄，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三

個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄。快速排序是一個(gè)不穩(wěn)定的排序方法。

6堆排序

堆排序的時(shí)間，主要由建立初始］堆和反復(fù)重建堆這兩部分的時(shí)間開銷構(gòu)

成，它們均是通過調(diào)用Heapify實(shí)現(xiàn)的。堆排序的最壞時(shí)間復(fù)雜度為

O(nlogn)o堆序的平均性能較接近于最壞性能。由于建初始堆所需的比較

次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，

輔助空間為0(1),它是不穩(wěn)定的排序方法。

7.歸并排序

歸并操作的工作原理如下：

申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的

序列，設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置。

比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)

指針到下一位置。重復(fù)步驟3直到某一指針達(dá)到序列尾，將另一序列剩

下的所有元素直接復(fù)制到合并序列尾。速度僅次于快速排序，但較穩(wěn)定。

歸并排序的時(shí)間復(fù)雜度為O(nlogn)。

三、算法設(shè)計(jì)分析

程序總體采用分塊化設(shè)計(jì)，每種排序的函數(shù)都以其相應(yīng)的名字保存，

在主程序調(diào)用時(shí)用#include"**.cpp”調(diào)用。這樣的總體布局將各個(gè)功

能隔離開來，每個(gè)模塊負(fù)責(zé)每個(gè)模塊的功能，使得程序的布局簡(jiǎn)單明了。

且子程序只有在被調(diào)用時(shí)才會(huì)運(yùn)行大大節(jié)約系統(tǒng)資源減少了運(yùn)算時(shí)間。

同時(shí)由于功能的隔離使得程序的擴(kuò)展性大大提高，無論程序?qū)⒁魏胃?/p>

3文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

動(dòng)時(shí)，都會(huì)方便很多。

四、源代碼

以“.cpp”保存，其他子函數(shù)分別保存，以下是主函數(shù)的代碼。

#include<iostream>

#include<conio.h>

#include<time.h>

#include”快速排序.cpp”

#include”堆排序.cpp”

#include”直接插入排序.cpp”

#include”選擇排序.cpp”

#include”冒泡排序.cpp”

#include"希爾排序.cpp”

#include”歸并排序.cpp”

usingnamespacestd;

intmain()

clock_tstart,finish;

inti,timel,time2,time3,time4,time5,time6,time7;

inta[30000],b[30000];

srand(time(O));

for(i=0;i<30000;i++)

a[i]=rand();

**************************\n”?

cout?"\t選擇排序\n";

coutw”**************************\n”?

for(i=0;i<30000;i++)b[i]=a[i];start=clock();

choices_sort(b);

finish=clock();

timel=finish-start;

printf("選擇排序耗時(shí)％d毫秒!\n\n\n”,timel);

cou***************************\n”?

cout?"\t直接插入排序\n";

cout<<***************************\n”?

for(i=0;i<30000;i++)b[i]=a[i];

start=clock();

direct(b);

finish=clock();

time2=finish-start;

printf("直接插入排序耗時(shí)％(1毫秒!\n\n\n”,time2);

***************************\n"?

4文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯,歡迎下載支持.

coutv<"\t堆排序\n";

cout<<”**************************\ri''?

for(i=0;i<30000;i++)b[i]=a[i];start=clock();

heap_sort(b,30000);

finish=clock();

time3=finish-start;

printf(”堆排序耗時(shí)％(1毫秒!\n\n\n”,time3);

coutv<''**************************\ri”?

cout?"\t快速排序\n";

cout<<***************************\n”?

for(i=0;i<30000;i++)bfi]=a[i];start=clock();

sort(b,0,29999);

finish=clock();

time4=finish-start;

printf("快速排序耗時(shí)％d毫秒!\n\n\n”,time4);

cout^^<***************************\n"?

cout?"\t冒泡排序\n";

cou***************************\n”?

for(i=0;i<30000;i++)b[i]=a[i];start=clock();

bubble_sort(b);

finish二clock。；

time5=finish-start;

printf("冒泡排序耗時(shí)％d毫秒!\n\n\n】ime5);

cout^^<”**************************\n"?

coutv<"\t希爾排序\n";

cout<<”**************************\ri''?

for(i=0;i<30000;i++)b[i]=a[i];start=clock();

shellsort(b,30000);

finish=clock();

time6=finish-start;

printf("希爾排序耗時(shí)％d毫秒!\n\n\n\tim排);

cou***************************\n”?

cout?"\t歸并排序\n";

cout^^<”**************************\n"?

for(i=0;i<30000;i++)b[i]=a[i];

start=clock();

MergeSort(b,0,29999);

finish=clock();

time7=finish-start;

printf("歸并排序耗時(shí)％d毫秒!\n\n\n”,time7);

5文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

getch();

return0;

以下是直接插入排序的函數(shù)，以“直接插入排序.cpp”保存

#include<iostream>

#include<conio.h>

usingnamespacestd;

voiddirect(int

a[]){inti,j,w;

for(i=0;i<30000;i++)

for(j=i;j>=0;j-)

if(a[j]>=a[j+l])

w=afj];

a[j]=a|j+l];

a[j+l]=w;

以下是選擇排序的函數(shù)，以“選擇排序.cpp”保存

#include<iostream>

#include<conio.h>

usingnamespacestd;

voidchoices_sort(inta[])

(

inti,j,k,t;

for(i=0;i<30000;i++)

(

k=i;

for(j=i+l;j<30000;j++)

if(a[k]>aU])

k=j;

t=a[i];

a[i]=a[k];

a[k]=t;

以下是冒泡排序的函數(shù)，以“冒泡排序.cpp”保存

6文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

#include<iostream>

#include<conio.h>

usingnamespacestd;

voidbubble_sort(inta[])

(

inti,j,w;

for(i=0;i<30000;i++)

for(j=0;j<30000-i;j++)

if(a[j]>a[j+l])

{

w=a[j];

a[j]=a[j+l];

a[j+l]=w;

以下是希爾排序的函數(shù)，以“希爾排序.cpp”保存

#include<iostream>

#include<conio.h>

#include<time.h>

usingnamespacestd;

voidshellsort(inta[],intn)

(

intd,i,j,temp;

for(d=n/2;d>=l;d=d/2)

(

for(i=d;i<n;i++)

(

temp=a[i];

for(j=i-d;(j>=0)&&(a[j]>temp);j=j-d)

(

a[j+d]=a|j];

}

a[j+d]=temp;

以下是快速排序的函數(shù)，以“快速排序.cpp”保存

#include<iostream>

#include<conio.h>

usingnamespacestd;

voidsort(inta[],intx,inty)

7文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯,歡迎下載支持.

intxx=x,yy=y;

intk=a[x];

if(x>=y)return;

while(xx!=yy)

{

while(xx<yy&&a[yy]>=k)yy—;

a[xx]=a[yy];

while(xx<yy&&a[xx]<=k)xx++;

a[yy]=a[xx];

)

a[xx]=k;

sort(a,x,xx-l);

sort(a,xx+l,y);

)

以下是堆排序的函數(shù)，以“堆排序.c叩”保存

#include<iostream>

#include<conio.h>

#include<time.h>

usingnamespacestd;

voidsift(int*x,intn,ints)

(

intt,k,j;

t=*(x+s);/*暫存開始元素*/

k=s;/*開始元素下標(biāo)*/

j=2*k+1;/*右子樹元素下標(biāo)*/

while(j<n)

(

if(j<n-l&&*(x+j)<*(x+j+l))/*判斷是否滿足堆的條件：滿足

就繼續(xù)下一輪比較，否則調(diào)整。*/

(

j++；

)

if(t<*(x+j))/*調(diào)整*/

(

*(x+k)=*(x+j);

k=j；/*調(diào)整后，開始元素也隨之

調(diào)整*/

j=2*k+1;

)

else/*沒有需要調(diào)整了，已經(jīng)是

個(gè)堆了，退出循環(huán)。*/

(

break;

8文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

*(x+k)=t;/*開始元素放到它正確位

置*/

)

voidheap_sort(int*x,intn)

(

inti,k,t;

for(i=n/2-l;i>=0;i—)

(

sift(x,n,i);/*初始建堆*/

}

for(k=n-1;k>=l;k—)

(

t=*(x+0);/*堆頂放到最后*/

*(x+0)=*(x+k);

*(x+k)=t;

sift(x,k,0);/*剩下的數(shù)再建堆*/

以下是歸并排序的函數(shù)，以“歸并排序.cpp”保存

#include<iostream>

#include<conio.h>

usingnamespacestd;

voidMerge(int*R,intlow,intm,inthigh)

(一

inti=low,j=m+l,p=0;

int*R1;

R1=(int*)malloc((high-low+l)*sizeof(int));

if(!Rl)

return;

while(i<=m&&j<=high)

Rl[p++]=(R[i]<=RU])?R[i++]:RU++];

while(i<=m)

Rl[p++]=R[i++];

while(j<=high)

Rl[p++]=RU++]；

for(p=0,i=low;i<=high;p++,i++)

R[i]=Rl[p]；

)

voidMergeSort(intR[],intlow,inthigh)

intmid;

9文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

文檔來源為:從網(wǎng)絡(luò)收集整理.wor