数据结构实验6-排序2.doc

实验6 排序算法实现实验本实验为验证和操作实验 ，需要4学时 。 1. 实验目的熟悉几种典型的排序方法（插入，选择，快速，希尔排序），并对各种算法的特点、使用范围和效率有进一步的了解。 2. 实验内容用C+描述并实现以上几种典型排序主要查找算法及其主要操作，其逻辑结构。完成如下程序： #include using namespace std;typedef int KeyType; / 关键字的类型const int MAXSIZE=100; / 数组的容量/-struct ElemType /学生的记录信息 KeyType key ; /学号 char name10; /姓名 int english; /成绩 int math; /成绩;/-class SqHash public: ElemType *ht,*z; /表数组 int length; int couts; /表大小（长度） /KeyType p; / 除留余数法的大质数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();/-SqHash:SqHash(int n1,int p1) int p; length=n1; p=p1; ht=new ElemTypelength; for(int i=0;ilength;i+) hti.key=-1;/-void SqHash:creat_hash() int i,K,en,ma; i=0; char na10; coutK; couts=0; while(K!=-1&ilength) /coutnaenma; hti.key=K; /strcpy(,na); /用串拷贝赋值 /hti.english=en; /hti.math=ma; /插入学生记录K coutn 插入成功！ ; i+; couts+; coutK;/-/查询某关键字的记录int SqHash: sort1() int i,j,k=1;int ll1; /元素从1开始存储，couts表示数组中含有元素个数，此处即为最后一个元素的下标for(i=2;i=couts;i+)if(hti.keyhti-1.key) ll1=ht0.key;ht0=hti; /设置监视哨 for(k;k=1;k+2)ht0.key=ll1;for(j=i-1;ht0.keyhtj.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;icouts+10; i+) if(hti.key!=-1) coutn i=i 学号：hti.key; / 姓名： / 英语成绩：hti.english 高数成绩：hti.math; /-int main() int p0,n0; coutn0; coutp0; SqHash ha(n0,p0); ElemType a; int k; do coutnnn; coutn 1. 建立表 ; coutn 2. 对学生记录排序; coutn 3. 输出表; coutn 4. 结束; coutn=; coutk; switch(k) case 1: ha.creat_hash(); break; case 2: coutn 排序学生数据：; int i=ha.sort1(); if(i=-1) coutn排序不成功endl ; elsecout=1&k=3); return 0;3. 实验结果1.运行与建表2. 输出表（排序前）3. 排序4. 输出表（排序后）5. 结束4. 实验总结Shell排序（ShellSort）Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。Shell排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。快速排序（QuickSort）快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成:（1） 如果不多于1个数据，直接返回。（2） 一般选择序列最左边的值作为支点数据。（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。（4） 对两边利用递归排序数列。快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是