实验 8 实验日志
实验日期：2019 年 12 月 16 日星期一 学院：信息科学与工程学院 专业：计算机科学与技术
班级：计科 1802 学号：201808010205 姓名：展双龙
一、实验目的
基于教材内容，任选两种排序算法，实现并比较性能。
二、基本要求
（1）至少要有一种排序算法的性能优于O(n2)；
（2）对实现的排序算法进行实验比较，实验比较数据参见教材7.8章节；
（3）排序算法要基于教材，测试输入的整数数据文件（5个，文件中数据规模分别是100，1K，10K，100K和1M），排序结果也要输出到文件中； （4）要在屏幕上输出排序过程所花费时间；
三、实验内容
选择shell排序、快速排序两种排序方法进行实验。 与实验8相似，首先写了一个生成5种不同大小数据文件的程序，主要运用了随机函数以及文件流，接着选用了QueryPerformanceCounter来获得精确的时间。 用两个数组分别存放相同的来自于数据文件的数据，用两种排序算法分别对两个含元素相同的数组进行排序，保证两个排序算法所进行的排序对象相同。
使用两个函数分别计算shell排序与快速排序的时间，记录下每种方法所用的时间，以ms为单位。在函数中将查找时间和查找结果都写入了文件中，可以去查看，以下是对时间的整合表格：
排序方法 规模 100 1K
时间 0.0149 0.462 5.9928 75.9016 6184.15
时间单位
shell
10K 100K 1M
ms
100 1K
快速排序
10K 100K 1M
0.0129 0.2338 1.6215 20.133 192.93
四、结果分析
从表中可以看出，快速查找总的来说比shell要快，尤其是数据规模变得越来越大的时候。在数据呈指数上升时，明显可以看出快速排序算法比shell快了很多，从时间复杂度方面分析，shell排序的时间复杂度在最优的情况下，为：O（n ^ (1.3) ） （元素已经排序好顺序），但在最差的情况下，为：O（n ^ 2），事实上shell排序算法在数据规模较小或中等规模的情况下的速度并没有比快速排序慢多少；而快速是排序的时间复杂度则是更好的O（nlogn），数据规模较大时确实是要快得多。 当然，上面的数据因为个人电脑以及运行环境和随机数的生成方式等等因素不可能是完全准确的。
5个数据文件的生成程序与实验8中的完全相同，因此源码包中不再累赘。 注：源码包中的out开头的txt是输出文件，其余的txt是待查数据。
相关推荐：
loading