实验报告-各种排序方法及其实现.docVIP

计算机学院实验报告专用纸实验室：网络实验室 机号：网38 实验日期：2010年6月25日姓名XXX班级课程名称数据结构任课教师实验项目名称各种排序方法及其实现指导教师实验组别X同组者无教师评语及成绩： 实验成绩： 教师签字： （请按照实验报告的有关要求书写。一般必须包括：1、实验目的；2、实验内容；3、实验步骤与方法；4、实验数据与程序清单；5、出现的问题与解决方法；6、实验结果、结果分析与体会等内容）1、实验目的（1）理解排序的定义和各种排序方法的特点（2）掌握各种排序方法的排序过程及其依据的原则（3）掌握各种排序方法的时间复杂度的分析方法2、实验内容（1）实现直接排序、冒泡、直接选择、快速、堆、归并排序算法；（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; /顺序表实际的长度/=直接插入排序法=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/=冒泡排序= 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; /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指针加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时才排序pivotpos=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) / /交换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(largehigh & 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(SeqList 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.key=Rj.key)? Ri+:Rj+; while(i=m) /若第一个子序列非空，则复制剩余记录到R1R1p+=Ri+; while(j=high) /若第二个子序列非空，则复制剩余记录到R1中R1p+=Rj+; for(p=0,i=low;i=high;p+,i+)Ri=R1p; /归并完成后将结果复制回Rlow.high/=对R1.n做一趟归并排序=void MergePass(SeqList R,int length) int i; for(i=1;i+2*length-1=n;i=i+2*length)Merge(R,i,i+length-1,i+2*length-1); /归并长度为length的两个相邻的子序列 if(i+length-1n) /尚有一个子序列，其中后一个长度小于lengthMerge(R,i,i+length-1,n); /归并最后两个子序列 /注意：若in且i+length-1n时，则剩余一个子序列轮空，无须归并/= 自底向上对R1.n做二路归并排序=void MergeSort(SeqList R) int length; for(length=1;lengthn;length*=2) /做lgn趟排序MergePass(R,length); /有序长度n时终止/=输入顺序表=void input_int(SeqList R) int i; printf(Please input num(int):); scanf(%d,&n); printf(Plase input %d integer:,n); for(i=1;i=n;i+)scanf(%d,&Ri.key);/=输出顺序表=void output_int(SeqList R) int i;计算机学院实验报告附页姓名XXX班级实验名称各种排序方法及其实现 for(i=1;i=n;i+) printf(%4d,Ri.key);/=主函数=void main() int i; SeqList R; input_int(R); printf(t* Select *n); printf(t1: Insert Sortn); printf(t2: Bubble Sortn); printf(t3: Quick Sortn); printf(t4: Straight Selection Sortn); printf(t5: Heap Sortn); printf(t6: Merge Sortn); printf(t7: Exitn); printf(t*n); scanf(%d,&i); /输入整数1-7，选择排序方式 switch (i)case 1: InsertSort(R); break; /值为1，直接插入排序case 2: BubbleSort(R); break; /值为2，冒泡法排序case 3: QuickSort(R,1,n); break; /值为3，快速排序case 4: SelectSort(R); break; /值为4，直接选择排序case 5: HeapSort(R); break; /值为5，堆排序case 6: MergeSort(R); break; /值为6，归并排序case 7: exit(0); /值为7，结束程序 printf(Sort reult:); output_int(R);5、实验结果Please input num(int):10 Plase input 10 integer:265 301 751 129 937 863 742 694 计算机学院实验报告附页姓名XXX班级实验名称各种排序方法及其实现76 438 * Select * 1: Insert Sort 2: Bubble Sort 3: Quick Sort 4: Straight Selection Sort 5: Heap Sort 6: Merge Sort 7: Exit * 1 129, 265, 301, 751, 937, 863, 742, 694, 76, 438, 129, 265, 301, 751, 863, 937, 742, 694, 76, 438, 129, 265, 301, 742, 751, 863, 937, 694, 76, 438, 129, 265, 301, 694, 742, 751, 863, 937, 76, 438, 76, 129, 265, 301, 694, 742, 751, 863, 937, 438, 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 276,265,301,751,129,937,863,742,694,438,76,129,265,301,751,438,937,863,742,694,76,129,265,301,438,751,694,937,863,742,76,129,265,301,438,694,751,742,937,863,76,129,265,301,438,694,742,751,863,937,Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937,376,129,265,751,937,863,742,694,301,438,76,129,265,751,937,863,742,694,301,438,76,129,265,438,301,694,742,751,863,937,76,129,265,301,438,694,742,751,863,937,76,129,265,301,438,694,742,751,863,937,76,129,265,301,438,694,742,751,863,937,Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937,476,301,751,129,937,863,742,694,265,438,76,129,751,301,937,863,742,694,265,438,76,129,265,301,937,863,742,694,751,438,76,129,265,301,438,863,742,694,751,937,76,129,265,301,438,694,742,863,751,937,76,129,265,301,438,694,742,751,863,937,计算机学院实验报告附页姓名XXX班级实验名称各种排序方法及其实现Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937,5863,694,751,265,438,301,742,129, 76,937,751,694,742,265,438,301, 76,129,863,937,742,694,