實驗六排序一、 實驗目的1、 掌握內部排序的基本算法；2、 分析比較內部排序算法的效率。二、 實驗預習說明以下概念1、 簡單排序：將一組記錄按某關鍵字遞增或遞減的順序排序。2、 希爾排序：又稱“縮小增量排序”屬于插入排序類的方法。3、 快速排序：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。4、 堆排序：只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。三、 實驗內容和要求1、編程實現(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("請輸入待排序的記錄的個數(shù)：")；//scanf("%d”,&L.length);printf(-請輸入待排序的記錄的關鍵字(整型數(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];//復制為哨兵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.簡單插入排序\n");InsertSort(S);Print_Sq(S);/*printf("3.快速排序\n");QuickSort(S);Print_Sq(S);printf("5.堆排序\n");HeapSort(S);Print_Sq(S);*/}2、輸入待排序序列：49386597132749(以輸入一個字符作為結束)1)直接插入排序運行結果(寫出每一趟的狀態(tài))：TOC\o"1-5"\h\z3849 65 97 13 27 491338 49 65 97 27 491327 38 49 65 97 4913273849496597

2）堆排序運行結果（寫出每一趟的狀態(tài)）:3、編程實現(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("請輸入待排序的記錄的個數(shù)：〃)；//scanf(〃%d〃,&L.length);printf(-請輸入待排序的記錄的關鍵字(整型數(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];//復制為哨兵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]的記錄，樞軸記錄到位，并返回其所在位置，此時//在它之前(后)的記錄均不大(小)于它。KeyTypepivotkey;L.r[0]=L.r[low];//用子表的第一個記錄作樞軸記錄pivotkey=L.r[low];//樞軸記錄關鍵字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){//對順序表L中的子序列L.r[low..high]進行快速排序intpivotloc;if(low<high){//長度大于1pivotloc=Partition(L,low,high);//將L.r[low..high]一分為二QSort(L,low,pivotloc-1);//對低子表遞歸排序pivotloc是樞軸位置QSort(L,pivotloc+1,high);//對高子表遞歸排序}}voidQuickSort(Sqlist&L){//對順序表L作快速排序。QSort(L,1,L.length);}voidmain(){SqlistS;InitList_Sq(S);Print_Sq(S);printf("\n1.簡單插入排序\n");InsertSort(S);Print_Sq(S);printf("\n2.快速排序\n");QuickSort(S);Print_Sq(S);/*printf("5.堆排序\n");HeapSort(S);Print_Sq(S);*/}輸入待排序序列：49386597132749(以輸入一個字符作為結束)運行結果(寫出每一趟的狀態(tài))：初始關鍵字： 49386597132749完成一趟排序： {273813}49{976549}分別進行