{ 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