资源描述：
《数据结构内部排序比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构实训报告实验名称：数据结构题目：内部排序比较专业：班级：姓名：学号：实验日期：一、实验目的：通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。训练学生综合设计算法能力。二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。三、实验内容1、待排序表的表长不小于100；至少要用5组不同的输入数据作比较；排序算法不少于3种；2、待排序的元素的关键字为整数；3、比较的指标为有关键字参加的比较次数和关
2、键字的移动次数(关键字交换以3次计)。4、演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。5、最后要对结果作简单的分析。6、测试数据：用伪随机数产生程序产生。四、实验编程结果或过程：1.数据定义typedefstruct{KeyTypekey;}RedType;typedefstruct{RedTyper[MAXSIZE+1];intlength;}SqList;2.函数如下，代码详见文件“排序比较.cpp”intCreate_Sq(SqList&L)voidBubble_sort(SqList&L)//冒泡排序voidInsertSor
3、t(SqList&L)//插入排序voidSelectSort(SqList&L)//简单选择排序intPartition(SqList&L,intlow,inthigh)voidQSort(SqList&L,intlow,inthigh)//递归形式的快速排序算法voidQuickSort(SqList&L)voidShellInsert(SqList&L,intdk)//希尔排序voidShellSort(SqList&L,intdlta[])3.运行测试结果，运行结果无误，如下图语速个数为20元素个数为100错误调试无。影响排序的因素：1、待排序的记录数目n的大小。2、记录
4、本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。3、关键字的结构及其分布情况。4、对排序稳定性的要求五、实验总结：（1）实验中的存在问题和提高1、存在问题：程序有待增强。2、提高：界面处理简洁。（2）收获与体会：1、随机数的生成；2、排序的算法的比较次数与移动次数的计算3、各种排序的算法附录源程序/*一.选择排序算法：算法基本原理：一次选定数组中的每一个数，记下当前位置并假设它是从当前位置开始后面数中的最小数min=i，从这个数的下一个数开始扫描直到最后一个数，并记录下最小数的位置min，扫描结束后如果min不等于i，说明假设错误，否则交换min与i位置上数。算法实现
5、：*/#include//选择排序，如果第一个数字小于后面的则向后移动，依次类推//该排序时不稳定的，时间复杂度是N平方intmain(){intarray[10]={112,4,2,3,5,33,6,7,8,9};//定义一个数组intlength=sizeof(array)/sizeof(array[0]);//得到数组的长度intmin,k=0,s=0,i=0,j=0;//k保存临时结果，s，i，j为循环变量//选择排序开始for(i=0;iarr
6、ay[j]){min=j;}if(min!=i){k=array[i];array[i]=array[j];array[j]=k;}}}//选择排序结束，输出显示排序的结果for(s=0;s//冒泡
7、排序,开始的时候两个数进行比较，大的向后小的向前，第一次比较很容易的就把最大的一个数字放到了最后小的呢，继续向前，第二次当然也找到了第二个大的，放到倒数第二的位置，如此下去便可。这个是优化的冒泡排序方法，让k=j保存最后的那个数的下标，这样k后面的数都是排序好的了,这个排序是稳定的，时间复杂度是N平方intmain(){intarray[10]={1,2,11,22,33,4,23,234,4,6};intlength=sizeof(array)/sizeof(array[0])
