數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)六

實(shí)驗(yàn)六排序一、 實(shí)驗(yàn)?zāi)康?、 掌握內(nèi)部排序的基本算法；2、 分析比較內(nèi)部排序算法的效率。二、 實(shí)驗(yàn)預(yù)習(xí)說明以下概念1、 簡(jiǎn)單排序：將一組記錄按某關(guān)鍵字遞增或遞減的順序排序。2、 希爾排序：又稱“縮小增量排序”屬于插入排序類的方法。3、 快速排序：通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。4、 堆排序：只需要一個(gè)記錄大小的輔助空間，每個(gè)待排序的記錄僅占有一個(gè)存儲(chǔ)空間。三、 實(shí)驗(yàn)內(nèi)容和要求1、編程實(shí)現(xiàn)直接插入排序算法。程序代碼：#include<stdio.h>#include<stdlib.h>#defineERROR0#defineOK1#defineLT(a,b)((a)<(b))#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTyper[MAXSIZE+1];intlength;}Sqlist;intInitList_Sq(Sqlist&L){inti=1;//printf("請(qǐng)輸入待排序的記錄的個(gè)數(shù)：")；//scanf("%d”,&L.length);printf(-請(qǐng)輸入待排序的記錄的關(guān)鍵字(整型數(shù))：")；while(scanf("%d”,&L.r[i])){i++;}L.length=i-1;returnOK;}/*InitList*/voidPrint_Sq(Sqlist&L)/*輸出順序表*/{inti;for(i=1;i<=L.length;i++)printf("%d”,L.r[i]);}voidInsertSort(Sqlist&L){inti,j;for(i=2;i<=L.length;++i)if(LT(L.r[i],L.r[i-1]))//“<”，需將L.r[i]插入有序子表{L.r[0]=L.r[i];//復(fù)制為哨兵L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0],L.r[j]);--j)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//插入到正確位置}}voidmain(){SqlistS;InitList_Sq(S);Print_Sq(S);printf("\n1.簡(jiǎn)單插入排序\n");InsertSort(S);Print_Sq(S);/*printf("3.快速排序\n");QuickSort(S);Print_Sq(S);printf("5.堆排序\n");HeapSort(S);Print_Sq(S);*/}2、輸入待排序序列：49386597132749(以輸入一個(gè)字符作為結(jié)束)1)直接插入排序運(yùn)行結(jié)果(寫出每一趟的狀態(tài))：TOC\o"1-5"\h\z3849 65 97 13 27 491338 49 65 97 27 491327 38 49 65 97 4913273849496597

2）堆排序運(yùn)行結(jié)果（寫出每一趟的狀態(tài)）:3、編程實(shí)現(xiàn)快速排序算法。程序代碼：#include<stdio.h>#include<stdlib.h>#defineERROR0#defineOK1#defineLT(a,b)((a)<(b))#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTyper[MAXSIZE+1];intlength;}Sqlist;intInitList_Sq(Sqlist&L){inti=1;//printf("請(qǐng)輸入待排序的記錄的個(gè)數(shù)：〃)；//scanf(〃%d〃,&L.length);printf(-請(qǐng)輸入待排序的記錄的關(guān)鍵字(整型數(shù))：");while(scanf(〃%d〃,&L.r[i])){i++;}L.length=i-1;returnOK;}/*InitList*/voidPrint_Sq(Sqlist&L)/*輸出順序表*/{inti;for(i=1;i<=L.length;i++)printf("%d”,L.r[i]);}voidInsertSort(Sqlist&L){inti,j;for(i=2;i<=L.length;++i)if(LT(L.r[i],L.r[i-1]))//“<”，需將L.r[i]插入有序子表{L.r[0]=L.r[i];//復(fù)制為哨兵L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0],L.r[j]);--j)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//插入到正確位置}}intPartition(Sqlist&L,intlow,inthigh){//交換順序表L中子表r[low..high]的記錄，樞軸記錄到位，并返回其所在位置，此時(shí)//在它之前(后)的記錄均不大(小)于它。KeyTypepivotkey;L.r[0]=L.r[low];//用子表的第一個(gè)記錄作樞軸記錄pivotkey=L.r[low];//樞軸記錄關(guān)鍵字while(low<high){//從表的兩端交替地向中間掃描while(low<high&&L.r[high]>=pivotkey)--high;L.r[low]=L.r[high];//將比樞軸記錄小的記錄移到低端while(low<high&&L.r[low]<=pivotkey)++low;L.r[high]=L.r[low];//將比樞軸記錄大的記錄移到高端}L.r[low]=L.r[0];//樞軸記錄到位returnlow;//返回樞軸位置}voidQSort(Sqlist&L,intlow,inthigh){//對(duì)順序表L中的子序列L.r[low..high]進(jìn)行快速排序intpivotloc;if(low<high){//長(zhǎng)度大于1pivotloc=Partition(L,low,high);//將L.r[low..high]一分為二QSort(L,low,pivotloc-1);//對(duì)低子表遞歸排序pivotloc是樞軸位置QSort(L,pivotloc+1,high);//對(duì)高子表遞歸排序}}voidQuickSort(Sqlist&L){//對(duì)順序表L作快速排序。QSort(L,1,L.length);}voidmain(){SqlistS;InitList_Sq(S);Print_Sq(S);printf("\n1.簡(jiǎn)單插入排序\n");InsertSort(S);Print_Sq(S);printf("\n2.快速排序\n");QuickSort(S);Print_Sq(S);/*printf("5.堆排序\n");HeapSort(S);Print_Sq(S);*/}輸入待排序序列：49386597132749(以輸入一個(gè)字符作為結(jié)束)運(yùn)行結(jié)果(寫出每一趟的狀態(tài))：初始關(guān)鍵字： 49386597132749完成一趟排序： {273813}49{976549}分別進(jìn)行