北京邮电大学 数据结构试验报告
实验名称： 实验四 排序 学生姓名： 班 级： 班内序号： 学 号：
日 期： 2014年1月4日
1 实验目的
学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。
2 实验内容
2.1 题目1
使用简单数组实现下面各种排序算法，并进行比较。 排序算法：
1、插入排序
2、希尔排序
3、冒泡排序 4、快速排序 5、简单选择排序
6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他
要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性。
3 程序分析
3.1 存储结构
顺序存储结构——数组
3.2 关键算法分析
1.插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕
void Insertsort(int r[],int n,int* compare,int* move)//插入排序 {
*compare=0; *move=0; int i; int j;
for(i=1;i
(*compare)++; (*move)++; r[j+1]=r[j]; } if(j>=0) (*compare)++; r[j+1]=x; } }
2.希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序 void ShellInsert(int r[],int n,int* compare,int* move)//希尔排序 {
*compare=0; *move=0; int j;
10 9 12 12 20 20 31
for(int d=n/2;d>=1;d=d/2)//间距越来越小 {
for(int i=d;i<=n-1;i++)//从a[d]往后逐个元素确定是否需要前移 { if(r[i]