实验三内部排序算法效率的比较

实验三 内部排序算法效率的比较

一、实验目的：

了解不同排序算法的时间效率

了解先进的排序算法与简单的排序算法的差别 掌握希尔排序算法 掌握快速排序算法 掌握堆排序算法

能够根据实际问题选择合适的算法

二、实验内容与要求：

 希尔排序和直接插入排序  快速排序和冒泡排序  堆排序和直接选择排序 要求：

编写实验程序，对随机生成的n个整数分别采用两种排序方法进行排序，并分别统计每种排序算法中的关键字比较次数。

通过进行多组实验(m组)，统计每种算法的平均比较次数。 程序要具有灵活性。m、n值应在运行时确定 重点观察当n增大时两种算法的差别。

206

少年易学老难成，一寸光阴不可轻 -

三、提示：

实验分两步进行： 步骤1．

首先编写排序算法，令n=10，显示排序结果，目的是查看排序算法是否正确。 步骤2.

修改教材中的排序算法，增加对“关键字比较次数”和“记录移动次数”统计的语句。建议使用全局变量作为计数器。比较100个、1000个数据的排序效率

四、参考程序

1.希尔排序和直接插入排序的比较实验程序

# define maxnum 5000 /*排序记录的个数为5000*/ # include # include

typedef int KeyType; /*定义关键字为整型*/ typedef struct { KeyType key;

int data; /*其他信息略*/ } RecordType;

long compare=0; /*shellsort关键字比较次数*/

207

少年易学老难成，一寸光阴不可轻 -

long compare1=0; /*直接插入的关键字比较次数*/ long move=0; /*shellsort记录移动次数*/ long move1=0; /*直接插入记录移动次数*/

void ShellInsert(RecordType r[],int n,int d) { int i,j;

for (i=d+1; i<=n; i++) {

if ( r[i].key/*暂存r[i]*/

for (j=i-d; j>0 && r[0].keyr[j+d]=r[j];

/* 记录后移，找插入位置 */

compare++; /*记录比较次数*/ }

r[j+d]=r[0]; } } }

/*希尔排序过程：通过多次调用一趟插入排序实现 */ void ShellSort(RecordType r[],int n,int d[],int m)

/* 插入记录 */

208

少年易学老难成，一寸光阴不可轻 -

/* 对数组r中记录进行排序, n为数组r的长度，d为增量序列，m为d的长度 */ { int k;

for ( k=0; k/*直接插入排序*/

void Insertsort(RecordType r[],int n) { int i,j;

for (i=2; i<=n; i++) {

r[0]=r[i];

for (j=i-1; r[0].keyr[j+1]=r[j];

compare1++; /*记录比较次数* }

r[j+1]=r[0]; } } main() {

RecordType r[maxnum+1],bf[maxnum+1];

209

少年易学老难成，一寸光阴不可轻 -

double shell_com=0, Ins_com=0;

int i,times,m,d[10],n; /*d为希尔排序的增量序列,m为其长度*/ clrscr();

printf(\"\\n input times :\"); /*实验组数，最后取平均值*/ scanf(\"%d\

printf(\"\\n input number(<1000) :\"); /*读入待排序的数据个数*/ scanf(\"%d\

printf(\"\\n input the len of INC_serial(<10) :\");

scanf(\"%d\读入增量序列长度*/ printf(\"\\n input the searil :\");

for (i=0; i0) {

/*生成待排序的n个数据,注意保存初始数据*/ for (i=1; i<=n; i++)

{ r[i].key=bf[i].key=rand()%1000;

/* printf(\"%d \

}

/*对随机生成的数据进行希尔排序，显示所进行的关键字比较次数*/ compare=0; ShellSort(r,n,d,m);

210

少年易学老难成，一寸光阴不可轻 -

printf(\"\\nshell: compare=%.0f\ shell_com+=compare;

/*对随机生成的数据进行直接插入排序，所需关键字比较次数*/ compare1=0; Insertsort(bf,n);

printf(\"\Insert: compare=%.0f\ Ins_com+=compare1; times--; }

/*显示对times组数据排序的平均比较次数*/

printf(\"\\nShellsort comparing number=%.0f”,shell_com/m); printf(\"\\nInsertsort comparing number=%.0f\

}

211