綜合排序數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

題目：綜合排序-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)院系：信息工程學(xué)院專業(yè)：運(yùn)算機(jī)科學(xué)與技術(shù)班級(jí)：姓名：學(xué)號(hào)：指導(dǎo)老師:時(shí)間：目錄TOC\o"1-2"\h\z\u一、 問(wèn)題描述 8二、 內(nèi)容簡(jiǎn)介 9大體要求： 9.算法思想： 9.模塊劃分： 11.數(shù)據(jù)結(jié)構(gòu)： 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--)/*比較,找出本趟最小關(guān)鍵字的記錄*/ 13if(a[j]<a[j-1]) 13{ 13temp=a[j];/*進(jìn)行互換,將最小關(guān)鍵字記錄前移*/ 13a[j]=a[j-1]; 13a[j-1]=temp; 13} 13} 13} 13創(chuàng)建堆核心代碼 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時(shí)刻部份代碼 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用直接插入排序法用的時(shí)刻為%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用直接選擇排序法用的時(shí)刻為%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用冒泡排序法用的時(shí)刻為%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用堆排序法用的時(shí)刻為%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用快速排序法用的時(shí)刻為%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時(shí)刻數(shù)組的冒泡排序 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====>請(qǐng)?jiān)谏鲜鲂蛱?hào)當(dāng)選擇一個(gè)并輸入:"); 19} 19主函數(shù)代碼 19voidmain() 19{ 19inti,p,a[N]; 19srand((int)time(NULL));/*隨機(jī)種子*/ 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請(qǐng)按任意鍵繼續(xù)...");getchar();break; 19case3:TBubbleSort(a,p);printf("\n請(qǐng)按任意鍵繼續(xù)...");getchar();break; 19case4:Tquicksort(a,N,p);printf("\n請(qǐng)按任意鍵繼續(xù)...");getchar();break; 19case5:Theapsort(a,N,p);printf("\n請(qǐng)按任意鍵繼續(xù)...");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("排序這組數(shù)據(jù)兩種較快的排序法別離是：\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請(qǐng)按任意鍵繼續(xù)...");srand((int)time(NULL)); 20for(i=0;i<N;i++){a[i]=rand()%30000+1;}getchar();break; 20case7:Disp(a);FILE*fp;fp=fopen("隨機(jī)數(shù).txt","w"); 20for(i=0;i<N;i++)fprintf(fp,"%d",a[i]);fclose(fp);getchar();printf("\n請(qǐng)按任意鍵繼續(xù)...");getchar();break; 20default:Wrong();printf("\n請(qǐng)按任意鍵繼續(xù)...");getchar();break; 20} 20} 20} 20.測(cè)試情形： 20三、 小結(jié) 23問(wèn)題描述利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行多種方式進(jìn)行排序。

要求：

1)至少采用三種方法實(shí)現(xiàn)上述問(wèn)題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。

2)統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。

3)如果采用4種或4種以上的方法者，可適當(dāng)加分。內(nèi)容簡(jiǎn)介大體要求：設(shè)計(jì)一個(gè)的菜單將在實(shí)現(xiàn)的功能顯示出來(lái)，并有選擇提示別離實(shí)現(xiàn)直接插入排序、折半插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單排序、堆排序算法；通過(guò)量種測(cè)試數(shù)據(jù)，對(duì)各類排序算法的時(shí)刻復(fù)雜度和空間復(fù)雜度進(jìn)行比較.算法思想：1.處置流程圖開始開始直接插入排序時(shí)間效率比較直接選擇排序顯示菜單冒泡排序快速排序堆排序顯示隨機(jī)數(shù)顯示排序后的的數(shù)據(jù)和時(shí)間效率輸入序號(hào)結(jié)束退出隨機(jī)數(shù)顯示各個(gè)排序法對(duì)同一組數(shù)據(jù)排序所用的時(shí)間和其中兩種較快的方法12345670voidBubleSort(doublea[])voidBubleSort(doublea[])時(shí)間數(shù)組的冒泡排序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.設(shè)計(jì)一個(gè)高精度時(shí)刻函數(shù)，別離測(cè)試各類排序的時(shí)刻消耗；4.在主函數(shù)中，用開關(guān)語(yǔ)句swtich(){case值1;break;…case值n;break;Default語(yǔ)句序列:n+1;}挪用各類排序算法，各類排序的時(shí)刻消耗函數(shù)，從而在屏幕上輸出供選擇的菜單，各類排序時(shí)刻和空間復(fù)雜度的比較。.模塊劃分：1.輸入初始數(shù)據(jù)函數(shù)：intMakeList(RECNODE*r)2.輸出未排序前的數(shù)據(jù)函數(shù)：voidUndealoutList(RECNODE*r,intn)3.處置后的序列函數(shù)：voidDealoutList(RECNODE*r,intn)4.這種排序的算法：voidInsertSort(RECNODE*r,intn)序時(shí)刻測(cè)試函數(shù)：doubleTInsertSort(intlen,RECNODE*a,intp).數(shù)據(jù)結(jié)構(gòu)：1.預(yù)概念常量和自概念類型：#defineMAXSIZE100typedefstruct{intkey;}RECNODE;2.大體函數(shù)的算法用以下形式表示：函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）義intb,t,i,j;輸入初始數(shù)據(jù)函數(shù)中概念intk,j，k為輸入數(shù)據(jù)個(gè)數(shù)，j為輸入的數(shù)據(jù)。5.快速排序中概念staticintw=0,int*low，*high。6.在直接選擇排序中概念intz，臨時(shí)貯存i的值。7.在希爾排序中概念intdk，記錄前后位置的增量。8.在排序時(shí)刻消耗測(cè)試的函數(shù)和主函數(shù)中概念了intp，為菜單的序號(hào)。9.在主函數(shù)中概念intlen，為測(cè)試數(shù)據(jù)的總長(zhǎng)度。.源程序：插入排序核心代碼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--)/*比較,找出本趟最小關(guān)鍵字的記錄*/if(a[j]<a[j-1]){temp=a[j];/*進(jìn)行互換,將最小關(guān)鍵字記錄前移*/a[j]=a[j-1];a[j-1]=temp;}}}創(chuàng)建堆核心代碼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){