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

2、e10; /姓名 int english; /成績 int math; /成績;/-class SqHash public: ElemType *ht,*z; /表數(shù)組 int length; int couts; /表大小（長度） /KeyType p; / 除留余數(shù)法的大質數(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請逐一輸入各個學號(關鍵字值)(-1結束)：" cin>>K; couts=0; while(K!=-1&&i<length) /cout<<"n請輸入學

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

5、元素從1開始存儲，couts表示數(shù)組中含有元素個數(shù)，此處即為最后一個元素的下標for(i=2;i<=couts;i+)if(hti.key<hti-1.key) ll1=ht0.key;ht0=hti; /設置監(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<<" 學號："<<hti.key; /<<" 姓名："<< /<<" 英語成績："<<hti.english<<" 高數(shù)成績："<<hti.math; /-int main() int p0,n0; cout<<"n 請輸入n值（n值應是記錄總數(shù)的1.3-1.

7、5倍)" cin>>n0; cout<<"n 請輸入P值（應是不大于n 的大質數(shù)）：" cin>>p0; SqHash ha(n0,p0); ElemType a; int k; do cout<<"nnn" cout<<"n 1. 建立表 " cout<<"n 2. 對學生記錄排序" cout<<"n 3. 輸出表" cout<<"n 4. 結束" 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 排序學生數(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. 實驗結果1.運行與建表2. 輸出表（排序前）3. 排序4. 輸出表（排序后）5. 結束4. 實驗總結Shell排序（ShellSort）Shell排序通過將數(shù)據(jù)分成不同的組，先對每一組進行排序，然后再對所有的元素進行一次插入排序，以減少數(shù)據(jù)交換和移動的次數(shù)。平均效率是O(nlogn)。其中分組的合理性會對算法產生重要的影響。現(xiàn)在多用D.E.Knuth的分組方法。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相

10、對比較簡單，它適合于數(shù)據(jù)量在5000以下并且速度并不是特別重要的場合。它對于數(shù)據(jù)量較小的數(shù)列重復排序是非常好的。Shell排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。快速排序（QuickSort）快速排序是一個就地排序，分而治之，大規(guī)模遞歸的算法。從本質上來說，它是歸并排序的就地版本。快速排序可以由下面四步組成:（1） 如果不多于1個數(shù)據(jù)，直接返回。（2） 一般選擇序列最左邊的值作為支點數(shù)據(jù)。（3） 將序列分成2部分，一部分都大于支點數(shù)據(jù)，另外一部分都小于支點數(shù)據(jù)。（4） 對兩邊利用遞歸排序數(shù)列。快速排序比大部分排序算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法，但是就通常