数据结构实验六 内部排序

实验六

内部排序算法比较

1、实验目的

掌握多种排序方法的基本思想，如直接插入、起泡、简单选择、快速、堆、希尔排序等排序方法，并能够用高级语言实现。

2、问题描述

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受

3、基本要求

（1） 对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简

单选择排序、快速排序、希尔排序、堆排序。

（2） 待排序的表长不小于100；其中的数据要用伪随机数产生程序产生；至少

要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。

（3） 最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。

4、测试数据

由随机数产生器生成。

5、实现提示

主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动

次数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。

6、源程序

#include #include #include

#define MAXNUM 10000

long cn[MAXNUM],mn[MAXNUM]; typedef struct { int key; }datatype;

void D_InsertSort(datatype R[],long n)//直接排序 { long i ,j; for(i=2;i<=n;i++) { cn[0]++; if(R[i].key

R[0]=R[i];mn[0]++; for(j=i-1;R[0].key

void Select_Sort(datatype R[],long n)//简单选择排序 { long i,j,k; for(i=1;i

void Bubble_Sort(datatype R[],long n)//冒泡排序 { long i,j; for(i=1;i

} } }

void HeapAdjust(datatype R[], long s, long t)//堆调整 { datatype rc; long i,j; rc=R[s]; i=s; for(j=2*i;j<=t;j=2*j) { cn[3]++; if(jR[j].key) break; R[i]=R[j]; mn[3]++; i=j; } R[i]=rc; }

void HeapSort(datatype R[], long n)//推排序 { long i; for(i=n/2;i>0;i--) HeapAdjust(R,i,n); for(i=n;i>1;i--) { R[0]=R[1]; R[1]=R[i]; R[i]=R[0]; mn[3]+=3; HeapAdjust(R,1,i-1); } }

void Merge(datatype R[],datatype R1[], long s, long m, long t) { long i ,j ,k; i=s;j=m+1;k=s; while(i<=m&&j<=t) { cn[4]++; if(R[i].key

{ R1[k++]=R[i++]; mn[4]++; } else { R1[k++]=R[j++]; mn[4]++; } } while(i<=m) { R1[k++]=R[i++]; mn[4]++; } while(j<=t) { R1[k++]=R[j++]; mn[4]++; } }

void MSort(datatype R[],datatype R1[], long s,long t) {

long m; if(s==t) { R1[s]=R[s]; mn[4]++; } else{ m=(s+t)/2; MSort(R,R1,s,m); MSort(R,R1,m+1,t); Merge(R1,R,s,m,t); } }

void MergeSort(datatype R[],datatype R1[],long n)//归并排序 { MSort(R,R1,1,n); }

long Partition(datatype R[], long low, long high) { R[0]=R[low]; mn[5]++;