數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)6排序2

1、實(shí)驗(yàn)6 排序算法實(shí)現(xiàn)實(shí)驗(yàn)本實(shí)驗(yàn)為驗(yàn)證和操作實(shí)驗(yàn) ，需要4學(xué)時(shí) 。 1. 實(shí)驗(yàn)?zāi)康氖煜追N典型的排序方法（插入，選擇，快速，希爾排序），并對(duì)各種算法的特點(diǎn)、使用范圍和效率有進(jìn)一步的了解。 2. 實(shí)驗(yàn)內(nèi)容用C+描述并實(shí)現(xiàn)以上幾種典型排序主要查找算法及其主要操作，其邏輯結(jié)構(gòu)。完成如下程序： #include <iostream>using namespace std;typedef int KeyType; / 關(guān)鍵字的類型const int MAXSIZE=100; / 數(shù)組的容量/-struct ElemType /學(xué)生的記錄信息 KeyType key ; /學(xué)號(hào) char nam

2、e10; /姓名 int english; /成績(jī) int math; /成績(jī);/-class SqHash public: ElemType *ht,*z; /表數(shù)組 int length; int couts; /表大小（長(zhǎng)度） /KeyType p; / 除留余數(shù)法的大質(zhì)數(shù)public: SqHash( int n1,int p1); SqHash() delete ht; length=0; ; void creat_hash(); /int find( KeyType k ); int sort1(); /void creat_hash(); void PrintOut();/-Sq

3、Hash:SqHash(int n1,int p1) int p; length=n1; p=p1; ht=new ElemTypelength; for(int i=0;i<length;i+) hti.key=-1;/-void SqHash:creat_hash() int i,K,en,ma; i=0; char na10; cout<<"n請(qǐng)逐一輸入各個(gè)學(xué)號(hào)(關(guān)鍵字值)(-1結(jié)束)：" cin>>K; couts=0; while(K!=-1&&i<length) /cout<<"n請(qǐng)輸入學(xué)

4、生的姓名，英語成績(jī)和高數(shù)成績(jī)：" /cin>>na>>en>>ma; hti.key=K; /strcpy(,na); /用串拷貝賦值 /hti.english=en; /hti.math=ma; /插入學(xué)生記錄K cout<<"n 插入成功！" ; i+; couts+; cout<<"n請(qǐng)逐一輸入各個(gè)學(xué)號(hào)(關(guān)鍵字值)(-1結(jié)束)：" cin>>K;/-/查詢某關(guān)鍵字的記錄int SqHash: sort1() int i,j,k=1;int ll1; /

5、元素從1開始存儲(chǔ)，couts表示數(shù)組中含有元素個(gè)數(shù)，此處即為最后一個(gè)元素的下標(biāo)for(i=2;i<=couts;i+)if(hti.key<hti-1.key) ll1=ht0.key;ht0=hti; /設(shè)置監(jiān)視哨 for(k;k<=1;k+2)ht0.key=ll1;for(j=i-1;ht0.key<htj.key;j-)htj+1.key=htj.key;htj+1.key=ht0.key; if(i!=0) return 1; else return 0;/-void SqHash:PrintOut() int i,j; for (i=0;i<couts

6、+10; i+) if(hti.key!=-1) cout<<"n i="<<i<<" 學(xué)號(hào)："<<hti.key; /<<" 姓名："<< /<<" 英語成績(jī)："<<hti.english<<" 高數(shù)成績(jī)："<<hti.math; /-int main() int p0,n0; cout<<"n 請(qǐng)輸入n值（n值應(yīng)是記錄總數(shù)的1.3-1.

7、5倍)" cin>>n0; cout<<"n 請(qǐng)輸入P值（應(yīng)是不大于n 的大質(zhì)數(shù)）：" cin>>p0; SqHash ha(n0,p0); ElemType a; int k; do cout<<"nnn" cout<<"n 1. 建立表 " cout<<"n 2. 對(duì)學(xué)生記錄排序" cout<<"n 3. 輸出表" cout<<"n 4. 結(jié)束" cout<&l

8、t;"n=" cout<<"n 輸入您的選擇(1,2,3,4):" cin>>k; switch(k) case 1: ha.creat_hash(); break; case 2: cout<<"n 排序?qū)W生數(shù)據(jù)：" int i=ha.sort1(); if(i=-1) cout<<"n排序不成功"<<endl ; elsecout<<"排序成功！" break; case 3: ha.PrintOut(); break;

9、 while(k>=1&&k<=3); return 0;3. 實(shí)驗(yàn)結(jié)果1.運(yùn)行與建表2. 輸出表（排序前）3. 排序4. 輸出表（排序后）5. 結(jié)束4. 實(shí)驗(yàn)總結(jié)Shell排序（ShellSort）Shell排序通過將數(shù)據(jù)分成不同的組，先對(duì)每一組進(jìn)行排序，然后再對(duì)所有的元素進(jìn)行一次插入排序，以減少數(shù)據(jù)交換和移動(dòng)的次數(shù)。平均效率是O(nlogn)。其中分組的合理性會(huì)對(duì)算法產(chǎn)生重要的影響?，F(xiàn)在多用D.E.Knuth的分組方法。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相

10、對(duì)比較簡(jiǎn)單，它適合于數(shù)據(jù)量在5000以下并且速度并不是特別重要的場(chǎng)合。它對(duì)于數(shù)據(jù)量較小的數(shù)列重復(fù)排序是非常好的。Shell排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序，當(dāng)剛開始元素很無序的時(shí)候，步長(zhǎng)最大，所以插入排序的元素個(gè)數(shù)很少，速度很快；當(dāng)元素基本有序了，步長(zhǎng)很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時(shí)間復(fù)雜度會(huì)比o(n2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以shell排序是不穩(wěn)定的。快速排序（QuickSort）快速排序是一個(gè)就地排序，分而治之，大規(guī)模遞歸的算法。從本質(zhì)上來說，它是歸并排序的就地版本?？焖倥判蚩梢杂上旅嫠牟浇M成:（1） 如果不多于1個(gè)數(shù)據(jù)，直接返回。（2） 一般選擇序列最左邊的值作為支點(diǎn)數(shù)據(jù)。（3） 將序列分成2部分，一部分都大于支點(diǎn)數(shù)據(jù)，另外一部分都小于支點(diǎn)數(shù)據(jù)。（4） 對(duì)兩邊利用遞歸排序數(shù)列?？焖倥判虮却蟛糠峙判蛩惴ǘ家?。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法，但是就通常