综合排序数据结构课程设计

题目：综合排序-数据结构课程设计院系：信息工程学院专业：运算机科学与技术班级：姓名：学号：指导老师:时间：目录TOC\o"1-2"\h\z\u一、 问题描述 8二、 内容简介 9大体要求： 9.算法思想： 9.模块划分： 11.数据结构： 11.源程序： 12插入排序核心代码 12voidInsertSort(inta[],intp) 12inti,j,temp; 12for(i=1;i<N;i++) 12{ 12temp=a[i]; 12for(j=i;j>0&&a[j-1]>temp;j--) 12a[j]=a[j-1]; 12a[j]=temp; 12} 12} 12选择排序核心代码 12voidSelectSort(inta[],intp) 12{ 12inti,j,k; 12for(i=0;i<N-1;i++) 12{ 12k=i; 12for(j=i+1;j<N;j++) 12if(a[j]<a[k]) 12k=j; 12if(k!=i) 12{ 12inttemp; 12temp=a[k]; 13a[k]=a[i]; 13a[i]=temp; 13} 13} 13} 13冒泡排序算法核心代码 13voidBubbleSort(inta[],intp) 13{ 13inti,j,temp; 13for(i=0;i<N-1;i++) 13{ 13for(j=N-1;j>i;j--)/*比较,找出本趟最小关键字的记录*/ 13if(a[j]<a[j-1]) 13{ 13temp=a[j];/*进行互换,将最小关键字记录前移*/ 13a[j]=a[j-1]; 13a[j-1]=temp; 13} 13} 13} 13创建堆核心代码 13voidcreatheap(inta[],inti,intn){ 13intj; 13intt; 13t=a[i]; 13j=2*(i+1)-1; 13while(j<=n) 13{ 13if((j<n)&&(a[j]<a[j+1])) 13j++; 13if(t<a[j]) 13{ 13a[i]=a[j]; 13i=j; 13j=2*(i+1)-1; 13} 13else 13j=n+1; 13} 13a[i]=t; 14} 14堆排序核心代码 14voidheapsort(inta[],intn,intp) 14{ 14inti; 14intt; 14for(i=n/2-1;i>=0;i--) 14creatheap(a,i,n-1); 14for(i=n-1;i>=1;i--) 14{ 14t=a[0]; 14a[0]=a[i]; 14a[i]=t; 14creatheap(a,0,i-1);} 14} 14快速排序核心代码 14voidquicksort(inta[],intn,intp) 14{ 14inti,j,low,high,temp,top=-1; 14structnode 14{ 14intlow,high; 14}st[N]; 14top++; 14st[top].low=0;st[top].high=n-1; 14while(top>-1) 14{low=st[top].low;high=st[top].high; 14top--; 14i=low;j=high; 14if(low<high) 14{temp=a[low]; 14while(i!=j) 14{while(i<j&&a[j]>temp)j--; 14if(i<j){a[i]=a[j];i++;} 14while(i<j&&a[i]<temp)i++; 14if(i<j){a[j]=a[i];j--;} 14} 14a[i]=temp; 14top++;st[top].low=low;st[top].high=i-1; 15top++;st[top].low=i+1;st[top].high=high; 15} 15} 15} 15时刻部份代码 15doubleTInsertSort(inta[],intp) 15{ 15inti; 15intb[N]; 15for(i=0;i<N;i++) 15b[i]=a[i]; 15LARGE_INTEGERm_liPerfFreq={0}; 15QueryPerformanceFrequency(&m_liPerfFreq); 15LARGE_INTEGERm_liPerfStart={0}; 15QueryPerformanceCounter(&m_liPerfStart); 15InsertSort(b,p); 15LARGE_INTEGERliPerfNow={0}; 15QueryPerformanceCounter(&liPerfNow); 15doubletime=-; 15time/=; 15if(p!=6) 15{Disp(b);getchar();} 15printf("\n用直接插入排序法用的时刻为%f秒；",time); 15FILE*fp; 15fp=fopen("直接插入排序.txt","w"); 15for(i=0;i<N;i++) 15fprintf(fp,"%d",b[i]); 15fclose(fp); 15return(time); 15} 15doubleTSelectSort(inta[],intp) 15{ 15inti; 15intb[N]; 15for(i=0;i<N;i++) 15b[i]=a[i]; 15LARGE_INTEGERm_liPerfFreq={0}; 15QueryPerformanceFrequency(&m_liPerfFreq); 15LARGE_INTEGERm_liPerfStart={0}; 15QueryPerformanceCounter(&m_liPerfStart); 15SelectSort(b,p); 15if(p!=6) 15{Disp(b);getchar();} 16LARGE_INTEGERliPerfNow={0}; 16QueryPerformanceCounter(&liPerfNow); 16doubletime=-; 16time/=; 16printf("\n用直接选择排序法用的时刻为%f秒；",time); 16FILE*fp; 16fp=fopen("直接选择排序.txt","w"); 16for(i=0;i<N;i++) 16fprintf(fp,"%d",b[i]); 16fclose(fp);return(time); 16} 16doubleTBubbleSort(inta[],intp) 16{ 16inti; 16intb[N]; 16for(i=0;i<N;i++) 16b[i]=a[i]; 16LARGE_INTEGERm_liPerfFreq={0}; 16QueryPerformanceFrequency(&m_liPerfFreq); 16LARGE_INTEGERm_liPerfStart={0}; 16QueryPerformanceCounter(&m_liPerfStart); 16BubbleSort(b,p); 16LARGE_INTEGERliPerfNow={0}; 16QueryPerformanceCounter(&liPerfNow); 16doubletime=-; 16time/=; 16if(p!=6) 16{Disp(b);getchar();} 16printf("\n用冒泡排序法用的时刻为%f秒；",time); 16FILE*fp; 16fp=fopen("冒泡排序.txt","w"); 16for(i=0;i<N;i++) 16fprintf(fp,"%d",b[i]); 16fclose(fp);return(time); 16} 16doubleTheapsort(inta[],intn,intp) 16{ 16inti; 16intb[N]; 16for(i=0;i<N;i++) 16b[i]=a[i]; 17LARGE_INTEGERm_liPerfFreq={0}; 17QueryPerformanceFrequency(&m_liPerfFreq); 17LARGE_INTEGERm_liPerfStart={0}; 17QueryPerformanceCounter(&m_liPerfStart); 17heapsort(b,N,p); 17LARGE_INTEGERliPerfNow={0}; 17QueryPerformanceCounter(&liPerfNow); 17doubletime=-; 17time/=; 17if(p!=6) 17{Disp(b);getchar();} 17printf("\n用堆排序法用的时刻为%f秒；",time); 17FILE*fp; 17fp=fopen("堆排序.txt","w"); 17for(i=0;i<N;i++) 17fprintf(fp,"%d",b[i]); 17fclose(fp);return(time); 17} 17doubleTquicksort(inta[],intn,intp) 17{ 17inti; 17intb[N]; 17for(i=0;i<N;i++) 17b[i]=a[i]; 17LARGE_INTEGERm_liPerfFreq={0}; 17QueryPerformanceFrequency(&m_liPerfFreq); 17LARGE_INTEGERm_liPerfStart={0}; 17QueryPerformanceCounter(&m_liPerfStart); 17quicksort(b,N,p); 17LARGE_INTEGERliPerfNow={0}; 17QueryPerformanceCounter(&liPerfNow); 17doubletime=-; 17time/=; 17if(p!=6) 17{Disp(b);getchar();} 17printf("\n用快速排序法用的时刻为%f秒；",time); 17FILE*fp;fp=fopen("快速排序.txt","w"); 17for(i=0;i<N;i++) 17fprintf(fp,"%d",b[i]); 17fclose(fp);return(time); 17} 18时刻数组的冒泡排序 18voidBubleSort(doublea[]) 18{ 18inti,j; 18doubletemp; 18for(i=1;i<6;i++) 18{ 18for(j=4;j>=i;j--) 18if(a[j+1]<a[j]) 18{ 18temp=a[j+1]; 18a[j+1]=a[j]; 18a[j]=temp; 18} 18} 18} 18主界面代码 18voidmenu() 18{ 18printf("★☆★☆\n"); 19printf("☆★****************************************************☆★\n"); 19printf("\n====>请在上述序号当选择一个并输入:"); 19} 19主函数代码 19voidmain() 19{ 19inti,p,a[N]; 19srand((int)time(NULL));/*随机种子*/ 19for(i=0;i<N;i++) 19a[i]=rand()%50000+1; 19while(1) 19{ 19system("cls"); 19menu(); 19scanf("%d",&p); 19if(p==0) 19{ 19printf("=====>谢谢利用!\n"); 19getchar(); 19break; 19} 19doubleTIMES[5],TIMES1[5];.");getchar();break; 19case2:TSelectSort(a,p);printf("\n请按任意键继续...");getchar();break; 19case3:TBubbleSort(a,p);printf("\n请按任意键继续...");getchar();break; 19case4:Tquicksort(a,N,p);printf("\n请按任意键继续...");getchar();break; 19case5:Theapsort(a,N,p);printf("\n请按任意键继续...");getchar();break; 19case6:system("cls"); 19TIMES1[1]=TIMES[1]=TInsertSort(a,p);TIMES1[2]=TIMES[2]=TSelectSort(a,p); 19TIMES1[3]=TIMES[3]=TBubbleSort(a,p);TIMES1[4]=TIMES[4]=Tquicksort(a,N,p);TIMES1[5]=TIMES[5]=Theapsort(a,N,p);getchar(); 19BubleSort(TIMES); 19printf("\n\n"); 19{ 19printf("排序这组数据两种较快的排序法别离是：\n"); 19if(TIMES[1]==TIMES1[1])printf("直接插入排序:%f秒!\n",TIMES[1]); 19if(TIMES[1]==TIMES1[2])printf("直接选择排序:%f秒!\n",TIMES[1]); 19if(TIMES[1]==TIMES1[3])printf("冒泡排序:%f秒!\n",TIMES[1]); 19if(TIMES[1]==TIMES1[4])printf("快速排序:%f秒!\n",TIMES[1]); 19if(TIMES[1]==TIMES1[5])printf("堆排序:%f秒!\n",TIMES[1]); 20if(TIMES[1]!=TIMES[2]) 20{ 20if(TIMES[2]==TIMES1[1])printf("直接插入排序:%f秒!\n",TIMES[2]); 20if(TIMES[2]==TIMES1[2])printf("直接选择排序%f秒!\n",TIMES[2]); 20if(TIMES[2]==TIMES1[3])printf("冒泡排序%f秒!\n",TIMES[2]); 20if(TIMES[2]==TIMES1[4])printf("快速排序%f秒!\n",TIMES[2]); 20if(TIMES[2]==TIMES1[5])printf("堆排序%f秒!\n",TIMES[2]); 20} 20}printf("\n请按任意键继续...");srand((int)time(NULL)); 20for(i=0;i<N;i++){a[i]=rand()%30000+1;}getchar();break; 20case7:Disp(a);FILE*fp;fp=fopen("随机数.txt","w"); 20for(i=0;i<N;i++)fprintf(fp,"%d",a[i]);fclose(fp);getchar();printf("\n请按任意键继续...");getchar();break; 20default:Wrong();printf("\n请按任意键继续...");getchar();break; 20} 20} 20} 20.测试情形： 20三、 小结 23问题描述利用随机函数产生N个随机整数（20000以上），对这些数进行多种方式进行排序。

要求：

1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。

2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

3)如果采用4种或4种以上的方法者，可适当加分。内容简介大体要求：设计一个的菜单将在实现的功能显示出来，并有选择提示别离实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单排序、堆排序算法；通过量种测试数据，对各类排序算法的时刻复杂度和空间复杂度进行比较.算法思想：1.处置流程图开始开始直接插入排序时间效率比较直接选择排序显示菜单冒泡排序快速排序堆排序显示随机数显示排序后的的数据和时间效率输入序号结束退出随机数显示各个排序法对同一组数据排序所用的时间和其中两种较快的方法12345670voidBubleSort(doublea[])voidBubleSort(doublea[])时间数组的冒泡排序voidInsertSort(inta[],intp)voidSelectSort(inta[],intp)voidDisp(inta[])voidcreatheap(inta[],inti,intn)voidheapsort(inta[],intn,intp)doubleTInsertSort(inta[],intp)voidquicksort(inta[],intn,intp)voidBubbleSort(inta[],intp)doubleTSelectSort(inta[],intp)doubleTquicksort(inta[],intleft,intright,intp)doubleTBubbleSort(inta[],intp)doubleTheapsort(inta[],intn,intp)3.设计一个高精度时刻函数，别离测试各类排序的时刻消耗；4.在主函数中，用开关语句swtich(){case值1;break;…case值n;break;Default语句序列:n+1;}挪用各类排序算法，各类排序的时刻消耗函数，从而在屏幕上输出供选择的菜单，各类排序时刻和空间复杂度的比较。.模块划分：1.输入初始数据函数：intMakeList(RECNODE*r)2.输出未排序前的数据函数：voidUndealoutList(RECNODE*r,intn)3.处置后的序列函数：voidDealoutList(RECNODE*r,intn)4.这种排序的算法：voidInsertSort(RECNODE*r,intn)序时刻测试函数：doubleTInsertSort(intlen,RECNODE*a,intp).数据结构：1.预概念常量和自概念类型：#defineMAXSIZE100typedefstruct{intkey;}RECNODE;2.大体函数的算法用以下形式表示：函数类型函数名（函数参数表）义intb,t,i,j;输入初始数据函数中概念intk,j，k为输入数据个数，j为输入的数据。5.快速排序中概念staticintw=0,int*low，*high。6.在直接选择排序中概念intz，临时贮存i的值。7.在希尔排序中概念intdk，记录前后位置的增量。8.在排序时刻消耗测试的函数和主函数中概念了intp，为菜单的序号。9.在主函数中概念intlen，为测试数据的总长度。.源程序：插入排序核心代码voidInsertSort(inta[],intp)inti,j,temp;for(i=1;i<N;i++){temp=a[i];for(j=i;j>0&&a[j-1]>temp;j--)a[j]=a[j-1];a[j]=temp;}}选择排序核心代码voidSelectSort(inta[],intp){inti,j,k;for(i=0;i<N-1;i++){k=i;for(j=i+1;j<N;j++)if(a[j]<a[k])k=j;if(k!=i){inttemp;temp=a[k];a[k]=a[i];a[i]=temp;}}}冒泡排序算法核心代码voidBubbleSort(inta[],intp){inti,j,temp;for(i=0;i<N-1;i++){for(j=N-1;j>i;j--)/*比较,找出本趟最小关键字的记录*/if(a[j]<a[j-1]){temp=a[j];/*进行互换,将最小关键字记录前移*/a[j]=a[j-1];a[j-1]=temp;}}}创建堆核心代码voidcreatheap(inta[],inti,intn){ intj;intt; t=a[i]; j=2*(i+1)-1; while(j<=n) { if((j<n)&&(a[j]<a[j+1])) j++; if(t<a[j]) { a[i]=a[j]; i=j; j=2*(i+1)-1; } else j=n+1; } a[i]=t;}堆排序核心代码voidheapsort(inta[],intn,intp){ inti; intt; for(i=n/2-1;i>=0;i--) creatheap(a,i,n-1); for(i=n-1;i>=1;i--) { t=a[0]; a[0]=a[i]; a[i]=t; creatheap(a,0,i-1);} }快速排序核心代码voidquicksort(inta[],intn,intp){