排序实验报告

《排序实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

数据结构实验报告专业班级：计算机科学与技术16-1班姓名：王贯东学号：2016211990日期：2017年2月26日一、实验目的和要求完成尽量大的数据排序，并显示运行时间，并在对等的情况下比较三份作业进行分析。二、实验环境软件环境：DevC++，Win10硬件环境：i76700HQGTX960M三、实验内容完成三种排序并写出实验报告四、实验过程4.1任务定义和问题分析生成随机数存入文档，使用时间函数记录时间，在数据相同的情况下比较不同排序算法的排序时间空间效率。4.2数据结构的选择和概要设计直接插入排序：生成100个随机数存入data.txt并读取数据，进行插入排序，显示每一轮排序后的数据并显示时间。冒泡排序：读取data.txt,进行冒泡排序，显示每一轮排序后的数据并显示时间。快速排序：读取data.txt,进行快速排序，并显示时间。4.3详细设计直接插入排序：

1首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1);然后将R[k..i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。冒泡排序：1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。3.针对所有的元素重复以上的步骤，除了最后一个。4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。快速排序：1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；5）重复第3、4步，直到i=j；(3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i，j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。五、测试及结果分析5.1实验数据4118467633426500191691572411478293582696224464570528145232811682799614912995119424827543632391146043902153292123821742118716197181989554472172614771115381869199122566726299170359894287032381131322303331767346641514177112825368682554727644326623275720037128598723974127529778123163035221901842288301069040894219264226482744623805158906729243701535015006311012439335481962912623240841995418756118404966737613931263081694432439246261132355372153816118208222929165415.2结果及分析记录测试结果，实验中遇到的问题和相对应的解决办法，对主要算法的时间和空间等性能的分析结果。要求附上运行界面截图。插入排序：时间复杂度O(n^2),空间复杂度O(1)

2排序时间与输入有关：输入的元素个数；元素已排序的程度。最佳情况，输入数组是已经排好序的数组，运行时间是n的线性函数；最坏情况，输入数组是逆序，运行时间是n的二次函数。·冒泡排序：时间复杂度O(n^2),空间复杂度O(1)，稳定，因为存在两两比较，不存在跳跃。排序时间与输入无关，最好，最差，平均都是O(n^2)

3快速排序：时间复杂度：最坏O（n^2）最好O（n）空间复杂度：递归造成的栈空间的使用，最好情况，递归树的深度logn空间复杂度logn，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(log2n)。由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。六、实验收获快排的效率是最高的，但其缺点十分明显：在待排序列基本有序的情况下，会退化成起泡排

4序，时间复杂度接近O（N^2）。在基本有序的序列中，直接插入排序的效率非常高，增量的选择直接影响排序的效率。插入，冒泡的速度比较慢，但参加排序的序列局部或整体有序时，能达到较快的速度。七、参考文献百度文库，数据结构C++描述八、附录（源代码）