資源描述:
《實(shí)驗(yàn)五:排序方法的比較》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、成績(jī):實(shí)驗(yàn)報(bào)告課程名稱:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)項(xiàng)目:排序方法的比較姓名:李翠超專業(yè):計(jì)算機(jī)科學(xué)與技術(shù)班級(jí):計(jì)算機(jī)16-6學(xué)號(hào):1609040307計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院實(shí)驗(yàn)教學(xué)中心2017年12月20日哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院實(shí)驗(yàn)教學(xué)中心實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)項(xiàng)目名稱:排序方法的比較一、實(shí)驗(yàn)?zāi)康?.通過(guò)實(shí)驗(yàn)掌握排序的基本概念,掌握各種排序的基本思想和算法實(shí)現(xiàn)。2.能夠較為靈活的選用某種排序方法解決問(wèn)題二、實(shí)驗(yàn)內(nèi)容1.實(shí)現(xiàn)常用的內(nèi)部排序算法并進(jìn)行比較:如起泡排序、直接插入排序、簡(jiǎn)單選擇排序、快速排序等至少四種排序算法。試通過(guò)隨機(jī)
2、數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù),以取得直觀感受。以實(shí)踐教學(xué),加深對(duì)教材內(nèi)容的吸收,提升自己。2.冒泡排序的基本思想:通過(guò)對(duì)待排序序列從后向前(從下標(biāo)較大的元素開始),依次比較相鄰元素的排序碼,若發(fā)現(xiàn)逆序則交換,使排序碼較小的元素逐漸從后部移向前部(從下標(biāo)較大的單元移向下標(biāo)較小的單元),就象水底下的氣泡一樣逐漸向上冒。3.直接插入排序基本思想:把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無(wú)序表,開始時(shí)有序表中只包含一個(gè)元素,無(wú)序表中包含有n-1個(gè)元素,排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素,把它的排序碼依次與
3、有序表元素的排序碼進(jìn)行比較,將它插入到有序表中的適當(dāng)位置,使之成為新的有序表。4.快速排序的基本思想是:任取待排序序列中的某個(gè)元素作為基準(zhǔn)(一般取第一個(gè)元素),通過(guò)一趟排序,將待排元素分為左右兩個(gè)子序列,左子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼,右子序列的排序碼則大于基準(zhǔn)元素的排序碼,然后分別對(duì)兩個(gè)子序列繼續(xù)進(jìn)行排序,直至整個(gè)序列有序。三、實(shí)驗(yàn)操作步驟1.閱讀實(shí)驗(yàn)內(nèi)容和要求?2.基本要求:待排序表的表長(zhǎng)不小于100;至少要用5組不同的輸入數(shù)據(jù)作測(cè)試;至少完成四個(gè)算法。????3.根據(jù)編譯的結(jié)果,如果錯(cuò)誤的及時(shí)找
4、出并改正四、實(shí)驗(yàn)結(jié)果分析哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院實(shí)驗(yàn)教學(xué)中心實(shí)驗(yàn)報(bào)告五、源代碼#include#include#defineOK1#defineERROR0#defineMAX_LENGTH_INSERT_SORT7//用于快速排序時(shí)判斷是否選用插入排序闕值#defineMAXSIZE10000//用于要排序數(shù)組個(gè)數(shù)最大值,可根據(jù)需要修改#defineMax20typedefstruct{intr[MAXSIZE+1];//用于存儲(chǔ)要排序數(shù)組,r[0]用作哨兵或臨時(shí)變量int
5、length;//用于記錄順序表的長(zhǎng)度}SqList;//交換L中數(shù)組r的下標(biāo)為i和j的值voidswap(SqList*L,inti,intj){inttemp=L->r[i];L->r[i]=L->r[j];L->r[j]=temp;}voidprint(SqListL){inti;for(i=1;i
6、i,j;哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院實(shí)驗(yàn)教學(xué)中心實(shí)驗(yàn)報(bào)告for(i=1;ilength;i++){for(j=L->length-1;j>=i;j--){//注意j是從后往前循環(huán){if(L->r[j]>L->r[j+1]){//若前者大于后者(注意這里與上一算法的差異)swap(L,j,j+1);//交換L->r[j]與L->r[j+1]的值}}}}//對(duì)順序表L作簡(jiǎn)單選擇排序voidSelectSort(SqList*L){inti,j,min;for(i=1;ilength;i++){min=
7、i;//將當(dāng)前下標(biāo)定義為最小值下標(biāo)for(j=i+1;j<=L->length;j++){//循環(huán)之后的數(shù)據(jù)if(L->r[min]>L->r[j])//如果有小于當(dāng)前最小值的關(guān)鍵字min=j;//將此關(guān)鍵字的下標(biāo)賦值給min}if(i!=min)//若min不等于i,說(shuō)明找到最小值,交換swap(L,i,min);//交換L->r[i]與L->r[min]的值}}//對(duì)順序表L作直接插入排序voidInsertSort(SqList*L){inti,j;for(i=2;i<=L->length;i++){if(L->
8、r[i]r[i-1]){//需將L->r[i]插入有序子表L->r[0]=L->r[i];//設(shè)置哨兵for(j=i-1;L->r[j]>L->r[0];j--)L->r[j+1]=L->r[j];//記錄后移L->r[j+1]=L->r[0];//插入到正確位置}}}//堆排序,已知L->r[s..m]中記錄的關(guān)鍵字除L