2010数据结构实验指导书48

int getInfo() const { return ID; }

const string& getkey () const { return name; } };

由于排序是基于比较的，所以可排序的对象一定要定义比较算符，有的排序算法需要比较算符operator < 有的需要operator <=，这和能放入散列表的对象不同（要定义!=和/或==）。它们应该是类成员还是友元？

试用内插排序、归并排序和快速排序对以下数组以name做关键字排序 Bird MyBirds[14] = {

Bird(19, "robin"), Bird(14, "sparrow"), Bird(23, "hawk"), Bird( 1, "eagle"), Bird(68, "seagull"), Bird(20, "bluejay"), Bird(24, "hawk"), Bird(84, "owl"), Bird(27, "cardinal"), Bird(55, "Jakana"), Bird(11, "Moa"), Bird(10, "Egret"), Bird(79, "Penguin"), Bird(25, "hawk") }; 注意：

1、 这个数组和实验5略有不同，name为"hawk"的有3项，其ID不同，是为了让同学们观

察排序算法是否稳定；

2、 教科书给的排序算法都是对vector类型的，也就是应该对vector <Bird> V排序，但vector

没有{ … }的初始化形式，所以这里以数组的形式初始化。实验中做各种排序时，可以用循环把数组的各元素赋给vector。

实验课题二：实测比较各排序算法的运行时间。

1、定义长度为N的数组（C）或vector（C++），用0到N-1之间的随机整数对各元素赋值； 2、用内插排序、归并排序和快速排序对其排序，记录排序的时间； 3、用不同的N做几次测试，比较各排序算法所用的时间。

最初可以取N = 1000，你可能得不到有效的测试结果，接下来，你可能会令N = 10000，这时的测试数据会比较有意义了，再接着你可能想把N再扩大10倍，这里要提醒同学们，内插排序的时间复杂度是O (N2)，当N扩大10倍，它需要的排序时间大致要扩大上百倍，你有这个耐心等待吗？所以请同学们小心，对较大的N，只应对O(N log N)的算法测试； 4、当测试框架搭好后，很方便对其它排序作测试，所以鼓励同学们对Shell排序、堆排序等，甚至STL 中的sort、stable_sort（用迭代器指定排序范围），都可一并作比较测试； 5、注意记录整理测试结果好写入实验报告。

【实验参考程序】

C和C++描述的排序算法的实现分别在各自的Sort.h内。

C++ 版还有：TestSort.cpp和Random.h、Random.cpp，后面2个用于产生伪随机数。TestSort已经搭了一个测试框架，对书中各种排序甚至选择算法作了测试，但没有测排序时间，用C写的同学也可以参考（时间测试见下面）。