北邮数据结构实验报告-排序 下载本文

北京邮电大学 数据结构试验报告

实验名称: 实验四 排序 学生姓名: 班 级: 班内序号: 学 号:

日 期: 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=0;j--) {

(*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]=0)&&(x=0) (*compare)++;