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