快速排序-實(shí)驗(yàn)報(bào)告

1、福建江夏學(xué)院數(shù)據(jù)結(jié)構(gòu)與關(guān)系數(shù)據(jù)庫(kù)（本科）實(shí)驗(yàn)報(bào)告姓名 班級(jí) 學(xué)號(hào) 實(shí)驗(yàn)日期 課程名稱 數(shù)據(jù)結(jié)構(gòu)與關(guān)系數(shù)據(jù)庫(kù)（本科） 指導(dǎo)教師 成績(jī)實(shí)驗(yàn)名稱：快速排序一、 實(shí)驗(yàn)?zāi)康?、掌握快速排序算法；二、 實(shí)驗(yàn)環(huán)境1、 硬件環(huán)境：微機(jī)2、 軟件環(huán)境： Windows XP，VC6.0三、實(shí)驗(yàn)內(nèi)容、步驟及結(jié)果1、實(shí)驗(yàn)內(nèi)容：對(duì)于給定的一組關(guān)鍵字，編寫(xiě)一個(gè)快速排序的程序并進(jìn)行排序輸出。3、 代碼：#include <stdio.h>#include <stdlib.h>#define MAXSIZE 1000typedef int KeyType;typedef struct KeyType

2、 key;/* 關(guān)鍵碼字段，可以是整型、字符串型、構(gòu)造類型等*/ElemType;ElemType rMAXSIZE;/* 順序存儲(chǔ)結(jié)構(gòu)*/typedef struct ElemType *r;/* 數(shù)組基址*/ int length;/* 表長(zhǎng)度*/S_TBL;void CreateTestData(S_TBL * tbl) tbl->r=r; tbl->r0.key=0;/輔助單元，默認(rèn)存放0 tbl->r1.key=503; tbl->r2.key=87; tbl->r3.key=512; tbl->r4.key=61; tbl->r5.key=

3、908; tbl->r6.key=170; tbl->r7.key=889; tbl->r8.key=276; tbl->r9.key=675; tbl->r10.key=453; tbl->length=10;void PrintData(S_TBL * tbl) printf("R0:%d R1-%d:",tbl->r0.key,tbl->length);for(int i=1;i<=tbl->length;i+)printf("%03d ",tbl->ri.key);printf(&

4、quot;n");/*直接插入排序*/void InsertSort(S_TBL * p)int i,j;for(i=2;i<=p->length;i+)if(p->ri.key < p->ri-1.key) /*小于時(shí)，需將elemi插入有序表*/ p->r0.key=p->ri.key; /*為統(tǒng)一算法設(shè)置監(jiān)測(cè)*/ for(j=i-1;p->r0.key<p->rj.key;j-) p->rj+1.key=p->rj.key;/*記錄后移*/p->rj+1.key=p->r0.key;/*插入到正

5、確位置*/PrintData(p);/*希爾排序*/void ShellInsert(S_TBL *p,int dk) /*一趟增量為dk 的插入排序，dk 為步長(zhǎng)因子*/int i,j; for(i=dk+1;i<=p->length;i+)if(p->ri.key < p->ri-dk.key) /*小于時(shí)，需elemi將插入有序表*/ p->r0=p->ri;/*為統(tǒng)一算法設(shè)置監(jiān)測(cè)*/ for(j=i-dk;j>0 && p->r0.key<p->rj.key;j=j-dk) p->rj+dk=p-&

6、gt;rj;/*記錄后移*/p->rj+dk=p->r0;/*插入到正確位置*/void ShellSort(S_TBL *p,int dlta,int t) /*按增量序列dlta0，1，t-1對(duì)順序表*p 作希爾排序*/ for(int k=0;k<t;k+) ShellInsert(p,dltak);/*一趟增量為dltak的插入排序*/ /PrintData(p);/*冒泡排序*/void BubbleSort(S_TBL *p)int i,j,n,noswap=0;ElemType swap;n=p->length;for(i=1;i<=n-1 &

7、;& !noswap;i+)noswap=1;for(j=n-1;j>=i;j-)if(p->rj.key>p->rj+1.key)swap=p->rj;p->rj=p->rj+1;p->rj+1=swap;noswap=0;PrintData(p);/*簡(jiǎn)單選擇排序*/void SelectSort(S_TBL *s) int i,j,t;ElemType swap;for(i=1;i<s->length;i+) /* 作length-1 趟選取*/for(j=i+1,t=i;j<=s->length;j+) /

8、* 在i 開(kāi)始的length-n+1 個(gè)記錄中選關(guān)鍵碼最小的記錄*/if(s->rt.key>s->rj.key)t=j;/* t 中存放關(guān)鍵碼最小記錄的下標(biāo)*/swap=s->rt;/* 關(guān)鍵碼最小的記錄與第i 個(gè)記錄交換*/ s->rt=s->ri;s->ri=swap;PrintData(s);int Partition(S_TBL *tbl,int low,int high) /*一趟快排序*/ /*交換順序表tbl 中子表tbl->lowhigh的記錄，使支點(diǎn)記錄到位，并反回其所在位置*/ /*此時(shí)，在它之前(后)的記錄均不大(小)于它

9、*/int pivotkey;tbl->r0=tbl->rlow; /*以子表的第一個(gè)記錄作為支點(diǎn)記錄*/pivotkey=tbl->rlow.key; /*取支點(diǎn)記錄關(guān)鍵碼*/while(low<high) /*從表的兩端交替地向中間掃描*/ while(low<high&&tbl->rhigh.key>=pivotkey) high-;tbl->rlow=tbl->rhigh; /*將比支點(diǎn)記錄小的交換到低端*/PrintData(tbl);while(low<high&&tbl->rlow.

10、key<=pivotkey) low+;tbl->rhigh=tbl->rlow; /*將比支點(diǎn)記錄大的交換到低端*/PrintData(tbl);tbl->rlow=tbl->r0; /*支點(diǎn)記錄到位*/PrintData(tbl);return low; /*反回支點(diǎn)記錄所在位置*/void QSort(S_TBL *tbl,int low,int high) /*遞歸形式的快排序*/ /*對(duì)順序表tbl 中的子序列tbl->lowhigh作快排序*/int pivotloc;if(low<high) pivotloc=Partition(tbl,low,high); /*將表一分為二*/PrintData(tbl);QSort(tbl,low,pivotloc-1); /*對(duì)低子表遞歸排序*/QSort(tbl,pivotloc+1,high); /*對(duì)高子表遞歸排序*/int main(void) S_TBL * tbl=(S_TBL *)malloc(sizeof(S_TBL); CreateTestData(tbl);/InsertSort(tbl);/int