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