北京邮电大学电信工程学院 第1 页 2 0 0 8 级数据结构实验报告 实验名称： 实验四 排序 学生姓名： 班 级： 班内序号： 学 号： 日 期： 2 0 0 9 年1 2 月6 日 1 ．实验要求 a. 实验目的 通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 b. 实验内容 使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1 、插入排序 2 、希尔排序 3 、冒泡排序 4 、快速排序 5 、简单选择排序 6 、堆排序（选作） 7 、归并排序（选作） 8 、基数排序（选作） 9 、其他 北京邮电大学电信工程学院 第2页 2. 程序分析 2.1 存储结构 存储结构: 顺序存储结构 示意图如下: 2.2 关键算法分析 核心算法思想： 1. 利用教材讲述的基本算法思想，实现七种排序算法，统计其运行相关数据。 2. 将七种排序函数入口地址作为函数指针数组，实现快速调用和统计。使得程序代码可读性增、结构更加优化。 关键算法思想描述和实现： 关键算法1： 实现七种算法的基本排序功能。 1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。 2、希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，北京邮电大学电信工程学院 第3页 待整个序列基本有序时，再对全体记录进行一次直接插入排序。 3、冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。 4、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。 5、选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。 6、堆排序：通过建立大根堆或者小根堆，取出根节点，反复调整堆使之保持大根堆或者小根堆，直至最后序列有序。 7、归并排序：将若干个有序序列两两归并，直至所有待排序的记录都在一个有序序列为止。 C++实现： 参看源代码的七个排序函数。 关键算法 2 ： 获取当前系统时间，精确到微秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。此处调用函数 Qu ery...
