2023年數(shù)據(jù)結(jié)構(gòu)排序?qū)嶒?yàn)報(bào)告

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告

實(shí)驗(yàn)五排序

一、需求分析：

本演示程序用C++6.()編寫，完畢各種排序的實(shí)現(xiàn)，對(duì)輸入的一組數(shù)字實(shí)現(xiàn)不同的排序

方法，對(duì)其由小到大順序輸出。

(1)分別對(duì)直接插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序算法

進(jìn)行編寫。

(2)、對(duì)存儲(chǔ)的函數(shù)即輸入的數(shù)字進(jìn)行遍歷。

(3)、初始化函數(shù)對(duì)輸入的數(shù)字進(jìn)行保存。

(4)、主函數(shù)實(shí)現(xiàn)使用者操作界面的編寫，對(duì)輸入、選擇、保存、輸出的各種實(shí)現(xiàn)。這當(dāng)

中還涉及了各個(gè)函數(shù)的調(diào)用的實(shí)現(xiàn)。

(5)、程序所能達(dá)成的功能：完畢對(duì)輸入的數(shù)字的生成，并通過對(duì)各排序的選擇實(shí)現(xiàn)數(shù)

字從小到大的輸出。

二、程序重要功能以及基本規(guī)定:

(1)、設(shè)計(jì)一個(gè)菜單，格式如下：

1、直接插入排序

2、希爾排序

3、冒泡排序

4、快速排序

5、選擇排序

6、堆排序

7,退出

(2)、選擇不同的菜單但進(jìn)行相應(yīng)的排序，并給出排序的關(guān)鍵字序列。

三、系統(tǒng)框架圖:

本程序包含了9個(gè)函數(shù)，它們分別是:

(1)、直接插入排序的算法函數(shù)InsertSort()。

(2)、希爾排序的算法函數(shù)ShellSort()?

(3)、冒泡排序算法函數(shù)BubbleSort().主函數(shù)

(4)、快速排序的算法函數(shù)Partition

各對(duì)輸操作

(5)、選擇排序算法函數(shù)SelectSort()o

個(gè)入的界面

(6)、堆排序算法函數(shù)HeapAdjustO。

排數(shù)組的設(shè)

(7)、對(duì)存儲(chǔ)數(shù)字的遍歷函數(shù)Visit()。

序進(jìn)行計(jì),函

(8)、初始化函數(shù)InitSqList。。

算遍歷數(shù)的

(9)、主函數(shù)main()。

卻誦田.

四、具體設(shè)計(jì)

實(shí)現(xiàn)各個(gè)算法的重要內(nèi)容，下面是各個(gè)函數(shù)的重要信息：

(1)各個(gè)排序函數(shù)的算法：

一、直接插入排序

voidInsertSort(SqList&L)

(

°inti,j;

for(i=2；i<=L.length;i++)

{

oif(L.r[i].key<L.r[i-1].key)

g(

0?L.r[0]=L.r[i];

aL.r[i]=L.r[i-1];

6for(j=i-2;(L.rE0].key<L.r[j].key)；

。，L.r[j+1]=L.r[j]；

aL.r[j+1]=L.r[0];

00j

)

}

二、希爾排序

voidShcllSort(SqList&L)

{

?nti,j;

intdk=1;//增量

while(dk<=L.1ength/3)

dk=3*dk+1;〃增大增量

while(dk>0)

(

?dk/-3;//減小增量

?for(i=dk;i<=L.length;i++)

8{

??L.r[O].key=L.r[i].key;

8?j=i；

?whi1e((j>=dk)&&(L.r[.j-dk].key>L.r[0].key))

(

???L.r[j].key=L.r[j-dk].key;

j—=dk;

)

???L.r[j].key=L.r[OJ.key;

4)

}

三、冒泡排序

voidBubbleSort(SqList&L)

(

?inti,j;

for(i=0;i<L.length-2；i++)

{

?intflag=1;

for(j=O;j<L.length-i-2;j++)

if(L.r[j].key>L.r|j+l].key)

dftdf1ag=0;

gnnttemp；

，temp=L.r[j],key；

gL.r[j].key=L.r[j+l].key;

。L.r[j+1].key=temp;

g}

”〃若無互換說明已有序

gif(flag==1)

，gbreak；

0}

)

四、快速排序

intPartition(SQList&L,intlow9inthigh)

(

〃分割區(qū)域函數(shù)

L.r[0]=L.r[low]；

intpivotkey=L.r[low].key；〃一般將順序表第一個(gè)元素作為支點(diǎn)

while(1ow<high)

。while(low<high&&L,r[high].key>=pivotkey)

ghigh--;

，L.r[Iow]=L.r[high]；

whi1e(1ow<high&&L.r[low].key<=pivotkey)

Mow++;

L.r[high]=L.r[low];

?}

L.r[low]=L.r[0]；〃返回樞軸位置

returnlow;

)

voidQSort(SqList&L,intlow,inthigh)

(

〃每張子表的快速排序

dif(low<high)

(

“ntpivot1oc=Partition(L,low,high);

gQSort(L,low,pivotloc-1);

。QSort(L,pivotloc+1,high);

}

}

voidQuickSort(SqList&L)

(

dQSort(L,l,L.1ength);

}

五、簡(jiǎn)樸選擇排序

voidSelectSort(SqList&L)

(

intmin;

intj；

ofor(inti=0;i<L.length；i++)

//選擇第i小的記錄，并互換

，j=i；

，min=L.r[i].key；

for(intk=i;k<L.length;k++)

{//在R[i..n?l]中選擇最小的記錄

，if(L.r[k].key<min)

dd(

??min=L.r[k].key;

???j=k;

8)

?)

，if(i!=j)

，{//與第i個(gè)記錄互換

?inttemp=L.r[i].key;

L.r[i].key=L.r[j].key;

???L.r[j].key=temp;

81

?)

}

六、堆排序

voidHeapAdjust(HeapType&H,ints,inti

{

。〃堆調(diào)整,將記錄調(diào)整為小頂堆

intj;

aRedTyperc=H.r[s]；〃暫時(shí)存儲(chǔ)根結(jié)點(diǎn)

?for(j=2*s;j<=m;j*=2)

”/沿著結(jié)點(diǎn)記錄較小的向下篩選

“f(j<m&&H.r[j].key<H.r[j+l].key)

g，++j；

gif(rc.key>=H.r[j].key)

a。break；

H.r[s]=H.r[j];

s=j；

}

?H.r[s]=rc;

}

voidHeapSort(HeapType&H)

(

inti;

edTypetemp;

for(i=H.length;i>0；--i)

HeapAdjust(H,i,H.length);

for(i=H.length;i>l;—i)

{

d

otemp=H.r[1];

?H.r[1]=H.r[i]；

?H.r[i]=temp;

oHeapAdjust(H>1>i-1);

)

)

(2)遍歷函數(shù)與初始化

voidVisit(SqListL)

for(inti=l;i<=L.length;i++)

cout?L.r[i].key<<n"；

dcout?endl;

)

voidInitSqList(SqList&L,inta[])

(

for(inti=l;i<=L.length;i++)

L.r[i].key=a[i]；

}

五、測(cè)試結(jié)果

以下是各種界面的測(cè)試結(jié)果：

■，E:\最后的俁程設(shè)計(jì)\DebugBE序exe"

育入

一?

主

Q入112

-E

f數(shù)5

H人28

月

主

數(shù)

入376

ED

主

數(shù)

入423

月

主

數(shù)

入546

ED即

(1)輸入的界面：

序

作

操

LI.界

(2).L

-*E:\最后的課程設(shè)計(jì)\Debug網(wǎng)序.exe”

歡

非

庫

、虬

界

*********犬

生

干

月

喬

陵

￡0選

人

述

妤

1直

-

豐

卜

2序

希

-二

豐

3:定

-閆

二

本

速

4序

-二

展

豐

擇

；

5-序

選

6-非*

7-用

請(qǐng)輸入你需要的操作:

面:

（3）各種排序的結(jié)果:

，E:\最后的課程設(shè)計(jì)\Debug\^E序.exe”

般

岸LA

序

刖

25823

鍵繼!

非8I

字

序

序

一

的操

入你

作

要

23后S8

12住=

續(xù)

0鍵!