{ temp=r[1];/*将堆顶元素r[1]与最后一个元素交换位置*/ r[1]=r[i];

r[i]=temp;

shift(r,1,i-1);/*将数组元素r[1]到r[i-1]重新调整成为一个新堆*/

}/*FOR*/ }/*HEAP_SORT*/

/*二路归并排序算法如下*/

void merge(rectype *a,rectype *r,int low,int mid,int high) { int i,j,k; i=low;j=mid+1;k=low;

while((i<=mid)&&(j<=high))/*将两个相邻有序子表进行合并*/ { if(a[i].key<=a[j].key)/*取两表中小者复制*/ r[k++]=a[i++]; else r[k++]=a[j++]; }

while(i<=mid) r[k++]=a[i++];/*复制第一个有序子表的剩余记录*/ while(j<=high) r[k++]=a[j++];/*复制第二个有序子表的剩余记录*/ }/*MERGE*/

void merge_pass(rectype *r,rectype *r1,int length) { int i=1,j,n=NUM;

while ((i+2*length-1)<=n)/*归并若干长度为2*length的两个相邻有序子表*/ { merge(r,r1,i,i+length-1,i+2*length-1); i=i+2*length;/*i指向下一对有序子表的起点*/ }

if(i+length-1

merge(r,r1,i,i+length-1,n);/*处理表长不足2*length的部分*/ else for(j=i;j<=n;j++)

r1[j]=r[j];/*将最后一个子表复制到r1中*/ }/*MERGEPASS*/

8

void merge_sort(rectype *r) { int length; rectype r1[MAX];

length=1;/*归并长度从1开始*/ while(length

{ merge_pass(r,r1,length);/*一趟归并，结果存放在r1中*/ length=2*length;/*归并后有序表的长度加倍*/

merge_pass(r1,r,length);/*再次归并，结果存放在r中*/ length=2*length;/*再次将归并后有序表的长度加倍*/ }

}/*MERGE_SORT*/

void creat_randnum(int *a )/*产生给定个数和范围的随机整数函数*/ { int i; int range=30000; srand(time(NULL)); for(i=1;i<=NUM;i++)

{a[i]=rand();} /*调用rand生成随机整数*/

printf(\排序前的原始随机整数为:\\n\\n\\t\for(i=1;i<=NUM;i++)

{ printf(\输出随机整数*/ if(i==0) printf(\}printf(\}/*CREAT_RANDNUM*/

void create() /*产生NUM个随机整数并保存到记录数组s中*/ { int b[MAX]; int range=30000,i;

creat_randnum(b); /*调用随机整数生成函数，结果存放在数组b中*/ for(i=1;i<=NUM;i++)

s[i].key=b[i];/*将随机整数存放到数组s中*/

9

s1=s;/*s1指向s,以便保存原始数据*/ }/*CREAT*/

void print_record(rectype *r)/*记录数组的输出函数*/ { int i;

printf(\排序后的有序随机整数:\\n\\n\\t\for(i=1;i<=NUM;i++) {printf(\ if(i==0) printf(\}getchar();getchar(); }/*PRINTRECORD*/

int menu_select()/*主菜单选择模块*/ { char c; int kk;

system(\清屏函数*/

printf(\内排序算法的比较----主控模块:\\n\\n\printf(\直接插入排序\\n\printf(\希尔排序\\n\printf(\冒泡排序\\n\printf(\快速排序\\n\printf(\直接选择排序\\n\printf(\堆排序\\n\printf(\二路归并排序\\n\printf(\退出\\n\

do {printf(\请按数位0—7键选择功能:\ c=getchar(); kk=c-48; }while ((kk<0)||(kk)>7); return(kk); }/*MENU_SELECT*/

main() /*算法比较--主程序模块*/

10

{

double time1, time2, time3, time4, time5, time6, time7;

clock_t start, finish;

int kk;

do {kk=menu_select(); /*进入主菜单选择模块*/ if(kk!=0) create(); /*建立记录数组*/ switch(kk)

{ case 1:{

case 2:{ start=clock();

case 3:{ start=clock();

case 4:{ start=clock();

case 5:{ start=clock();

start=clock(); insert_sort(s1); finish=clock();

time1 = (double)(finish - start)/ CLOCKS_PER_SEC ; printf( \直接插入排序耗时%f seconds\\n\

shell_sort(s1); finish=clock();

time2 = (double)(finish - start)/ CLOCKS_PER_SEC ; printf( \希尔排序耗时%f seconds\\n\

bubble_sort(s1); finish=clock();

time3 = (double)(finish - start)/ CLOCKS_PER_SEC ;

printf( \冒泡排序耗时%f seconds\\n\

quick_sort(s1,1,NUM); finish=clock();

time4 = (double)(finish - start)/ CLOCKS_PER_SEC ;

printf( \快速排序耗时%f seconds\\n\

select_sort(s1); finish=clock();

11