当前位置：搜档网 › 七种排序算法的比较及每种排序的上机统计时间

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

《数据结构》课程设计报告

课题: 排序算法的比较

学院:信息学院

班级: 2011级电子信息工程1班

小组成员:韦志东（组长）

夏琪

完成时间: 2014-01-08

教师:周铁

、设计任务书 (2)

1、课程分析

、选题要求

利用随机函数产生30000个随机整数，利用直接插入排序、希尔排序，冒泡排序、直接选择排序、快速排序、堆排序、归并排序的排序方法进行排序，并统计每一种排序上机所花费的时间。

、选题的意义及背景

排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键词有序的序列。

此实验通过对各种内部排序算法进行比较，能使我们更好的掌握各种排序的基本思想，掌握各种排序方法的算法实现，掌握各种排序方法的优劣分析及花费的时间的计算，掌握各种排序方法所适应的不同场合。通过该题目的设计，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。

、设计任务书

（1）定义结构体，头文件，定义数组范围，大小。

（2）依次描写七种排序的算法。

（3）描写产生随机函数的算法。

（4）描写菜单函数。

（5）描写主函数，调用七种排序的算法。

2、设计分析

原始资料

用户输入记录的个数30000个，数据由随机函数生成。

输出数据

产生的随机数分别用冒泡排序、直插排序、希尔排序、选择排序、快速排序、堆排序、归并排序这些排序方法进行排序，并统计每一种排序上机所花费的时间。程序流程图

#include ""

#include<>

#define MAX 60000 /*记录数组的个数*/

#define NUM 30000 /*实际输入数组的个数*/

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

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) /*记录交换*/

{ 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时终止本趟排序*/

}/*while*/ /*当增量jump=1且change=0时终止算法*/

}/*SHELLSORT*/

/*冒泡排序算法如下*/

void bubble_sort(rectype *r) /*从下往上扫描的冒泡排序*/

{ int i,j,noswap=0,n=NUM; /*noswap为交换标志,NUM为实际输入记录数*/ rectype temp;

for(i=1;i

{ noswap=1; /*设置交换标志，noswap=1表示没有记录交换*/ for(j=n;j>=i;j--) /*从下往上扫描*/

if(r[j].key

{ =r[j-1].key;

r[j-1].key=r[j].key;

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;

i=s;j=t;temp=r[i]; /*初始化，temp为基准记录*/

do {while((r[j].key>=&&(i

j--; /*从右往左扫描，查找第一个关键词小于temp的记录*/

if(i

while((r[i].key<=&&(i

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];

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]的左右孩子中关键词较大者*/

{ r[i]=r[j]; /*将r[j]调到父亲结点的位置上*/

i=j; /*调整i和j的值，以便继续“筛”结点*/

j=2*i;

}

else

j=m+2; /*调整完毕，退出循环*/

}

r[i]=temp; /*将被筛选的结点放入正确的位置*/

}/*SHIFT*/

void heap_sort(rectype *r)/*对数组r[1]到r[NUM]进行堆排序*/ { rectype temp;

int i,n;

n=NUM; /*NUM为数组的实际长度*/

for(i=n/2;i>0;i--)/*建立初始堆*/

shift(r,i,n);

for(i=n;i>1;i--)/*进行n-1趟筛选，交换，调整，完成堆排序*/

{ 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的部分*/

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

}/*MERGEPASS*/

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\t\t排序前的原始随机整数为:\n\n\t");

for(i=1;i<=NUM;i++)

{ printf("%6d",a[i]); /*输出随机整数*/

if(i%10==0) printf("\n\t");

}printf("\n");

}/*CREAT_RANDNUM*/

void create() /*产生NUM个随机整数并保存到记录数组s中*/

{ int b[MAX];

int range=30000,i;

creat_randnum(b); /*调用随机整数生成函数，结果存放在数组b中*/

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

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

}/*CREAT*/

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

printf("\n\t\t\t排序后的有序随机整数:\n\n\t");

for(i=1;i<=NUM;i++)

{printf("%6d",r[i].key);

if(i%10==0) printf("\n\n\t");

}getchar();getchar();

}/*PRINTRECORD*/

int menu_select()/*主菜单选择模块*/

{ char c; int kk;

system("cls");/*清屏函数*/

printf("内排序算法的比较----主控模块:\n\n");

printf("\t\t\t1. 直接插入排序\n");

printf("\t\t\t2. 希尔排序\n");

printf("\t\t\t3. 冒泡排序\n");

printf("\t\t\t4. 快速排序\n");

printf("\t\t\t5. 直接选择排序\n");

printf("\t\t\t6. 堆排序\n");

printf("\t\t\t7. 二路归并排序\n");

printf("\t\t\t0. 退出\n");

do {printf("\n\t\t\t请按数位0—7键选择功能:");

c=getchar(); kk=c-48;

}while ((kk<0)||(kk)>7);

return(kk);

}/*MENU_SELECT*/

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

{

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:{ start=clock();

insert_sort(s1);

finish=clock();

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

printf( "直接插入排序耗时%f seconds\n", time1); break;} case 2:{ start=clock();

shell_sort(s1);

finish=clock();

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

printf( "希尔排序耗时%f seconds\n", time2); break;}

case 3:{ start=clock();

bubble_sort(s1);

finish=clock();

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

printf( "冒泡排序耗时%f seconds\n", time3); break;} case 4:{ start=clock();

quick_sort(s1,1,NUM);

finish=clock();

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

printf( "快速排序耗时%f seconds\n", time4); break;} case 5:{ start=clock();

select_sort(s1);

finish=clock();

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

printf( "直接选择排序耗时%f seconds\n", time5); break;} case 6:{ start=clock();

heap_sort(s1);

finish=clock();

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

printf( "堆排序耗时%f seconds\n", time6); break;} case 7:{ start=clock();

merge_sort(s1);

finish=clock();

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

printf( "二路归并排序耗时%f seconds\n", time7); break;} case 0:{ exit(0);}

}print_record(s1);

}while (kk!=0);

}/*MAIN*/

4．测试结果

（1）选择直接插入排序：

排序前本有30000个随机数显示，但数据太多，只截一部分图来表示。