实验6 排序算法的计算复杂度


实验时间

4-6课时。

实验目的

1. 掌握各种排序算法。
2. 学习测量程序运行时间的方法。

问题描述

在课程学习中,我们已经知道不同的排序算法具有不同的时间复杂度,那么在具体应用中,各种排序算法的运行时间究竟相差多少?通过这个实验,对程序运行时间进行实际的测量,可以直观感受到时间复杂度与问题规模的关系。

实验内容

为了公平起见,我们应该使用同一个无序序列作为输入,来测量不同排序算法的运行时间。那么无序序列如何得到?一种方法是,先生成一个长度为N的有序序列,再将该序列随机重排(random shuffle),从而得到一个长度为N的无序序列。
测量程序的运行时间,我们可以使用C/C++语言提供的计时器。需要注意的是,该计时器的灵敏度比较低,在Windows系统中,一般只有当两组运行时间相差0.1秒以上时,才能认为这两组时间是有差别的。
本实验要求编程实现至少5种排序算法(快速、堆、归并必做,其他选做),并在不同N值(如10000、100000、1000000)的条件下多次运行程序计算平均运行时间。实验报告应对不同算法的运行时间进行比较分析。

实现提示

部分程序代码示例如下: