{ 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