任洛漪 电子科技大学成都学院 计算机系

1 引言

各种排序算法时间复杂度比较部分是《数据结构》课程的重难点。如果光讲理论，学生理解比较肤浅，因此我们尝试在教学中用实验的方法让学生切身感受到各种排序算法的区别。

2 时间测量方法的准备

首先需要找到精确的时间测量方法。

常规的计时用是头文件中的clock()函数，精度为1ms，但对于插入排序和冒泡排序对1000 个正序序列排序的情况，耗时只有几十微秒，故需要设计精确到微秒的测量方式。

代码如下

double run_time；

_LARGE_INTEGER time_start；

_LARGE_INTEGER time_over；

double dpFreq；

_LARGE_INTEGER f；

void StartTimer() {

QueryPerformanceCounter(&f)；

dpFreq = (double)f.QuadPart；

QueryPerformanceCounter(&time_start)；}

void EndTimer() {

QueryPerformanceCounter(&time_over)；

run_time = 1000000 * (time_over.QuadPart - time_start.QuadPart) / dpFreq；}

实际使用中，在做排序之前调用StartTimer()开始计时，排序之后立刻调用EndTimer()结束计时。时间间隔记录到全局变量run_timer 中。

3 测试数据的准备

由于初始记录的关键字的分布情况不同，排序算法的耗时也不同。故需要准备以下三种序列。

a)、正序初始序列，存放关键字递增的数据序列。

b)、逆序初始序列，存放关键字递减的数据序列。注意，由于排序基本都是原地重排，为了避免上一次排序的干扰，每次对逆序序列排序之前都必须重新生成逆序序列。

c)、随机数初始序列，存放关键字为随机数的数据序列。随机序列进行比较之前需要生成一个随机序列并将其复制多份，每个排序方式排一份数据，以便让每种排序方法都针对相同序列并互不干扰。

4 实验设计

基于以问题为导向，试验将回答以下问题：

（1）对于正序序列的表，最省时间的排序方式为哪种算法？最费时间的又是哪种算法？

为此我们设计了了下列实验，首先对正序序列赋值，然后使用直接插入排序、冒泡排序、简单选择排序、快速排序、堆排序、两路归并排序分别对该序列进行排序。并分别计时，生成结果如下：

图1 正序序列情况下各种排序算法时间复杂度比较

可见，冒泡排序只需0.026 毫秒，在六种排序算法中耗时最少，因为正序情况下，它的时间复杂度为O(n)。

同时可见，与冒泡法时间复杂度相同的直接插入法，耗时更大。因为虽然执行次数相同，但每次循环中，直接插入法的还需执行移动，而同等情况下冒泡算法几乎没有移动次数，故速度更快。

并且对于正序序列，基准为第一个元素的快速排序并不占优势，它的耗时仅次于简单选择排序，因为这种情况下，快速排序对应的二叉排序树退化为一颗单枝树，时间复杂度为O(n2)。

对于正序序列，最费时的是简单选择，因为同样的实际复杂度O(n2)下，它的比较次数比快速排序要多。

（2）对于逆序序列，哪种算法最耗时？哪种最省时？实验结果为

图2 逆序序列情况下各种排序算法时间复杂度比较

可见，对于1000 个数的逆序序列，堆排序和归并排序时间性能最好，时间复杂度为O(nlog2n)。直接插入，冒泡，简单选择和快速排序的耗时较长，时间复杂度都为O(n2)。

在后四个算法中，最快的是选择排序，因其移动的次数最少。快速排序在这种情况下比较和移动的次数类似于选择排序，但由于使用递归需要系统分配时间调用递归栈，所以耗时比选择排序略高。冒泡和插入由于在逆序情况下移动和比较的次数都达到了最大值，所以排序性能不好。

（3）对于随机序列，哪种算法最耗时？哪种最省时？实验结果为

图3 随机序列情况下各种排序算法时间复杂度比较

可见，对于1000 个数以内的随机序列，快速排序、堆排序和归并排序时间性能最好。因为这种情况下，时间复杂度为O(nlog2n)。直接插入，冒泡，简单选择的耗时都较长，因为这种情况下时间复杂度都为O(n2)。

5 结论

通过实验，学生对下图各种排序的时间性能有了更直观和深入的理解。教学收到了较好的效果。