《实验报告-各种排序方法及其实现》由会员分享，可在线阅读，更多相关《实验报告-各种排序方法及其实现（8页珍藏版）》请在金锄头文库上搜索。
1、计算机学院实验报告专用纸实验室：网络实验室 机号：网38 实验日期：2010年6月25日姓名XXX班级课程名称数据结构任课教师实验项目名称各种排序方法及其实现指导教师实验组别X同组者无教师评语及成绩： 实验成绩： 教师签字： （请按照实验报告的有关要求书写。一般必须包括：1、实验目的；2、实验内容；3、实验步骤与方法；4、实验数据与程序清单；5、出现的问题与解决方法；6、实验结果、结果分析与体会等内容）1、实验目的（1）理解排序的定义和各种排序方法的特点（2）掌握各种排序方法的排序过程及其依据的原则（3）掌握各种排序方法的时间复杂度的分析方法2、实验内容（1）实现直接排序、冒泡、直接选择、快速
2、、堆、归并排序算法；（2）比较各种算法的运行速度。3、实验步骤和方法（1）编写各种排序法函数；（2）设计一个测试主函数，实现对各种排序算法的测试。（3）分析程序的运行结果。4、实验数据与程序清单计算机学院实验报告附页姓名XXX班级实验名称各种排序方法及其实现#includestdio.h#includestdlib.h#define Max 100 /假设文件长度typedef struct /定义记录类型 int key; /关键字项RecType;typedef RecType SeqListMax+1; /SeqList为顺序表，表中第0个元素作为哨兵int n; /顺序表实际的长度/=
3、直接插入排序法=void InsertSort(SeqList R) /对顺序表R中的记录R1n按递增序进行插入排序 int i,j; for(i=2;i=n;i+) /依次插入R2，Rn if(Ri.keyRi-1.key) /若Ri.key大于等于有序区中所有的keys，则Ri留在原位 R0=Ri;j=i-1; /R0是Ri的副本 do /从右向左在有序区R1i-1中查找Ri的位置 Rj+1=Rj; /将关键字大于Ri.key的记录后移 j-; while(R0.keyRj.key); /当Ri.keyRj.key 是终止 Rj+1=R0; /Ri插入到正确的位置上/endif/=冒泡排序
4、= typedef enum FALSE,TRUE Boolean; /FALSE为0，TRUE为1void BubbleSort(SeqList R) /自下向上扫描对R做冒泡排序 int i,j; Boolean exchange; /交换标志for(i=1;i=i;j-) /对当前无序区Rin 自下向上扫描 if(Rj+1.keyRj.key) /两两比较，满足条件交换记录R0=Rj+1; /R0不是哨兵，仅做暂存单元Rj+1=Rj;Rj=R0;exchange=TRUE; /发生了交换，故将交换标志置为真 if(! exchange) /本趟排序未发生交换，提前终止算法 return;
5、 /endfor（为循环）计算机学院实验报告附页姓名XXX班级实验名称各种排序方法及其实现/=一次划分函数=int Partition(SeqList R,int i,int j) / 对Rij做一次划分，并返回基准记录的位置 RecType pivot=Ri; /用第一个记录作为基准 while(ij) /从区间两端交替向中间扫描，直到i=j while(i=pivot.key) /基准记录pivot相当与在位置i上 j-; /从右向左扫描，查找第一个关键字小于pivot.key的记录Rjif(ij) /若找到的Rj.key pivot.key，则 Ri+=Rj; /交换Ri和Rj，交换后i
6、指针加1while(ij &Ri.key=pivot.key) /基准记录pivot相当与在位置j上 i+; /从左向右扫描，查找第一个关键字小于pivot.key的记录Riif(i pivot.key，则 Rj-=Ri; /交换Ri和Rj，交换后j指针减1 Ri=pivot; /此时，i=j，基准记录已被最后定位 return i; /返回基准记录的位置/=快速排序=void QuickSort(SeqList R,int low,int high) /Rlow.high快速排序 int pivotpos; /划分后基准记录的位置 if(lowhigh) /仅当区间长度大于1时才排序pivo
7、tpos=Partition(R,low,high); /对Rlow.high做一次划分，得到基准记录的位置QuickSort(R,low,pivotpos-1); /对左区间递归排序QuickSort(R,pivotpos+1,high); /对右区间递归排序 /=直接选择排序=void SelectSort(SeqList R) int i,j,k; for(i=1;in;i+) /做第i趟排序（1in-1）k=i;for(j=i+1;j=n;j+) /在当前无序区Rin中选key最小的记录Rk if(Rj.keyRk.key)k=j; /k记下目前找到的最小关键字所在的位置if(k!=i
8、) / /交换Ri和Rk R0=Ri;Ri=Rk;Rk=R0; /endif计算机学院实验报告附页姓名XXX班级实验名称各种排序方法及其实现 /endfor/=大根堆调整函数=void Heapify( SeqList R,int low,int high) / 将Rlow.high调整为大根堆，除Rlow外，其余结点均满足堆性质 int large; /large指向调整结点的左、右孩子结点中关键字较大者 RecType temp=Rlow; /暂存调整结点 for(large=2*low; largehigh,则表示Rlow是叶子，调整结束；否则先令large指向Rlow的左孩子if(la
9、rgehigh & Rlarge.key=Rlarge.key) /temp始终对应Rlow break; /当前调整结点不小于其孩子结点的关键字，结束调整Rlow=Rlarge; /相当于交换了Rlow和Rlargelow=large; /令low指向新的调整结点，相当于temp已筛下到large的位置 Rlow=temp; /将被调整结点放入最终位置上/=构造大根堆=void BuildHeap(SeqList R) /将初始文件R1.n构造为堆 int i; for(i=n/2;i0;i-)Heapify(R,i,n); /将Ri.n调整为大根堆/=堆排序=void HeapSort(S
10、eqList R) /对R1.n进行堆排序，不妨用R0做暂存单元 int i; BuildHeap(R); /将R1.n构造为初始大根堆 for(i=n;i1;i-) /对当前无序区R1.i进行堆排序，共做n-1趟。R0=R1; R1=Ri;Ri=R0; /将堆顶和堆中最后一个记录交换Heapify(R,1,i-1); /将R1.i-1重新调整为堆，仅有R1可能违反堆性质。 /=将两个有序的子序列Rlow.m和Rm+1.high归并成有序的序列Rlow.high=void Merge(SeqList R,int low,int m,int high) int i=low,j=m+1,p=0; /置初始值 RecType *R1; /R1为局部量计算机学院实验报告附页姓名XXX班级实验名称各种排序方法及其实现 R1=(RecType *)malloc(high-low+1)*sizeof(RecType); /申请空间 while(i=m & j=high) /两个子序列非空时取其小者输出到R1p上R1p+=(Ri
