内部排序实验报告.docVIP

深 圳 大 学 实 验 报 告 课程名称： 数据结构 实验项目名称： 内部排序 学院： 专业： 指导教师： 报告人 学号： 班级： 实验时间： 2012-12-25 实验报告提交时间： 2012-12-25 教务部制实验目的与要求： 掌握常见的排序算法的思想及其适用条件。 掌握常见的排序算法的程序实现。方法、步骤：输入一组关键字序列分别实现下列排序:1. 实现直接插入排序、折半插入排序和希尔排序算法。2. 实现冒泡排序和快速排序算法。3. 实现简单选择排序和堆排序算法。4. 实现归并排序算法。5. 在主函数中设计一个简单的菜单，分别测试上述算法。6. （*）综合训练：采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。实验过程及内容：/头文件#include#include#include / malloc()等#include / EOF(=Z或F6),NULL#include / atoi()#include / floor(),ceil(),abs() #include / cout,cin/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; typedef int Boolean;/对两个数值型关键字的比较#define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)#define LQ(a,b) (a)=(b)/待排记录的数据类型#define MAXSIZE 20 /一个用作示例的小顺序表的最大长度typedef int KeyType; /定义关键字类型为整型typedef int InfoType; /定义其它数据项的类型typedef structKeyType key; /关键字项InfoType otherinfo;/其他数据项RedType; /记录类型typedef structRedType rMAXSIZE+1;/r0闲置或用作哨兵单元int length;/顺序表长度SqList;/顺序表类型typedef SqList HeapType; / 堆采用顺序表存储表示/顺序表插入排序的函数void InsertSort(SqList &L);void BInsertSort(SqList &L);void ShellInsert(SqList &L,int dk);void ShellSort(SqList &L,int dlta,int t);/快速排序int Partition(SqList &L,int low,int high);void QSort(SqList &L,int low,int high);void QuickSort(SqList &L);/选择排序int SelectMinKey(SqList L,int i);void SelectSort(SqList &L);/堆排序void HeapAdjust(HeapType &H,int s,int m);void HeapSort(HeapType &H);/归并排序void Merge(RedType SR,RedType TR,int i,int m,int n);void MSort(RedType SR,RedType TR1,int s, int t);void MergeSort(SqList &L);/输出函数void print(SqList L);void print_H(HeapType H);#define N 8#define T 3void main() RedType dN=20,6,52,1,65,3,88,9,47,8,22,4,39,5,74,7; int i; SqList LL; int dtT=5,3,1; / 增量序列数组 int choice;s123: cout请选择要使用的排序算法：n0.退出n; cout1.插入排序n2.交换排序n; coutchoice; switch(choice) case 0: break; case 1: /插入排序 for(i=0;iN;i+) /给LL.r赋值 LL.ri+1=di; LL.length=N; printf(直接插入排序前:n); print(LL); InsertSort(LL); printf(直接插入排序后:n); print(LL); for(i=0;iN;i+) LL.ri+1=di; LL.length=N; printf(n折半插入排序前:n); print(LL); BInsertSort(LL); printf(折半插入排序后:n); print(LL); for(i=0;iN;i+) LL.ri+1=di; LL.length=N; printf(n希尔排序前: n); print(LL); ShellSort(LL,dt,T); printf(希尔排序后: n); print(LL); goto s123; case 2: /交换排序 for(i=0;iN;i+) LL.ri+1=di; LL.length=N; printf(快速排序前:n); print(LL); QuickSort(LL); printf(快速排序后:n); print(LL); goto s123; case 3: /选择排序 for(i=0;iN;i+) LL.ri+1=di; LL.length=N; printf(简单选择排序前:n); print(LL); SelectSort(LL); printf(简单选择排序后:n); print(LL); HeapType h; for(i=0;iN;i+) h.ri+1=di; h.length=N; printf(n堆排序前:n); print_H(h); HeapSort(h); printf(堆排序后:n); print_H(h); goto s123; case 4: /归并排序 for(i=0;iN;i+) LL.ri+1=di; LL.length=N; printf(归并排序前:n); print(LL); MergeSort(LL); printf(归并排序后:n); print(LL); goto s123; default: cout输入有误，请输入正确的选项！n; goto s123; /顺序表插入排序的函数(3个)void InsertSort(SqList &L)/ 对顺序表L作直接插入排序。算法10.1int i,j; for(i=2;i=L.length;+i) if(LT(L.ri.key,L.ri-1.key) L.r0=L.ri; L.ri=L.ri-1; for(j=i-2;LT(L.r0.key,L.rj.key);-j) L.rj+1=L.rj; L.rj+1=L.r0; /InsertSortvoid BInsertSort(SqList &L) /对顺序表L作折半插入排序。算法10.2 int low,high,m; for(int i=2;i=L.length;+i)L.r0=L.ri;low=1;high=i-1;while(low=high+1;-j) L.rj+1=L.rj; L.rhigh+1=L.r0; /for/BInsertSortvoid ShellInsert(SqList &L,int dk) /对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比，作了以下修改： / 1.前后记录位置的增量是dk,而不是1; / 2.r0只是暂存单元,不是哨兵。当j=0时,插入位置已找到。算法10.4int i,j;for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj; /记录后移，查找插入位置L.rj+dk=L.r0; /插入void ShellSort(SqList &L,int dlta,int t) /按增量序列dlta0.t-1对顺序表L作希尔排序。算法10.5int k;for(k=0;kt;+k)ShellInsert(L,dltak); /一趟增量为dltak的插入排序printf(第%d趟排序结果: n,k+1);print(L);int Partition(SqList &L,int low,int high) /交换顺序表L中子表rlow.high的记录，枢轴记录到位，并返回其 /所在位置，此时在它之前（后）的记录均不大（小）于它。算法10.6(b)KeyType pivotkey;L.r0=L.rlow; /用子表的第一个记录作枢轴记录pivotkey=L.rlow.key; /枢轴记录关键字while(low high) /从表的两端交替地向中间扫描while(low=pivotkey)-high;L.rlow=L.rhigh; /将比枢轴记录小的记录移到低端while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow; /将比枢轴记录大的记录移到高端L.rlow=L.r0; /枢轴记录到位return low; /返回枢轴位置void QSort(SqList &L,int low,int high) /对顺序表L中的子序列L.rlow.high作快速排序。算法10.7 if(lowhigh) int pivotloc; pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); /if/QSortvoid QuickSort(SqList &L) /对顺序表L作快速排序。算法10.8QSort(L,1,L.length);/QuickSortint SelectMinKey(SqList L,int i) /返回在L.ri.L.length中key最小的记录的序号KeyType min;int j,k;k=i; /设第i个为最小min=L.ri.key;for(j=i+1;j=L.length;j+)if(L.rj.keymin) /找到更小的k=j;min=L.rj.key;return k;void SelectSort(SqList &L) /对顺序表L作简单选择排序。算法10.9 int i,j,temp; for(i=1;iL.length;+i) j=SelectMinKey(L,i);if(i!=j)temp=i;i=j;j=temp; void HeapAdjust(HeapType &H,int s,int m) /算法10.10 /已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，本函数 /调整H.rs的关键字,使H.rs.m成为一个大顶堆(对其中记录的关键字而言)RedType rc;int j;rc=H.rs;for(j=2*s;j=m;j*=2) /沿key较大的孩子结点向下筛选if(j0;-i) HeapAdjust(H,i,H.length); for( i=H.length;i1;-i) H.r0=H.r1; H.r1=H.ri; H.ri=H.r0; HeapAdjust(H,1,i-1); /for/HeapSortvoid Merge(RedType SR,RedType TR,int i,int m,int n) /将有序的SRi.m和SRm+1.n归并为有序的TRi.n 算法10.12int j,k,l;for(j=m+1,k=i;i=m&j=n;+k) /将SR中记录由小到大地并入TRif LQ(SRi.key,SRj.key)TRk=SRi+;elseTRk=SRj+;if(i=m)for(l=0;l=m-i;l+)TRk+l=SRi+l; /将剩余的SRi.m复制到TRif(j=n)for(l=0;l=n-j;l+)TRk+l=SRj+l; /将剩余的SRj.n复制到TRvoid MSort(RedType SR,RedType TR1,int s, int t) /将SRs.t归并排序为TR1s.t。算法10.13RedType TR2MAXSIZE;if(s=t)TR1s=SRs;else int m=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t);void MergeSort(SqList &L) /对顺序表L作归并排序。算法10.14MSort(L.r,L.r,1,L.length);void print(SqList L)int i;for(i=1;i=L.length;i+)printf( (%d,%d) ,L.ri.key,L.ri.otherinfo);printf(n);vo