《数据结构》上机实验报告—常用排序算法的实现

1、福州大学数计学院数据结构上机实验报告专业和班级：信息计算科学与应用数学6班学号姓名成绩实验名称排序实验实验内容常用排序算法的实现实验目的和要求【实验目的】熟悉并掌握各种排序算法的思想方法和实现该算法的基本技术【实验内容】从键盘输入一组关键字序列分别实现下列排序: 1.实现简单选择排序、直接插入排序和冒泡排序。 2.实现快速排序算法。 3.实现折半插入排序。4.采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。【实验要点及说明】在主函数中设计一个简单的菜单，分别测试上述算法，最后要在屏幕上输出排序后的记录。问题描述和主要步骤主要程序：#include<iostream.h>

2、;#include<stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -1const int MAXSIZE=30; /顺序表的最大长度typedef structint key; /关键字项int data;record; /记录类型typedef structrecord rMAXSIZE+1;int length; /顺序表长度Form; /顺序表类型int Init_Form(Form &F)int i;for(i=0;i<=F.length;i+)F.r1.key=F.ri.data=0;return

3、OK;int print(Form &F,int comp,int move)int i;cout<<"关键字 数据项"<<endl;for(i=1;i<=F.length;i+)cout<<" "<<F.ri.key<<" "<<F.ri.data<<endl;cout<<"比较次数为："<<comp<<endl;cout<<"移动次数为："<

4、<move<<endl;return OK;int InsertSort(Form &F)/对顺序表F作直接插入排序int i,j;int comp=0;/比较次数int move=0;/移动次数for(i=2;i<=F.length;i+)comp+;if(F.ri.key<F.ri-1.key)F.r0=F.ri; /F.r0是监视哨F.ri=F.ri-1;j=i-2;comp+;if(F.r0.key<F.rj.key)/进行元素移动，以腾出位置插入F.riF.rj+1=F.rj;/ 记录后移j-;move+;F.rj+1=F.r0; /在j+

5、1处插入F.ricout<<"直接插入排序的结果为："<<endl;print(F,comp,move);return OK;int Partition(Form &F,int low,int high);int QuickSort(Form &F,int low,int high)/快速排序法int comp=0;int move=0;if(low<high)comp+;int p=Partition(F,low,high);QuickSort(F,low,p-1);QuickSort(F,p+1,high);cout<

6、<"快速排序的结果为："<<endl;print(F,comp,move);return OK;int Partition(Form &F,int low,int high)int comp=0;int move=0;F.r0=F.rlow;int p=F.rlow.key;while(low<high)comp+;if(low<high&&F.rhigh.key>=p)high-;move+;F.rlow=F.rhigh;if(low<high&&F.rlow.key<=p)low+;move+;F.rhigh=F.rlow;F.rlow=F.r0;return low;void main()Form F;Init_Form(F);int n;cout<<"请输入顺序表的长度:"cin>>n;F.length=n;cout<<"请输入数据:"<<endl;for(int i=1;i<F.length+1;i+)cin>>F.ri.key>>F.ri.d