实验报告3实验名称:数据结构与软件设计实习题目:内部排序算法比较专业:生物信息学班级:01 姓名:学号:实验日期:2010.07.24一、实验目的:比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序;二、实验要求:待排序长度不小于100,数据可有随机函数产生,用五组不同输入数据做比较,比较的指标为关键字参加比较的次数和关键字移动的次数;对结果做简单的分析,包括各组数据得出结果的解释;设计程序用顺序存储。
三、实验内容对各种内部排序算法的时间复杂度有一个比较直观的感受,包括关键字比较次数和关键字移动次数。
将排序算法进行合编在一起,可考虑用顺序执行各种排序算法来执行,最后输出所有结果。
四、实验编程结果或过程:1. 数据定义typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length;}SqList;2. 函数如下,代码详见文件“排序比较.cpp”int Create_Sq(SqList &L)void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法void QuickSort(SqList &L)void ShellInsert(SqList &L,int dk)//希尔排序void ShellSort(SqList &L,int dlta[ ])3. 运行测试结果,运行结果无误,如下图语速个数为20元素个数为100错误调试无。
调试分析:时间复杂度与空间复杂度:理论分析可以得出各种排序算法的时间复杂度和空间复杂度,如下表所示(图6):排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)起泡排序O(n2)O (n) O(n2)O(1)快速排序O(n log2n)O(n log2n)O(n2)O(log2n) ~O(n)简单选择排序O(n2)O(n2)O(n2)O(1)希尔排序O(n1..3)O(1)◆待排序的记录数目n 的大小。
◆记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小。
◆关键字的结构及其分布情况。
◆对排序稳定性的要求从结果中还可看出:对于一般的排序,比较次数多,而交换次数相对较少;而快速排序比较次数和交换次数都较少,两者相差不如前者大。
其中冒泡排序比较和交换次数都很大。
五、实验总结:(1)实验中的存在问题和提高存在问题:程序有待增强。
提高:界面处理简洁。
(2)收获与体会随机数的生成附录源程序#include <iostream.h>#include <malloc.h>#include <stdlib.h>#include <time.h>#define LS(a,b) ((a)<(b))#define LL(a,b) ((a)>(b))#define MAXSIZE 10000typedef int KeyType;typedef struct {KeyType key;}RedType;typedef struct {RedType r[MAXSIZE+1];int length;}SqList;int compare=0;int change=0;int Create_Sq(SqList &L){int k;cout<<"元素个数:";cin>>k;L.length=k;srand(time(NULL));for (int x=1; x<=k; x++){L.r[x].key= rand() % k;//随机域为0~k }return 1;}void Bubble_sort(SqList &L)//冒泡排序for(i=1;i<=L.length-1;++i){for(j=1;j<=k-1;++j){++m;if(LL(L.r[j].key,L.r[j+1].key)){l=L.r[j].key;L.r[j].key=L.r[j+1].key;L.r[j+1].key=l;++n;}}--k;}cout<<endl<<"-----冒泡排序后的序列-----"<<endl; for(i=1;i<=L.length;i++)cout<<" "<<L.r[i].key;cout<<endl;cout<<"冒泡排序的比较次数:";cout<<m<<endl;cout<<"冒泡排序的交换次数:";cout<<n<<endl;}void InsertSort(SqList &L)//插入排序{int i,j,m=0,n=0;cout<<endl;for(i=2;i<=L.length;++i)if(LS(L.r[i].key,L.r[i-1].key)){++m;++n;L.r[0]=L.r[i];L.r[i]=L.r[i-1];for(j=i-2;LS(L.r[0].key,L.r[j].key);--j){++m;L.r[j+1]=L.r[j];}L.r[j+1]=L.r[0];}cout<<"-----直接插入排序后的序列-----"<<endl; for(i=1;i<=L.length;i++)cout<<"直接插入排序的比较次数:";cout<<m<<endl;cout<<"直接插入排序的交换次数:";cout<<n<<endl;}void SelectSort(SqList &L) //简单选择排序{int l,i,j,m=0,n=0;cout<<endl;for(i=1;i<L.length;++i){L.r[0]=L.r[i];j=i+1;l=i;for(j;j<=L.length;++j){++m;if(LL(L.r[0].key,L.r[j].key)){l=j;L.r[0]=L.r[j];}}if(l!=i){++n;L.r[l]=L.r[i];L.r[i]=L.r[0];}}cout<<"-----简单选择排序后的序列-----"<<endl; for(i=1;i<=L.length;i++)cout<<" "<<L.r[i].key;cout<<endl;cout<<"简单选择排序的比较次数:";cout<<m<<endl;cout<<"简单选择排序的交换次数:";cout<<n<<endl;}int Partition(SqList &L,int low,int high){int pivotkey;L.r[0]=L.r[low];pivotkey=L.r[low].key;while(low<high){while(low<high&&L.r[high].key>=pivotkey){ ++compare;--high;}while(low<high&&L.r[low].key<=pivotkey){++compare;++low;}++change;L.r[high]=L.r[low];}L.r[low]=L.r[0];return low;}void QSort(SqList &L,int low,int high)//递归形式的快速排序算法{int pivotloc;if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}void QuickSort(SqList &L){int i;QSort(L,1,L.length);cout<<"-----快速排序后的序列为-----"<<endl;for(i=1;i<=L.length;i++)cout<<" "<<L.r[i].key;cout<<endl;cout<<"快速排序的比较次数:";cout<<compare<<endl;cout<<"快速排序的交换次数:";cout<<change<<endl;compare=0;change=0;}void ShellInsert(SqList &L,int dk)//希尔排序{int i;int j;for(i=dk+1;i<=L.length;++i)if(LS(L.r[i].key,L.r[i-dk].key)){++compare;L.r[0]=L.r[i];for(j=i-dk;j>0&&LS(L.r[0].key,L.r[j].key);j-=dk){++compare;}L.r[j+dk]=L.r[0];}}void ShellSort(SqList &L,int dlta[])//希尔排序{int k,j=L.length/2,t=0;while(j>=0){++t;j-=2;}j=L.length/2;for(k=0;k<t;++k)//计算每次的增量值{if(j==0)j=1;//定义最后一趟排序的增量dlta[k]=j;j-=2;}for(k=0;k<t;++k)ShellInsert(L,dlta[k]);cout<<"-----希尔排序后的序列为-----"<<endl; for(k=1;k<=L.length;k++)cout<<" "<<L.r[k].key;cout<<endl;cout<<"希尔排序的比较次数:";cout<<compare<<endl;cout<<"希尔排序的交换次数:";cout<<change<<endl;compare=0;change=0;}void main(){int i;int dlta[MAXSIZE];SqList L,a,b,c,d;Create_Sq(L);a=b=c=d=L;Bubble_sort(L); InsertSort(a); SelectSort(b); QuickSort(c); ShellSort(d,dlta); }。