北邮数据结构实验报告实验四

北京邮电大学信息与通信工程学院第1页北京邮电大学电信工程学院第1页2009级数据结构实验报告实验名称：实验四——排序学生姓名：班级：班内序号：学号：日期：2010/12/171．实验要求实验目的：通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容：使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序7、归并排序8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。2.程序分析2.1存储结构使用最简单的一维数组存储待排序的数据。共使用两个数组，一个用来存储原始数据，一个用来存储待排序数据。每次排序完毕，用原始数据更新一次待排序数据，保证每一次都对同一组数据排序。（图略）2.2关键算法分析1.直接插入的改进：在一般的直接插入中，关键码每移动一次就需要比较一次。在移动的方面，优化是比较困难的，因为对静态线性表的插入必然要带来大量的移动。但是，我们可以在比较上进行一些优化。在查找技术一张曾学过的“折半查找法”，在这里就可以照葫芦画瓢地运用。一趟排序的伪代码如下： 1.如果该元素大于处于其左侧相邻的元素则跳过该元素； 2.low=0，high=i； 3.循环直至low==high 3.1mid=(low+high)/2； 3.2如果当前元素大于中值high=mid； 3.3否则low=mid+1； 4.当前元素赋值给临时变量； 5.将有序区中处于low位置及其右侧的元素右移； 6.临时变量置于low位置简单说一下这里的折半查找与一般查找算法的区别。这里的查找，尤其是对无重复数据和大量数据的处理中，更多的时候是找不到完全相等的项的。所以忽略这种情况，每次查找都进行到正常查找算法中查找失败的情形。由于待选插入位置的数量为有序区项数加一，而在比较前加入的判断可将插入位置为有序去最末端（既不需移动）的情况特殊处理，所以实际待选插入位置数量与有序区项数相等，可用最终插入空当的右侧元素下标标记查找位置。基于这种思想，我们设计了这样的算法。插入值小于中值时，mid作为新的上限；大于中值时，将mid+1作为新的下限。这样可以保证待选插入空当一直保持在mid左侧，而且当low==high时恰好可以指向最终插入位置。该算法时间复杂度为O(n2)，空间复杂度O(1)。2.冒泡排序的改进在某趟排序中，如果需要进行相邻的连续交换，可以像插入排序那样先集体右移，最后定位原始左侧的数据。一趟排序的伪代码如下：1.对无序区元素ai自左至右循环 1.1如果该元素小于处于其右侧相邻的元素则跳过该元素； 1.2当前元素赋值给临时变量； 1.3当前元素右侧相邻元素左移； 1.4i++； 1.5循环直到临时变量小于或等于当前元素右侧相邻元素或已达序列尾部 1.5.1 1.5.2i++ 1.6临时变量置于当前位置；关于以上代码，由于较易理解，这里就不做更多的说明了。该算法时间复杂度为O(n2)，空间复杂度O(1)。3.快速排序的非递归算法及改进一般来说，递归算法由于传递参数和返回值的因素会影响效率，而且容易造成系统栈溢出，所以使用非递归算法会较好一些。另外，一趟排序中的轴值是始终不变的，不需要反复赋值，只需要先存入临时变量，确定位置后再写入即可。相关伪代码如下：1.建立两个栈，存储子列头尾，共用栈顶； 2.序列首尾相应入栈； 3.循环直到栈空 3.1栈顶元素出栈，用i,first接受头，j,last接收尾； 3.2首项赋值给轴值； 3.3无条件循环 3.3.1循环直至aj 3.3.1 3.3.3ai 3.3.4i++ 3.3.5循环直至ai 3.3.5.1i++ 3.3.6 3.3.7aj赋值给a 3.3.8j-- 3.4轴值赋值给ai； 3.5若轴值左侧子列存在且大于一个元素 3.5.1 3.6若轴值右侧子列存在且大于一个元素 3.6.1该算法时间复杂度为O(nlog2n)，空间复杂度O(1)。2.3其他.关于输入除了系统自动生成的三种数列外，程序设计了让用户手动输入的接口。这里用到了cin的容错机制，增强了程序的健壮性，并利用该容错机制接受结束符控制输入结束，并返回输入长度。相关代码如下：template<typenameT>intInput(T*a,intmaxsize){ intlength=0; while(1) { cin>>a[length]; if(cin.fail())//若输入流读入非数字字符 { cin.clear(); charc; cin>>c; cin.sync(); if(c=='#'&&length>0)//若读入截止符且输入有效数据非空 break; } else { length++; if(length==maxsize) break; } } returnlength;}3.程序运行结果开始数组初始化开始数组初始化键盘读入按键key?产生正序序列产生逆序序列产生随机序列键盘读入序列键盘读入按键key?使用相应算法进行排序并统计时间打印比较次数、移动次数及算法时间打印序列结束abcdelseia~gh测试结果：（规模n=10000）（注：该结果为PentiumDualCore1.73GHz上省电模式下测得的数据）正序序列比较次数移动次数时间(ms)插入排序999900希尔排序12000500冒泡排序999900快速排序5000499919998704简单选择排序4999500029997875堆排序24457639586816归并排序13632014000016逆序序列比较次数移动次数时间(ms)插入排序13361650014998766希尔排序24344424689115冒泡排序50005000500149981265快速排序5000499924998703简单选择排序4999500029997922堆排序22672035008815归并排序13632014000016随机序列比较次数移动次数时间(ms)插入排序12895324934235390希尔排序31010737790215冒泡排序49937479415868791547快速排序1725176524616简单选择排序4999500029997875堆排序23555637297515归并排序136320140000154.总结本次实验中遇到的问题主要还是对循环条件的控制，由于写代码时几乎完全没有参考书上的代码