快速排序-實驗報告

《快速排序-實驗報告》由會員上傳分享，免費在線閱讀，更多相關內容在應用文檔-天天文庫。

1、福建江夏學院《數(shù)據(jù)結構與關系數(shù)據(jù)庫（本科）》實驗報告姓名班級學號實驗日期課程名稱數(shù)據(jù)結構與關系數(shù)據(jù)庫（本科）指導教師成績實驗名稱：快速排序一、實驗目的1、掌握快速排序算法；二、實驗環(huán)境1、硬件環(huán)境：微機2、軟件環(huán)境：WindowsXP，VC6.0三、實驗內容、步驟及結果1、實驗內容：對于給定的一組關鍵字，編寫一個快速排序的程序并進行排序輸出。3、代碼：#include#include#defineMAXSIZE1000typedefintKeyType;typedefstruct{K

2、eyTypekey;/*關鍵碼字段，可以是整型、字符串型、構造類型等*/}ElemType;ElemTyper[MAXSIZE];/*順序存儲結構*/typedefstruct{ElemType*r;/*數(shù)組基址*/intlength;/*表長度*/}S_TBL;voidCreateTestData(S_TBL*tbl){tbl->r=r;tbl->r[0].key=0;//輔助單元，默認存放0tbl->r[1].key=503;tbl->r[2].key=87;tbl->r[3].key=512;tbl->r[4].k

3、ey=61;tbl->r[5].key=908;tbl->r[6].key=170;第5頁共5頁tbl->r[7].key=889;tbl->r[8].key=276;tbl->r[9].key=675;tbl->r[10].key=453;tbl->length=10;}voidPrintData(S_TBL*tbl){printf("R[0]:%dR[1-%d]:",tbl->r[0].key,tbl->length);for(inti=1;i<=tbl->length;i++){printf("%03d",tbl-

4、>r[i].key);}printf("");}/*直接插入排序*/voidInsertSort(S_TBL*p){inti,j;for(i=2;i<=p->length;i++){if(p->r[i].keyr[i-1].key)/*小于時，需將elem[i]插入有序表*/{p->r[0].key=p->r[i].key;/*為統(tǒng)一算法設置監(jiān)測*/for(j=i-1;p->r[0].keyr[j].key;j--){p->r[j+1].key=p->r[j].key;/*記錄后移*/}p->r[j+

5、1].key=p->r[0].key;/*插入到正確位置*/}//PrintData(p);}}/*希爾排序*/voidShellInsert(S_TBL*p,intdk){/*一趟增量為dk的插入排序，dk為步長因子*/inti,j;for(i=dk+1;i<=p->length;i++){if(p->r[i].keyr[i-dk].key)/*小于時，需elem[i]將插入有序表*/{p->r[0]=p->r[i];/*為統(tǒng)一算法設置監(jiān)測*/for(j=i-dk;j>0&&p->r[0].keyr[j

6、].key;j=j-dk){p->r[j+dk]=p->r[j];/*記錄后移*/第5頁共5頁}p->r[j+dk]=p->r[0];/*插入到正確位置*/}}}voidShellSort(S_TBL*p,intdlta[],intt){/*按增量序列dlta[0，1…，t-1]對順序表*p作希爾排序*/for(intk=0;k

7、p){inti,j,n,noswap=0;ElemTypeswap;n=p->length;for(i=1;i<=n-1&&!noswap;i++){noswap=1;for(j=n-1;j>=i;j--){if(p->r[j].key>p->r[j+1].key){swap=p->r[j];p->r[j]=p->r[j+1];p->r[j+1]=swap;noswap=0;}}PrintData(p);}}/*簡單選擇排序*/voidSelectSort(S_TBL*s){inti,j,t;ElemTypeswap;f

8、or(i=1;ilength;i++){/*作length-1趟選取*/for(j=i+1,t=i;j<=s->length;j++){/*在i開始的length-n+1個記錄中選關鍵碼最小的記錄*/if(s->r[t].key>s->r[j].key)第5頁共5頁t=j;/*t中存放關鍵碼最小記錄的下標*/