内部排序比较(实验报告源程序)C.doc

《内部排序比较(实验报告源程序)C.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告3实验名称：数据结构与软件设计实习题目：内部排序算法比较专业：生物信息学班级：01姓名：学号：实验日期：2010.07.24一、实验目的：比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序；二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。三、实验内容对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。将排序算法进行合编在一起，

2、可考虑用顺序执行各种排序算法来执行，最后输出所有结果。四、实验编程结果或过程：1.数据定义typedefstruct{KeyTypekey;}RedType;typedefstruct{RedTyper[MAXSIZE+1];intlength;}SqList;2.函数如下，代码详见文件“排序比较.cpp”intCreate_Sq(SqList&L)voidBubble_sort(SqList&L)//冒泡排序voidInsertSort(SqList&L)//插入排序voidSelectSort(SqList&L)//简单选择排序i

3、ntPartition(SqList&L,intlow,inthigh)voidQSort(SqList&L,intlow,inthigh)//递归形式的快速排序算法voidQuickSort(SqList&L)voidShellInsert(SqList&L,intdk)//希尔排序voidShellSort(SqList&L,intdlta[])3.运行测试结果，运行结果无误，如下图语速个数为20元素个数为100错误调试无。排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)起泡排序O(n2)O

4、(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)~O(n)简单选择排序O(n2)O(n2)O(n2)O(1)希尔排序O（n1..3）O（1）调试分析：时间复杂度与空间复杂度：理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示（图6）：影响排序的因素：u待排序的记录数目n的大小。u记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。u关键字的结构及其分布情况。u对排序稳定性的要求从结果中还可看出：对于一般的排序，比较次数多，而交换次数相对较少；而快速排序比较次数和交

5、换次数都较少，两者相差不如前者大。其中冒泡排序比较和交换次数都很大。五、实验总结：（1）实验中的存在问题和提高存在问题：程序有待增强。提高：界面处理简洁。（2）收获与体会各种排序的算法排序的算法的比较次数与移动次数的计算随机数的生成附录源程序#include#include#include#include#defineLS(a,b)((a)<(b))#defineLL(a,b)((a)>(b))#defineMAXSIZE10000typedefintKe

6、yType;typedefstruct{KeyTypekey;}RedType;typedefstruct{RedTyper[MAXSIZE+1];intlength;}SqList;intcompare=0;intchange=0;intCreate_Sq(SqList&L){intk;cout<<"20074795元素个数:";cin>>k;L.length=k;srand(time(NULL));for(intx=1;x<=k;x++){L.r[x].key=rand()%k;//随机域为0~k}return1;}voidBub

7、ble_sort(SqList&L)//冒泡排序{inti,j,l,k=L.length,m=0,n=0;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<

8、<