北邮数据结构实验报告-排序

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

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

日 期： 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)++;

r[j+d]=x; } else (*compare)++; } } }

3.冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止 void Bubblesort(int r[],int n,int* compare,int* move)//交换（冒泡）排序 { *compare=0; *move=0; int x;

for(int j=0;j

for(int i=n-1;i>j;i--) {

if(r[i]

4.快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成

int Partion(int r[],int first,int end,int* compare,int* move)//快速排序中的轴定位 {

int i=first; int j=end;

int zhou=r[i];//默认第一个元素为轴 while(i=zhou)) //查看右侧元素与轴的大小关系 { (*compare)++; j--; } if(i

(*compare)++; (*move)++;

r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置 } while((i

r[j]=r[i];//发现轴左侧的某数比轴值小，将其后置 } }

r[i]=zhou;//最后确定轴的位置 return i; }

void Qsort(int r[],int i,int j,int* compare,int* move)//快速排序 { if(i

int centre=Partion(r,i,j,compare,move); Qsort(r,i,centre-1,compare,move); Qsort(r,centre+1,j,compare,move); } }

5.选择排序：从待排序的记录序列中选择关键码最小的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止 void Selectsort(int r[],int n,int* compare,int* move)//选择排序 { *compare=0; *move=0;

for(int i=0;i

int min=i;

for(int j=i+1;j

(*compare)++;

if(r[j]