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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告實(shí)驗(yàn)五 排序一、需求分析：本演示程序用C+6.0編寫，完成各種排序的實(shí)現(xiàn)，對輸入的一組數(shù)字實(shí)現(xiàn)不同的排序方法，對其由小到大順序輸出。（1）分別對直接插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序算法進(jìn)行編寫。（2）、對存儲的函數(shù)即輸入的數(shù)字進(jìn)行遍歷。（3）、初始化函數(shù)對輸入的數(shù)字進(jìn)行保存。（4）、主函數(shù)實(shí)現(xiàn)使用者操作界面的編寫，對輸入、選擇、保存、輸出的各種實(shí)現(xiàn)。這當(dāng)中還包括了各個(gè)函數(shù)的調(diào)用的實(shí)現(xiàn)。（5）、程序所能達(dá)到的功能：完成對輸入的數(shù)字的生成，并通過對各排序的選擇實(shí)現(xiàn)數(shù)字從小到大的輸出。二、程序主要功能以及基本要求：（1）、設(shè)計(jì)一個(gè)菜單，格式如下：1、直接插

2、入排序2、希爾排序3、冒泡排序4、快速排序5、選擇排序6、堆排序7、退出（2）、選擇不同的菜單但進(jìn)行相應(yīng)的排序，并給出排序的關(guān)鍵字序列。三、系統(tǒng)框架圖：本程序包含了9個(gè)函數(shù)，它們分別是：（1）、直接插入排序的算法函數(shù)InsertSort（）。（2）、希爾排序的算法函數(shù)ShellSort（）。主函數(shù)（3）、冒泡排序算法函數(shù)BubbleSort（）。操作界面的設(shè)計(jì)，函數(shù)的調(diào)用。對輸入的數(shù)組進(jìn)行遍歷初始化各個(gè)排序算法函數(shù)（4）、快速排序的算法函數(shù)Partition（）。（5）、選擇排序算法函數(shù)SelectSort（）。（6）、堆排序算法函數(shù)HeapAdjust（）。（7）、對存儲數(shù)字的遍歷函數(shù)Vis

3、it（）。（8）、初始化函數(shù)InitSqList（）。（9）、主函數(shù)main（）。四、詳細(xì)設(shè)計(jì)實(shí)現(xiàn)各個(gè)算法的主要內(nèi)容，下面是各個(gè)函數(shù)的主要信息：（1）各個(gè)排序函數(shù)的算法：一、直接插入排序void InsertSort(SqList &L)int i,j;for( i=2; i<=L.length;i+)if(L.ri.key < L.ri-1.key)L.r0 = L.ri;L.ri = L.ri-1;for( j=i-2; (L.r0.key < L.rj.key); j-)L.rj+1 = L.rj;L.rj+1 = L.r0;二、希爾排序void ShellSo

4、rt(SqList &L) int i, j; int dk = 1;/增量 while(dk <=L.length/3)dk = 3*dk+1;/增大增量while(dk>0)dk /= 3;/減小增量for (i = dk; i <=L.length; i+) L.r0.key = L.ri.key; j = i; while (j >= dk) && (L.rj-dk.key > L.r0.key) L.rj.key = L.rj-dk.key; j -= dk; L.rj.key = L.r0.key; 三、冒泡排序void Bub

5、bleSort(SqList &L)int i,j;for(i=0;i<L.length-2;i+)int flag = 1;for(j=0;j<L.length-i-2;j+)if(L.rj.key > L.rj+1.key)flag = 0;int temp;temp = L.rj.key;L.rj.key = L.rj+1.key;L.rj+1.key = temp;/若無交換說明已經(jīng)有序if(flag=1)break;四、快速排序int Partition(SqList &L,int low,int high)/分割區(qū)域函數(shù)L.r0 = L.rlow;

6、int pivotkey = L.rlow.key;/一般將順序表第一個(gè)元素作為支點(diǎn)while(low < high)while(low<high && L.rhigh.key>=pivotkey)high-;L.rlow = L.rhigh;while(low<high && L.rlow.key<=pivotkey)low+;L.rhigh = L.rlow;L.rlow = L.r0;/返回樞軸位置return low;void QSort(SqList &L,int low,int high)/每張子表的快速排序if

7、(low<high)int pivotloc = Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);void QuickSort(SqList &L)QSort(L,1,L.length);五、簡單選擇排序void SelectSort(SqList &L)int min;int j;for (int i = 0; i <L.length; i+) / 選擇第i小的記錄，并交換j = i;min = L.ri.key;for (int k = i; k < L.leng

8、th; k+) / 在Ri.n-1中選擇最小的記錄if (L.rk.key < min) min = L.rk.key ;j = k;if (i != j) / 與第i個(gè)記錄交換int temp = L.ri.key;L.ri.key = L.rj.key;L.rj.key = temp;六、堆排序void HeapAdjust(HeapType &H,int s,int m)/堆調(diào)整，將記錄調(diào)整為小頂堆int j;RedType rc = H.rs;/暫時(shí)存儲根結(jié)點(diǎn)for(j=2*s; j<=m; j*=2)/沿著結(jié)點(diǎn)記錄較小的向下篩選if(j<m &&am

9、p; H.rj.key<H.rj+1.key)+j;if(rc.key>= H.rj.key)break;H.rs = H.rj;s = j;H.rs = rc;void HeapSort(HeapType &H)int i;RedType temp;for(i = H.length; i>0; -i)HeapAdjust(H,i,H.length);for(i=H.length; i>1; -i)temp = H.r1;H.r1 = H.ri;H.ri = temp;HeapAdjust(H,1,i-1);（2）遍歷函數(shù)與初始化void Visit(SqList L)for(int i=1; i<=L.length; i+)cout<<L.ri.key<<" "cout<<endl;void InitSqList(SqList &L,int a)for(int i=1;i<=L.length;i+)L.ri.key = ai;五、測試結(jié)果以下是各種界面的測試結(jié)果：（1）輸入的界面 :（2）排序操作界面：（3）各種排序的結(jié)果： 六、設(shè)計(jì)不足以及存在問題本程序是基于C+6.0的實(shí)現(xiàn)，其實(shí)在設(shè)計(jì)上