何彬?qū)嶒?yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)計(jì)算機(jī)科學(xué)與工程學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告(十)專(zhuān)業(yè)班級(jí)2013網(wǎng)絡(luò)工程01實(shí)驗(yàn)地點(diǎn)423機(jī)房學(xué)生學(xué)號(hào)指導(dǎo)教師趙卿松學(xué)生姓名實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)項(xiàng)目排序技術(shù)綜合應(yīng)用實(shí)驗(yàn)類(lèi)別基礎(chǔ)性（） 設(shè)計(jì)性（） 綜合性（） 其它（ ）實(shí)驗(yàn)?zāi)康募耙螅?）熟練掌握常用的排序方法，并掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法；（2）深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用；（3）了解各種方法的排序過(guò)程及其依據(jù)的原則，并掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。成 績(jī) 評(píng) 定 表類(lèi) 別評(píng) 分 標(biāo)

2、 準(zhǔn)分值得分合 計(jì)上機(jī)表現(xiàn)積極出勤、遵守紀(jì)律按要求完成設(shè)計(jì)任務(wù)30分程序與報(bào)告程序代碼規(guī)范、功能正確報(bào)告詳實(shí)完整、體現(xiàn)收獲70分說(shuō)明： 評(píng)閱教師： 趙卿松 日 期： 2015 年 6 月 18 日實(shí) 驗(yàn) 內(nèi) 容實(shí)驗(yàn)內(nèi)容：對(duì)希爾排序、快速排序、歸并排序任意選擇兩種排序方法進(jìn)行比較。任意選擇希爾排序、快速排序、歸并排序中兩種排序方法，對(duì)任意給定一組數(shù)據(jù)：?jiǎn)卧?、單減、亂碼等，對(duì)它們進(jìn)行比較分析。實(shí)驗(yàn)說(shuō)明：希爾排序算法如下：void ShellSort(int r , int n)for (d=n/2; d=1; d=d/2) /以增量為d進(jìn)行直接插入排序for (i=d+1; i0 & r0rj;

3、j=j-d) rj+d=rj; /記錄后移d個(gè)位置 rj+d=r0; 快速排序算法如下：void QuickSort(int r , int first, int end) if (firstend) /遞歸結(jié)束 pivot=Partition(r, first, end); /一次劃分 QuickSort(r, first, pivot-1); /遞歸地對(duì)左側(cè)子序列進(jìn)行快速排序 QuickSort(r, pivot+1, end); /遞歸地對(duì)右側(cè)子序列進(jìn)行快速排序 int Partition(int r , int first, int end)i=first; j=end; /初始化wh

4、ile (ij) while (ij & ri= rj) j-； /右側(cè)掃描 if (ij) rirj; /將較小記錄交換到前面 i+; while (ij & ri= rj) i+； /左側(cè)掃描if (ij) rjri; /將較大記錄交換到后面 j-; retutn i; /i為軸值記錄的最終位置實(shí) 驗(yàn) 內(nèi) 容#include#define Max 100int ShellSort(int r, int n)int x = 0;for (int d = n / 2; d = 1; d = d / 2) /以增量為d進(jìn)行直接插入排序 for (int i = d + 1; i 0 & r0 r

5、j; j = j - d)rj + d = rj; /記錄后移d個(gè)位置x+;rj + d = r0;return x;void exchange(int a, int i, int j)int temp;temp = ai;ai = aj;aj = temp;int Partition(int r, int first, int end, int &x) int i = first, j = end; /初始化while (i j)while (i j & ri = rj)j-; /右側(cè)掃描if (i j) exchange(r, i, j); /將較小記錄交換到前面 i+;x+;while

6、(i j & ri = rj)i+; /左側(cè)掃描if (i j) exchange(r, j, i); /將較大記錄交換到后面 j-;x+;return i; /i為軸值記錄的最終位置int quickSort(int r, int first, int end) /在序列 firstend中遞歸地進(jìn)行快速排序static int x = 0;int pivotpos;if (first end)pivotpos = Partition(r, first, end, x);quickSort(r, first, pivotpos - 1);quickSort(r, pivotpos + 1,

7、end);return x;void getlist(int a, int &n)printf(請(qǐng)輸入數(shù)組的元素的個(gè)數(shù)n：);scanf(%d, &n);for (int i = 1; i = n; i+)printf(請(qǐng)輸入數(shù)組的第%d個(gè)元素：, i);scanf(%d, &ai);void print(int a, int n)for (int i = 1; i = n; i+)printf(%d , ai);printf(n);void main()int aMax = 0 , bMax = 0 , n = 0, x, y;getlist(a, n);for (int i = 0; i

8、= n; i+)bi = ai;x = ShellSort(a, n);printf(經(jīng)過(guò)希爾排序得到的排序序列為：);print(a, n);printf(希爾排序需要的交換次數(shù)為：%d次nn, x);y = quickSort(b, 1, n);printf(經(jīng)過(guò)快速排序得到的排序序列為：);print(b, n);printf(快速排序需要的交換次數(shù)為：%d次nn, y);實(shí) 驗(yàn) 內(nèi) 容得出結(jié)論：希爾排序和快速排序的復(fù)雜程度上，對(duì)于順序或基本順序的序列，兩者復(fù)雜程度相當(dāng)；逆序、基本逆序或者亂序的情況下，快速排序都相對(duì)優(yōu)良。實(shí) 驗(yàn) 總 結(jié)通過(guò)本次上機(jī)實(shí)驗(yàn)，熟練掌握排序的常用算法，并且掌握了希爾