typedef int datatype;
typedef struct /*定义记录为结构体类型*/ { int key; /*记录的关键词域*/ datatype other; /*记录的其它域*/ } rectype;
rectype *s1,s[MAX];/*s[MAX]存放原始随机数，*s1取出原始数据后进行排序*/
/*直接插入排序算法如下*/
void insert_sort(rectype *r) /*对数组r按递增顺序进行插入排序算法*/ { int i,j,n=NUM; /*NUM为实际输入的记录数，是一个常量*/ for(i=1;i<=n;i++) /* i { r[0]=r[i]; /*r[0]为监视哨*/ j=i-1; /*依次插入记录r[1],??，r[NUM]*/ while(r[0].key {r[j+1]=r[j--];} /*将记录关键词大于r[i].key的记录后移*/ r[j+1]=r[0]; /*将记录r[i]插入到有序表的合适的位置上*/ } }/*INSERTSORT*/ /*希尔排序算法如下*/ void shell_sort(rectype *r) /*取增量为d(i+1)=[d(i)/2]的希尔排序的算法*/ { int i,n,jump,change,temp,m; /*change为交换标志，jump为增量步长*/ jump=NUM; n=NUM; /*NUM为顺序表的实际长度*/ while(jump>0) { jump=jump/2; /*取步长d(i+1)=[d(i)/2]*/ do { change=0; /*设置交换标志，change=0表示未交换*/ for(i=1;i<=n-jump;i++) { m=i+jump; /*取本趟的增量*/ if(r[i].key>r[m].key) /*记录交换*/ 4 { temp=r[m].key; r[m].key=r[i].key; r[i].key=temp; change=1; /*change=1表示有交换*/ }/*if*/ }/*for*/ /*本趟排序完成*/ }while(change==1); /*当change=0时终止本趟排序*/ /*当增量jump=1且change=0时终止算法*/ }/*while*/ }/*SHELLSORT*/ /*冒泡排序算法如下*/ void bubble_sort(rectype *r) /*从下往上扫描的冒泡排序*/ { int i,j,noswap=0,n=NUM; /*noswap为交换标志,NUM为实际输入记录数*/ rectype temp; for(i=1;i /*进行n-1趟冒泡排序*/ /*设置交换标志，noswap=1表示没有记录交换*/ /*从下往上扫描*/ /*交换记录*/ for(j=n;j>=i;j--) if(r[j].key noswap=0; /*当交换记录时，将交换标志置0即noswap=0 */ }/*if*/ if(noswap) break; /*若本趟排序中未发生记录交换，则终止排序*/ }/*for*/ /*终止排序算法*/ }/*BUBBLESORT*/ /*快速排序算法如下*/ int partition(rectype *r,int s,int t) /*快速排序算法中的一趟划分函数*/ { int i,j;rectype temp; 5 i=s;j=t;temp=r[i]; /*初始化，temp为基准记录*/ do {while((r[j].key>=temp.key)&&(i /*从右往左扫描，查找第一个关键词小于temp的记录*/ if(i /*从左往右扫描，查找第一个关键词大于temp的记录*/ if(i }while(i!=j);/*i=j,z则一次划分结束，基准记录达到其最终位置*/ r[i]=temp; /*最后将基准记录temp定位*/ return(i); }/*PARTITION*/ void quick_sort(rectype *r,int hs,int ht)/*对r[hs]到r[ht]进行快速排序*/ { int i; if(hs { i=partition(r,hs,ht); /*对r[hs]到r[ht]进行一次划分*/ quick_sort(r,hs,i-1); /*递归处理左区间*/ quick_sort(r,i+1,ht); /*递归处理右区间*/ } }/*QUICK_SORT*/ /*直接选择排序算法如下*/ void select_sort(rectype *r) { rectype temp; int i,j,k,n=NUM; /*NUM为实际输入记录数*/ for(i=1;i<=n;i++)/*做n-1趟选择排序*/ { k=i; for(j=i+1;j<=n;j++)/*在当前无序区中选择关键词最小的记录r[k]*/ if(r[j].key if(k!=i) {temp=r[i];/*交换记录r[i]和r[k]*/ r[i]=r[k]; 6 r[k]=temp; } }/*for*/ }/*SELECT_SORT*/ /*堆排序算法如下*/ void shift(rectype *r,int i,int m)/*堆的筛选算法,在数组中r[i]到r[m]中，调整堆r[i]*/ { int j; rectype temp; temp=r[i]; j=2*i; while (j<=m)/*j<=m,r[2*i]是r[i]的左孩子*/ { if((j j++; /*j指向r[i]的左右孩子中关键词较大者*/ if(temp.key { r[i]=r[j]; /*将r[j]调到父亲结点的位置上*/ i=j; /*调整i和j的值，以便继续“筛”结点*/ j=2*i; } else } r[i]=temp; }/*SHIFT*/ void heap_sort(rectype *r)/*对数组r[1]到r[NUM]进行堆排序*/ { rectype temp; int i,n; /*NUM为数组的实际长度*/ /*将被筛选的结点放入正确的位置*/ j=m+2; /*调整完毕，退出循环*/ n=NUM; for(i=n/2;i>0;i--)/*建立初始堆*/ shift(r,i,n); for(i=n;i>1;i--)/*进行n-1趟筛选，交换，调整，完成堆排序*/ 7