數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告(實(shí)驗(yàn)十七)6頁

1、深 圳 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告 課程名稱： 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與課程設(shè)計(jì) 實(shí)驗(yàn)項(xiàng)目名稱： 希爾排序 學(xué)院： 計(jì)算機(jī)與軟件學(xué)院 專業(yè)： 指導(dǎo)教師： 蔡平 報(bào)告人： 文成 學(xué)號(hào)： 2011150259 班級(jí)： 5 實(shí)驗(yàn)時(shí)間： 2012-12-17 實(shí)驗(yàn)報(bào)告提交時(shí)間： 2012-12-24 教務(wù)部制一、實(shí)驗(yàn)?zāi)康呐c要求：目的：1. 掌握哈希排序算法原理2.掌握哈希排序算法的實(shí)現(xiàn)方法要求：1.熟悉C+語言編程2.熟練編程實(shí)現(xiàn)哈希算法2、 實(shí)驗(yàn)內(nèi)容：問題 A: 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-希爾排序題目描述給出一個(gè)數(shù)據(jù)序列，使用希爾排序算法進(jìn)行從小到大的排序間隔gap使用序列長度循環(huán)除2直到1輸入第一行輸入t，表示有t個(gè)測(cè)試示

2、例第二行輸入n，表示第一個(gè)示例有n個(gè)數(shù)據(jù)第三行輸入n個(gè)數(shù)據(jù)，都是正整數(shù)，數(shù)據(jù)之間用空格隔開以此類推輸出每行輸出每個(gè)示例排序后，從小到大的結(jié)果樣例輸入26111 22 6 444 333 55877 555 33 1 444 77 666 2222樣例輸出6 22 55 111 333 444 1 33 77 77 444 555 666 2222 3、 實(shí)驗(yàn)步驟與過程：希爾排序是一種按照增量排序的方法。其中增量值是小于n的正整數(shù)。shell排序的基本思想是：    先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中

3、。先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂Ｔ创a：A：#include<iostream>using namespace std;int ShellSort(int array,int n) int gap,i,j; for(gap=n/2;gap>=1;gap-) for(i=0;i<gap; i+) for(j = i+gap; j<n; j=j+gap) if(arrayj<arrayj

4、-gap) int temp = arrayj; int k = j-gap; while(k>=0 && arrayk>temp) arrayk+gap = arrayk; k = k-gap; arrayk+gap = temp; return 0; int main() int testnum,i,j;cin>>testnum;for(i=0;i<testnum;i+)int num;cin>>num;int *array=new intnum;for(j=0;j<num;j+)cin>>arrayj;ShellSort(array,num);for(j=0;j<num;j+)cout<<arrayj<<" "cout<<endl;return 0;四、實(shí)驗(yàn)結(jié)果及數(shù)據(jù)處理分析：A：實(shí)驗(yàn)基本達(dá)到實(shí)驗(yàn)要求五、實(shí)驗(yàn)結(jié)論與體會(huì)： 從這個(gè)實(shí)驗(yàn)中我學(xué)會(huì)使用哈希算法進(jìn)行排序，雖然實(shí)現(xiàn)起來沒有冒泡和插入排序簡單。但實(shí)驗(yàn)數(shù)據(jù)比較多時(shí)，比前兩者時(shí)間復(fù)雜度要小。因此能熟練使用各種排序方法失衡重要的。指導(dǎo)教師批閱意見：成績?cè)u(píng)定： 指導(dǎo)教師簽