文檔來源為：從網(wǎng)絡(luò)收集整理文檔來源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持課程設(shè)計課程設(shè)計名稱：專業(yè)班級：學生姓名：學號：指導教師：課程設(shè)計時間：課程設(shè)計名稱：專業(yè)班級：學生姓名：學號：指導教師：課程設(shè)計時間：排序綜合000000000000000000000000000000000000000000000000000000計算機科學與技術(shù)專業(yè)課程設(shè)計任務(wù)書學生姓名專業(yè)班級學號題目排序綜合課題性質(zhì)A.工程設(shè)計課題來源D.自擬課題指導教師同組姓名無主要內(nèi)容綜合應(yīng)用所學知識，設(shè)計完成一個排序綜合系統(tǒng)。本系統(tǒng)擬實現(xiàn)以下功能：.直接插入排序.希爾排序.快速排序.堆排序.結(jié)果保存.計算排序時間系統(tǒng)要求采用VC6.0工具進行開發(fā)實現(xiàn)。任務(wù)要求綜合運用和融化所學理論知識， 提高分析和解決實際問題的能力，使用c語言設(shè)甘一個排序綜合系統(tǒng)。完成課程設(shè)計報告，報告中對關(guān)鍵部分給出圖表說明。 要求格式規(guī)范，工作量飽滿。

奔f文獻[1]數(shù)據(jù)Z^勾.嚴蔚敏，吳偉民編著.清華大學出版社.2007年03月[2]數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用：詩林等譯.機械工業(yè)出版社C+鐳言描術(shù)..2005年03月（美）薩尼（Sahni,S.）著，汪審查意見指導教師簽字：教研室主任簽字：2010年6月24日說明：本表由指導教師填寫，由教研室主任審核后下達給選題學生，裝訂在設(shè)計（論文）首頁信息科學與工程 學院課程設(shè)計成績評價表課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目：排序序號評審項目分數(shù)滿分標準說明1內(nèi)容思路清晰；語言表達準確，概念清楚，論點正確；實驗方法科學，分析歸納合理；結(jié)論嚴謹，設(shè)計有應(yīng)用價值。任務(wù)飽滿，做了大量的工作。2創(chuàng)新內(nèi)容新穎，題目能反映新技術(shù)，對前人工作有改進或突破，或有獨特見解3完整性、實用性整體構(gòu)思合理，理論依據(jù)充分，設(shè)計完整，實用性強4數(shù)據(jù)準確、可靠數(shù)據(jù)準確，公式推導正確5規(guī)范性設(shè)計格式、繪圖、圖紙、實驗數(shù)據(jù)、標準的運用等符合有關(guān)標準和規(guī)定6紀律性能很好的遵守各項紀律，設(shè)計過程認真；7答辯準備工作充分，回答問題有理論依據(jù)，基本概念清楚。主要問題回答簡明準確。在規(guī)定的時間內(nèi)作完報告?？偡志C合意見指導教師 年 月 日1、需求分析直接插入排序思路:設(shè)有一組關(guān)鍵字{K1,K2,…….,Kn},排序開始變認為K1是一個有序的序列，讓K2插入到表長為1的有序序列，使之成為一個表長為2的有序序列，讓K3插入到表長為2的有序序列，使之成為一個表長為3的有序序列，依次類推，最后讓Kn插入上述表長為n-1的有序序列，得到一個表長為n的有序序列.希爾排序思路：先取一個正整數(shù)d1(d1<n),把全部記錄分成d1個組,所有距離為d1的倍數(shù)的記錄看成是一組，然后在各組內(nèi)進行插入排序；然后取d2(d2<d1),重復上述分組和排序操作，直到取di=1(>=1),即所有記錄成為一個組為此.一般選d1約為n/2,d2為d1/2,…….,di=1快速排序：(遞歸和非遞歸)思路:以第一個關(guān)鍵字K1為控制字，將［K1、K2、…人川分成兩個子區(qū)，使左區(qū)的有關(guān)鍵字小于等于K1,右區(qū)所有關(guān)鍵字大于等于K1,最后控制居兩個子區(qū)中間的適當位置。在子區(qū)內(nèi)數(shù)據(jù)尚處于無序狀態(tài)。將右區(qū)首、尾指針保存入棧，對左區(qū)進行與第(1)步相類似的處理，又得到它的左子區(qū)和右子區(qū)，控制字區(qū)中。重復第(1)、(2)步，直到左區(qū)處理完畢。然后退棧對一個個子區(qū)進行相類似的處理，直到?？辗謪^(qū)處理函數(shù)hoare思路：首先用兩個指針i、j分別指向首、尾兩個關(guān)鍵字，i=1,j=8。如對(46、56、文檔來源為 文檔來源為 :從網(wǎng)絡(luò)收集整理 .word版本可編輯 .歡迎下載支持文檔來源為 文檔來源為 :從網(wǎng)絡(luò)收集整理 .word版本可編輯 .歡迎下載支持 .14、43、95、10、19、72）。第一個關(guān)鍵字 46作為控制字，該關(guān)鍵字所屬的記錄另存儲在一個x變量中。從文件右端元素r[j].key開始與控制字x.key相比較，當r[j].key大于等于x.key時，r[j]不移動，彳改指針j,j--,直到r[j].key<x.key,把記錄r[j]移動到文件左邊i所指向的位置；然后在文件左邊修改i指針,i++,讓r[i].key與x.key相比較，當r[i].key小于等于x.key時，r[i]不移動，修改指針i,i--,直到r[i].key<x.key,把記錄r[i]移動到文件右邊j所指向的位置；然后在文件右邊修改 j指針j--。重復上面的步驟 .堆排序思路：把 n個記錄存于向量 r之中，把它看成完全二叉樹，此時關(guān)鍵字序列不一定滿足堆的關(guān)系。堆排序大體分為兩步處理：初建堆，從堆的定義出發(fā)，當i=1、2、。。。。、[2/n]時應(yīng)滿足ki<=k2i和ki<=k2i+1.所以先取 i=[n/2]（它一定是第 n個結(jié)點的雙親編號 ）,將以i結(jié)點為根的子樹調(diào)整為堆，然后令 i=i-1，將以不結(jié)點為根的子樹調(diào)整為堆。此時可能會反復調(diào)整某些結(jié)點，直到 i=1為止，堆初步建成。堆排序，首先輸出堆頂元素（一般是最小值） ,讓堆中最后一個元素上移到原堆頂位置，然后恢復堆。 因為經(jīng)過第一步輸出堆頂元素的操作后， 往往破壞了堆關(guān)系，所以要恢復堆；重復執(zhí)行輸出堆頂元素、堆尾元素上移和恢復堆的步驟。概要設(shè)計頭文件#include<stdio.h>#include<stdlib.h>#include<cstdlib>#include<time.h>、ADTstructelement{intkey;}list[20];structrnode{intkey;intpoint;};各種操作函數(shù)：（1）創(chuàng)建一個數(shù)組函數(shù)： intcreat（）；（2）輸出數(shù)組函數(shù)： voidprint（structelementa[20],intn）；（3）保存函數(shù)： voidsave（structelementa[SIZE],intn,charfileName[]）（4）直接插入排序函數(shù)： voidinsert_sort（elementa[],intn）（5）希爾排序函數(shù)： voidshell（structelementa[20],intn）；（6）快速排序函數(shù)（分區(qū)處理函數(shù)） ：inthoare（structelementa[20],intl,inth）；（7）非遞歸的快速排序函數(shù)： voidquick1（structelementa[20],intn）；（8）遞歸的快速排序函數(shù)： voidquick2（structelementa[20],intl,inth）；（9）堆排序（調(diào)整堆的函數(shù)） ：voidheap（structelementa[20],inti,intm）；（10）堆排序（主體函數(shù)） ：voidheapsort（structelementa[20],intn；）（11）時間函數(shù)： start=clock（）;end=clock（）;主函數(shù)Voidmain（）{接受命令（選擇要執(zhí)行的操作） ；處理命令；輸出結(jié)果；}詳細設(shè)計程序源代碼：#include<stdio.h>#include<stdlib.h>#include<cstdlib>#include<time.h>#defineSIZE1000000structelement{intkey;}list[SIZE];///////創(chuàng)建一個數(shù)組 ////////intcreat(){inti,n;intnum;n=0;printf("請輸入元素個數(shù) :");scanf("%d",&num);for(i=0;i<num;i++){list[n].key=rand()%10000;n++;}return(n);}/////////////輸出數(shù)組 /////////////voidprint(structelementa[SIZE],intn){inti;for(i=0;i<n;i++)printf("%5d",a[i].key);printf("\n");/////////////保存到文件 /////////////voidsave(structelementa[SIZE],intn,charfileName[]){intm_wr=0;//寫入TXT文件變量FILE*fp;if((fp=fopen(fileName,"w"))==NULL)printf("Filewritererror\n");for(intm=0;m<n;m++){m_wr=a[m].key;fprintf(fp,"%d",m_wr); //寫入TXT中}fclose(fp);}////////////////////直接插入排序 ///////////////////voidinsert_sort(elementa[],intn){inti,j;elementnext;for(i=1;i<n;i++){next=a[i];for(j=i-1;j>=0&&next.key<a[j].key;j--)a[j+1].key=a[j].key;a[j+1]=next;}printf("輸出直接插入排序的結(jié)果 :\n");}/////////////////希爾排序 //////////////////////voidshell(structelementa[SIZE],intn){inti,j,k;for(i=n;i>=1;i--)a[i].key=a[i-1].key;k=n/2;while(k>=1){for(i=k+1;i<=n;i++){a[0].key=a[i].key;j=i-k;while((a[j].key>a[0].key)&&(j>=0)){a[j+k].key=a[j].key;j=j-k;}a[j+k]=a[0];}k=k/2;}for(i=0;i<n;i++)a[i].key=a[i+1].key;printf("輸出希爾排序的結(jié)果 :\n");}////////////////////快速排序 ///////////////////////////inthoare(structelementa[SIZE],intl,inth)//分區(qū)處理函數(shù){inti,j;structelementx;i=l;j=h;x.key=a[i].key;do{while((i<j)&&(a[j].key>=x.key))j--;if(i<j){a[i].key=a[j].key;i++;}while((i<j)&&(a[i].key<=x.key))i++;if(i<j){a[j].key=a[i].key;j--;}}while(i<j);a[i].key=x.key;return(i);}voidquick1(structelementa[SIZE],intn) //非遞歸的快速排序{inti,l,h,tag,top;ints[20][2];l=0;h=n-1;tag=1;top=0;dowhile(l<h){i=hoare(a,l,h);top++;s[top][0]=i+1;s[top][1]=h;h=h-1;}if(top==0)tag=0;else{l=s[top][0];h=s[top][1];top--;}}while(tag==1);}voidquick2(structelementa[SIZE],intl,inth)〃遞歸的快速排序{inti;if(l<h){i=hoare(a,l,h); //劃為兩個區(qū)quick2(a,l,i-1); //對左分區(qū)快速排序quick2(a,i+1,h); //對右分區(qū)快速排序}}////////////////////堆排序函數(shù) ////////////////////////////調(diào)整堆的函數(shù)voidheap(structelementa[SIZE],inti,intm)/*i是根結(jié)點編號 ,m是以i為根的子樹的最后一個結(jié)點編號 */{structelementx;intj;x.key=a[i].key; //保存記錄內(nèi)容j=2*i; //j為左孩子編號while(j<=m){if(j<m)if(a[j].key>a[j+1].key) //當結(jié)點 i有左 ,右兩個孩子時 ,j取關(guān)鍵較小的孩子編號j++;if(a[j].key<x.key) //向下一層探測{a[i].key=a[j].key;i=j;j=2*i;}elsej=m+1; //x.key小于左，右孩子的關(guān)鍵字時,使j>m,以便結(jié)束循環(huán)}a[i].key=x.key;}//堆排序的主體函數(shù)voidheapsort(structelementa[SIZE],intn){inti,v;structelementx;for(i=n;i>0;i--)a[i].key=a[i-1].key;for(i=n/2;i>=1;i--)heap(a,i,n);for(v=n;v>=2;v--){x.key=a[1].key; //堆頂堆尾元素交換a[1].key=a[v].key;a[v].key=x.key;heap(a,1,v-1); //這次比上次少處理一個記錄}for(i=0;i<n;i++)a[i].key=a[i+1].key;for(i=0;i<n/2;i++){intk;k=a[i].key;a[i].key=a[n-i-1].key;a[n-i-1].key=k;}}voidmain(){intnum,l,h,c;clock_tstart,end;c=1;charfile1[50]="直接插入排序 .txt";charfile2[50]="希爾排序 .txt";charfile3[50]="非遞歸的快速排序 .txt";charfile4[50]="遞歸的快速排序 .txt";charfile5[50]="堆排序.txt";文檔來源為 文檔來源為 :從網(wǎng)絡(luò)收集整理 .word版本可編輯 .歡迎下載支持 .printf("***********歡迎使用本系統(tǒng)學習各種排序 *************\n");*\n");printf("*1生成隨機排序元素*\n"printf("*2直接插入排序*\n"printf("*3希爾排序*\n"printf("*4非遞歸的快速排序*\n"printf("*5遞歸的快速排序*\n"printf("*6堆排序*\n"printf("*0退出*\n"printf("*溫馨提示：首先請生成用于排序的元素，以便進行排序);););););););主菜單************************\n");printf("********************printf("**************************************************\n");while(c!=0)printf("*請輸入0-6進行操作\n");scanf("%d",&c);switch(c)case1:num=creat();print(list,num);break;case2:start=clock();insert_sort(list,num);end=clock();print(list,num);save(list,num,file1);printf("Thetime:%dms\n",end-start);break;case3:start=clock();shell(list,num);end=clock();文檔來源為 文檔來源為 :從網(wǎng)絡(luò)收集整理 .word版本可編輯 .歡迎下載支持print(list,num);save(list,num,file2);printf("Thetime:%dms\n",end-start);break;case4:start=clock();quick1(list,num);end=clock();print(list,num);save(list,num,file3);printf("Thetime:%dms\n",end-start);break;case5:l=0;h=num-1;start=clock();quick2(list,l,h);end=clock();printf("輸出遞歸快速排序結(jié)果 :\n");print(list,num);save(list,num,file4);printf("Thetime:%dms\n",end-start);break;case6:start=clock();heapsort(list,num);end=clock();print(list,num);save(list,num,file5);printf("Thetime:%dms\n",end-start);break;}}}//mainend調(diào)試分析insertion_sort排序算法分析：該算法的時間復雜度為 O(n*n).直接插入排序是穩(wěn)定的排序方法。當 n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復雜度 O(n)和最壞時問復雜度0(n2)差別不大。shell排序算法分析：Shell排序算法的時間復雜度分析比較復雜，實際所需的時間取決于各次排序時增量的個數(shù)和增量的取值。當 n較大時，比較和移動的次數(shù)約在 nl.25到，所以Shell排序算法是一種不穩(wěn)定的排序算法。quick排序算法分析：快速排序主體算法時間運算約為 O(log2n),劃分子區(qū)函數(shù)運算量約為 O(n),所總時復雜度為 O(nlog2n).因為快速排序的記錄移動次數(shù)不大于比較的次數(shù)，所以快速排序的最壞時間復雜度應(yīng)為 0(n2),最好時間復雜度為O(nlgn)。heapsort排序算法分析：堆排序中 heap算