《内部排序实验报告》由会员分享，可在线阅读，更多相关《内部排序实验报告（30页珍藏版）》请在金锄头文库上搜索。
1、深 圳 大 学 实 验 报 告 课程名称： 数据结构 实验项目名称： 内部排序 学院： 专业： 指导教师： 报告人 学号： 班级： 实验时间： 2012-12-25 实验报告提交时间： 2012-12-25 教务部制实验目的与要求： 掌握常见的排序算法的思想及其适用条件。 掌握常见的排序算法的程序实现。方法、步骤：输入一组关键字序列分别实现下列排序:1. 实现直接插入排序、折半插入排序和希尔排序算法。2. 实现冒泡排序和快速排序算法。3. 实现简单选择排序和堆排序算法。4. 实现归并排序算法。5. 在主函数中设计一个简单的菜单，分别测试上述算法。6. （*）综合训练：采用几组不同数据测试各个排
2、序算法的性能（比较次数和移动次数）。实验过程及内容：/头文件#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;/对两个数值型关键字的比较#
3、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 le
4、ngth;/顺序表长度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 QuickS
5、ort(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(S
6、qList 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
7、赋值 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); ShellSor
8、t(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(简单选择排
9、序后: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输入
10、有误，请输入正确的选项！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
