排序是将一个无序的数据元素（或记录）序列，重新排列成一个按关键字递增（或递
减）的有序序列的过程。在计算机算法设计中，排序占有相当重要的地位。排序分为内排序和外排序。我们只讨论内排序。本课程涉及的主要的内排序算法有：插入排序、Shell排序、归并排序、快速排序等。排序算法有稳定和不稳定之分。
【实验内容】（实验课题一必做，课题二选做）
实验课题一：
【用C描述课本的同学】有以下结构体构成的数组：
struct StudentInfo { {
{\{\{\{\{\{\{\{\{\{\{\{\ };
1 使用直接插入的排序方法按照学号的顺序对以上数组进行排序（递增）；
2 分别用归并排序和快速排序按照姓名的顺序对以上数组进行排序（递增），有3人的名字是\，注意观察排序是否稳定。
char ID[10]; char * name; float score;
}StuInfo[12]=
【用C++描述课本的同学】对实验5中的Bird类数组排序
class Bird {
int ID; // 代表其它信息 string name; // 当作 key public:
Bird() {} // 缺省构造函数
Bird (int k, const string& str = string()):ID(k), name(str){}
16
int getInfo() const { return ID; }
const string& getkey () const { return name; } };
由于排序是基于比较的，所以可排序的对象一定要定义比较算符，有的排序算法需要比较算符operator < 有的需要operator <=，这和能放入散列表的对象不同（要定义!=和/或==）。它们应该是类成员还是友元？
试用内插排序、归并排序和快速排序对以下数组以name做关键字排序 Bird MyBirds[14] = {
Bird(19, \ Bird(14, \ Bird(23, \ Bird( 1, \ Bird(68, \ Bird(20, \ Bird(24, \ Bird(84, \ Bird(27, \ Bird(55, \ Bird(11, \ Bird(10, \ Bird(79, \ Bird(25, \}; 注意：
1、 这个数组和实验5略有不同，name为\的有3项，其ID不同，是为了让同学们观
察排序算法是否稳定；
2、 教科书给的排序算法都是对vector类型的，也就是应该对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写的同学也可以参考（时间测试见下面）。
17
用C的同学可以用C标准库的随机数产生器（C++版实际用的也是它）： #include
// seed就决定了后面调用random产生的序列 // 产生 [0, num-1] 之间的随机数
// 这个头文件包含下列函数的说明
// 随机数产生器初始化，一般应用只需自选seed初始化一
void srand (unsigned seed);
int random (int num);
【时间测试函数】C和C++都可以用
#include
void Settime ()
double Gettime()
// Return the elapsed time since the last call to Settime
{ return (double)((double)clock() - (double)tstart)/ (double)CLOCKS_PER_SEC; } 测试例： Settime ();
// 开始计时，这之后到调用Gettime ()之间是要测试时间的程序段
// elapsedTime 就是这段时间（以秒计）
// Initialize the program timer
{ tstart = clock(); }
// Time at beginning of timed section
// ……待测的语句段 double elapsedTime = Gettime ();
实验七 查找
【实验目的】
1、 掌握几种常用的内部查找算法；
2、熟悉二分查找算法和二叉搜索树的查找过程。
【实验原理】
18
查找又称为检索，就是根据给定的某一个值从一个数据元素集合中找出某个特定的数
据元素。查找和排序一样，是数据处理中经常使用的运算，查找算法的优劣对整个软件系统的影响很大。在一个数据元素集合中进行查找可选用的方法和该数据元素集合的存储结构有很大关系。查找有内查找和外查找之分。对于线性表，主要的内查找算法有顺序查找、二分查找等。但要注意，二分查找只适合于有序的线性表。第4章学的二叉搜索树是搜索性能优良的存储结构。
【实验要求】（实验课题一必做，课题二选做）
实验课题：
1 编写程序对实验六中的数组进行查找：
用C版教科书的同学：对数组StuInfo按照学号（ID）递增排序，然后用二分查找的方法进行学号查找，若找到则输出该学生的全部信息，若找不到相应记录也给出提示；接下来，对该数组按照学分绩（score）递减排序后，使用二分查找法以学分绩作关键字进行查找。 用C++版教科书的同学：对MyBirds分别以name和ID为关键字排序，然后进行二分查找。
2 对二叉搜索树查找
用C版教科书的同学：对StuInfo数组的数据以姓名（name）为关键字（key）建立一棵二叉搜索树（BST），然后以姓名为关键字进行搜索，并输出该记录相应的其它信息。要做到对关键字查找和删除，需要改变Find和Delete函数的原型，把对ElementType的查找和删除变成对KeyType的查找和删除，即把
Position Find( ElementType X, SearchTree T ); SearchTree Delete( ElementType X, SearchTree T ); 改为
Position Find( KeyType X, SearchTree T ); SearchTree Delete( KeyType X, SearchTree T ); 当然，对这些函数也要做相应的改动。
用C++教材的同学，和实验五（散列）的进阶类似，要改进二叉搜索树（BST）ADT定义，原来的BST ADT主要函数是：
19
相关推荐：
loading