七种排序算法的比较及每种排序的上机统计时间

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