數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-排序算法實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)成果報(bào)告排序算法實(shí)現(xiàn)學(xué)生學(xué)號(hào)： 學(xué)生姓名： 學(xué) 院： 計(jì)算機(jī)學(xué)院 專(zhuān)業(yè)班級(jí)： 軟件工程 1341 專(zhuān)業(yè)課程： 數(shù)據(jù)結(jié)構(gòu)與算法 指導(dǎo)教師： 2014 年 12 月 29 日題 目排序算法實(shí)現(xiàn)考核項(xiàng)目考核內(nèi)容得分平時(shí)考核（30分）出勤情況、態(tài)度、效率；知識(shí)掌握情況、基本操作技能、知識(shí)應(yīng)用能力、獲取知識(shí)能力系統(tǒng)設(shè)計(jì)（20分）分析系統(tǒng)的功能模塊編程調(diào)試（20分）實(shí)現(xiàn)系統(tǒng)的各個(gè)功能模塊，并完成調(diào)試回答問(wèn)題（15分）回答老師針對(duì)課程設(shè)計(jì)提出的問(wèn)題課程設(shè)計(jì)報(bào)告撰寫(xiě)（10分）嚴(yán)格按照規(guī)范要求完成課程設(shè)計(jì)報(bào)告源代碼（5分）按照規(guī)范要求完成課程設(shè)計(jì)源代碼的排版總 評(píng) 成 績(jī)指導(dǎo)教師評(píng)語(yǔ)： 日期： 年 月 日目 錄1課程設(shè)計(jì)目標(biāo)與任務(wù)11.1 課程設(shè)計(jì)目標(biāo)11.2 課程設(shè)計(jì)任務(wù)11.3 課程設(shè)計(jì)基本要求12 分析與設(shè)計(jì)22.1 題目需求分析22.2 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)32.3 算法描述42.4 程序流程圖72.5 程序測(cè)試說(shuō)明73 程序清單84.測(cè)試134.1 測(cè)試數(shù)據(jù)134.2 測(cè)試結(jié)果分析135 總結(jié)14參考文獻(xiàn)151 課程設(shè)計(jì)目標(biāo)與任務(wù)1.1 課程設(shè)計(jì)目標(biāo)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實(shí)踐教學(xué)環(huán)節(jié)。該實(shí)踐教學(xué)是軟件設(shè)計(jì)的綜合訓(xùn)練,包括問(wèn)題分析，總體結(jié)構(gòu)設(shè)計(jì)用戶(hù)界面設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧。要求學(xué)生在設(shè)計(jì)中逐步提高程序設(shè)計(jì)能力培養(yǎng)科學(xué)的軟件工作方法學(xué)生通過(guò)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)各方面得到鍛煉。1.2 課程設(shè)計(jì)任務(wù)設(shè)計(jì)排序相關(guān)函數(shù)庫(kù)，以便在程序設(shè)計(jì)中調(diào)用，要求設(shè)計(jì)程序，產(chǎn)生20000個(gè)隨機(jī)數(shù)，完成下面功能：（1）對(duì)這些數(shù)分別進(jìn)行直接插入排序、折半插入排序、希爾排序、起泡排序、快速排序、簡(jiǎn)單選擇排序，堆排序，2路-歸并排序等排序，并把排序結(jié)果進(jìn)行保存。（2）最好能借助語(yǔ)言環(huán)境實(shí)現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來(lái)，將復(fù)雜的運(yùn)行過(guò)程以動(dòng)態(tài)方式顯示出來(lái)；（3）給出若干例程，演示通過(guò)調(diào)用自己所寫(xiě)程序來(lái)實(shí)現(xiàn)相關(guān)問(wèn)題的要求。1.3 課程設(shè)計(jì)基本要求嚴(yán)格按照題意要求，獨(dú)立進(jìn)行設(shè)計(jì)，不能隨意更改。若確因條件所限，必須要改變課題要求時(shí)，應(yīng)在征得指導(dǎo)教師同意的前提下進(jìn)行。學(xué)生應(yīng)制定實(shí)習(xí)工作計(jì)劃，認(rèn)真完成實(shí)習(xí)的各個(gè)環(huán)節(jié)，并在老師的指導(dǎo)下認(rèn)真組織實(shí)習(xí)工作，撰寫(xiě)實(shí)習(xí)報(bào)告，做好實(shí)習(xí)總結(jié)。2 分析與設(shè)計(jì)2.1 題目需求分析1.直接插入排序思路：設(shè)有一組關(guān)鍵字K1,K2.Kn，排序開(kāi)始便認(rèn)為K1是一個(gè)有序的序列，讓K2插入到表長(zhǎng)為1的有序序列，使之成為一個(gè)表長(zhǎng)為2的有序序列，讓K3插入到表長(zhǎng)為2的有序序列，使之成為表長(zhǎng)為3的有序序列，依次類(lèi)推，最后Kn插入到上述表長(zhǎng)為n-1的有序序列，得到一個(gè)表長(zhǎng)為n的有序序列。2.折半插入排序思路：在將一個(gè)新元素插入已排好序的數(shù)組的過(guò)程中，尋找插入點(diǎn)時(shí)，將待插入?yún)^(qū)域的首元素設(shè)置為alow,末元素設(shè)置為ahigh，則輪比較時(shí)將待插入元素與am,其中m=(low+high)/2相比較,如果比參考元素小，則選擇alow到am-1為新的插入?yún)^(qū)域(即high=m-1)，否則選擇am+1到ahigh為新的插入?yún)^(qū)域（即low=m+1），如此直至low=high不成立，即將此位置之后所有元素后移一位，并將新元素插入ahigh+1。3.希爾排序思路：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2,d2d1,再將到d2作為增量繼續(xù)分組，再進(jìn)行直接插入排序，依次向下取值，直到完成排序。4.起泡排序思路：比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。5.快速排序思路：快速排序的實(shí)現(xiàn)基于分治法，具體分為三個(gè)步驟。假設(shè)待排序的序列為L(zhǎng)m.n。序列Lm . n被劃分成兩個(gè)可能為空的子序列Lm . pivot-1和Lpivot+1 . n，使Lm . pivot-1的每個(gè)元素均小于或等于Lpivot，同時(shí)Lpivot+1. n的每個(gè)元素均大于Lpivot。其中Lpivot稱(chēng)為這一趟分割中的主元（也稱(chēng)為樞軸、支點(diǎn)）。通過(guò)遞歸調(diào)用快速排序，對(duì)子序列Lm . pivot-1和Lpivot+1 . r排序。 由于兩個(gè)子序列是就地排序的，所以對(duì)它們的合并不需要操作，整個(gè)序列Lm . n已排好序。6.簡(jiǎn)單選擇排序思路：序序列的記錄個(gè)數(shù)為。i取1,2,n-1,從所有n-i+1個(gè)記錄（R,Ri+1,Rn中找出排序碼最小的記錄，與第個(gè)記錄交換。執(zhí)行n-1趟 后就完成了記錄序列的排序。2.2 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)此程序采用的是線(xiàn)性表的動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)：#define LIST_INIT_SIZE 100/線(xiàn)性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT 10/線(xiàn)性表存儲(chǔ)空間的分配增量Typedef structElemType *elem;/存儲(chǔ)空間基址Int length;/當(dāng)前長(zhǎng)度Int listsize;/當(dāng)前分配的存儲(chǔ)容量（以sizeof(ElemType)為單位）SqList;上述定義中，數(shù)組指針elem指示存儲(chǔ)空間基址，length表示線(xiàn)性表的當(dāng)前長(zhǎng)度，對(duì)線(xiàn)性表的初始化操作就是為順序表預(yù)定義大小的數(shù)組空間，并將線(xiàn)性表的當(dāng)前長(zhǎng)度設(shè)為“0”，listsize指示當(dāng)前分配的存儲(chǔ)空間大小，一旦元素插入而空間不足，可進(jìn)行再分配。1.3 算法描述1.直接插入排序 設(shè)置R0為哨兵，將剩下的數(shù)值逐個(gè)進(jìn)行插入，直至完成一趟排序：void InsertSort ( elem R , int n) / 對(duì)記錄序列R1.n作直接插入排序。 for ( i=2; i=n; +i ) R0 = Ri; / 復(fù)制為監(jiān)視哨 for ( j=i-1; R0 Rj; -j ) Rj+1 = Rj; / 記錄后移 Rj+1 = R0; / 插入到正確位置 / InsertSort2.折半插入排序因?yàn)镽1.i-1是一個(gè)按關(guān)鍵字有序的序列，則可以利用折半查找實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置：void BInsertSort (elem R ， int n) / 對(duì)記錄序列R1.n作折半插入排序。 for ( i=2; i=n; +i ) R0 = Ri; / 將Ri暫存到R0 low = 1; high = i-1; while ( low = high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0 =high+1; -j ) Rj+1 = Rj; / 記錄后移 Rhigh+1 = R0; / 插入 / BInsertSort3.希爾排序先取一個(gè)正整數(shù)d1n，把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序，然后取d2d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹梗簐oid ShellInsert ( elem R , int dk ) / 對(duì)待排序列R作一趟希爾插入排序 for ( i=dk+1; i=n; +i ) if ( Ri Ri-dk) void ShellSort (elem R , int d , int t) / 按增量序列d 0.t-1對(duì)順序表L作希爾排序。 for ( k=0; k0 & R01) for ( j = 1; j i; j+ ) if (R j+1 R j ) Swap(R j , R j+1 ); /if / while / BubbleSort5.快速排序選定一個(gè)中間數(shù)作為參考，所有元素與之比較，小的調(diào)到其左邊，大的調(diào)到其右邊：int Partition (Elem R, int low, int high) / 交換記錄子序列Rlow.high中的記錄，使樞軸記錄到位，并返回其所/ 在位置，此時(shí)，在它之前（后）的記錄均不大（?。┯谒黂0 = Rlow; / 用子表的第一個(gè)記錄作樞軸記錄pivotkey = Rlow; / 樞軸記錄關(guān)鍵字while (lowhigh) / 從表的兩端交替地向中間掃描while(low=pivotkey)-high;Rlow = Rhigh; / 將比樞軸記錄小的記錄移到低端while (lowhigh & Rlow=pivotkey) +low;Rhigh = Rlow; / 將比樞軸記錄大的記錄移到高端Rlow = R0; / 樞軸記錄到位return low; / 返回樞軸位置 / Partitionvoid QSort (Elem R, int low, int high) / 對(duì)記錄序列Rlow.high進(jìn)行快速排序if (low high) / 長(zhǎng)度大于1pivotloc = Partition(L, low, high); / 將L.rlow.high一分為二QSort(L, low, pivotloc-1); / 對(duì)低子表遞歸排序，pivotloc是樞軸位置QSort(L, pivotloc+1, high);/ 對(duì)高子表遞歸排序 / Qsort6.簡(jiǎn)單選擇排序在待排序的數(shù)據(jù)中選出最大（?。┑脑胤旁谄渥罱K的位置：Void SelectSort(SqList &L)/對(duì)順序表做簡(jiǎn)單選擇排序for(i=1;iL.length;+i)/選擇第i小的記錄，交換到位j=SelectMinKey(L,i);/在L.riL.length中選擇key最小記錄if(i!=j)Lri-L.rj;/與第i個(gè)記錄交換/ SelectSort開(kāi)始2.4 程序流程圖顯示菜單輸入序號(hào)簡(jiǎn)單選擇排序快速排序起泡排序希爾排序折半插入排序直接插入排序按輸入序號(hào)輸出結(jié)果結(jié)束圖1-2程序執(zhí)行流程圖開(kāi)始執(zhí)行后，會(huì)出現(xiàn)提示語(yǔ)句，提示1-6分別代表6種排序方法，對(duì)于生成的數(shù)組，點(diǎn)擊1-6任意數(shù)字，調(diào)用相應(yīng)的排序方法進(jìn)行排序。輸出結(jié)果后，按任意鍵結(jié)束。2.5 程序測(cè)試說(shuō)明主函數(shù)會(huì)調(diào)用rand()方法，隨機(jī)產(chǎn)生指定數(shù)目數(shù)值。并將數(shù)值賦予指定數(shù)組，通過(guò)提示語(yǔ)句輸入16數(shù)值，16分別代表不同的排序方式，當(dāng)輸入數(shù)字1時(shí)，通過(guò)switch語(yǔ)句，將執(zhí)行直接插入排序函數(shù)，然后通過(guò)輸出函數(shù)，輸出所需結(jié)構(gòu)。3 程序清單#include#include#include#define MAXE 20000typedef int KeyType;typedef struct /*記錄類(lèi)型*/KeyType key; /*關(guān)鍵字項(xiàng)*/ /InfoType data; /*其他數(shù)據(jù)項(xiàng),類(lèi)型為InfoType*/ RecType;void InsertSort(RecType R,int length);/直接插入排序void BInsertSort (RecType R,int low,int high,int length);/折半插入排序void ShellSort(RecType R,int n);/希爾排序void bubble_sort(RecType R,int length);/起泡排序int FindPos(RecType R,int low,int high);void QuickSort(RecType R,int low,int high);int SelectMinKey(RecType R,int i,int length);void SelectSort(RecType R,int length);/簡(jiǎn)單選擇排序void showSort(RecType R);/快速排序void showSort_F(RecType R);int main(void) int val;int i;RecType RMAXE;srand(unsigned)time(NULL); for(i=0;i=10;i+) Ri.key=(rand()%100+1); printf(產(chǎn)生的隨機(jī)數(shù)序列為：); for(i=0;i=10;i+) printf(%3d,Ri.key); printf(n); printf(隨機(jī)輸入1到6數(shù)字：); scanf(%d,&val); switch(val) case 1: InsertSort(R,10); printf(隨機(jī)數(shù)經(jīng)直接插入排序后：); showSort(R); break; case 2:BInsertSort(R,1,10,10); printf(隨機(jī)數(shù)經(jīng)折半插入排序后：); showSort(R); break; case 3:ShellSort(R,10); printf(隨機(jī)數(shù)經(jīng)希爾插入排序后：); showSort_F(R); break; case 4:bubble_sort(R,10); printf(隨機(jī)數(shù)經(jīng)起泡排序后：); showSort_F(R); break; case 5:QuickSort(R,0,9); printf(隨機(jī)數(shù)經(jīng)快速排序后：); showSort_F(R); case 6:SelectSort(R,10); printf(隨機(jī)數(shù)經(jīng)簡(jiǎn)單選擇排序后：); showSort_F(R); return 0;void InsertSort(RecType R,int length) / 對(duì)數(shù)組a作直接插入排序 int i,j; for(i=2;i=length;+i) if(Ri.keyRi-1.key) / 需將ai插入有序子表 R0.key=Ri.key; / 復(fù)制為哨兵 Ri.key=Ri-1.key; for(j=i-2;R0.keyRj.key;-j) Rj+1.key=Rj.key; / 記錄后移 Rj+1.key=R0.key; / 插入到正確位置 void BInsertSort (RecType R,int low,int high,int length) int m; for ( int i=2; i=length; +i ) R0.key = Ri.key; / 將Ri暫存到R0 low = 1; high = i-1; while ( low = high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0.key =high+1; -j ) Rj+1.key = Rj.key; / 記錄后移 Rhigh+1.key = R0.key; / 插入 / BInsertSortvoid ShellSort(RecType R,int n)/*希爾排序算法*/int i,j,d,k;RecType temp;d=n/2;/*d取初值n/2*/while (d0) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /*Rj與Rj+d交換*/Rj=Rj+d;Rj+d=temp;j=j-d;printf( d=%d: ,d);/*輸出每一趟的排序結(jié)果*/for (k=0;kn;k+)printf(%3d,Rk.key);printf(n); d=d/2; /*遞減增量d*/void bubble_sort(RecType R,int length) / 將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列(起泡排序) int i,j,t; for(i=0;ilength-1;i+) for(j=i+1;jRj.key) t=Ri.key; Ri.key=Rj.key; Rj.key=t; void QuickSort(RecType R,int low,int high)int pos;if(lowhigh)pos=FindPos(R,low,high); QuickSort(R,low,pos-1);QuickSort(R,pos+1,high);int FindPos(RecType R,int low,int high) int val=Rlow.key; while(lowhigh) while(low=val) -high; Rlow.key=Rhigh.key; while(lowhigh&Rlow.key=val) +low; Rhigh.key=Rlow.key; Rlow.key=val; return high; int SelectMinKey(RecType R,int i,int length) / 返回在ai.length中key最小的記錄的序號(hào) int min; int j,k; k=i; / 設(shè)第i個(gè)為最小 min=Ri.key; for(j=i+1;jlength;j+) if(Rj.keymin) / 找到更小的 k=j; min=Rj.key; return k; void SelectSort(RecType R,int length) / 對(duì)數(shù)組a作簡(jiǎn)單選擇排序 int i,j; int t; for(i=0;ilength-1;+i) / 選擇第i小的記錄，并交換到位 j=SelectMinKey(R,i,length); / 在ai.length中選擇最小的記錄 if(i!=j) / 與第i個(gè)記錄交換 t=Ri.key; Ri.key=Rj.key; Rj.key=t; void showSort(RecType R)int i;for(i=1;i=10;i+)printf(%d ,Ri.key);printf(n);void showSort_F(RecType R)int i;for(i=0;i10;i+)printf(%d ,Ri.key);printf(n);4 測(cè)試4.1 測(cè)試數(shù)據(jù)由函數(shù)rand()產(chǎn)生的隨機(jī)數(shù)進(jìn)行測(cè)試。4.2 測(cè)試結(jié)果分析圖1-3直接插入排序當(dāng)輸入數(shù)字1時(shí)，主函數(shù)通過(guò)switch語(yǔ)句調(diào)用直接插入排序，對(duì)數(shù)組進(jìn)行從小到大的排序。圖1-4冒泡排序當(dāng)輸入數(shù)字4時(shí)，主函數(shù)通過(guò)switch語(yǔ)句調(diào)用冒泡排序，對(duì)數(shù)組進(jìn)行從小到大的排序。5 總結(jié)通過(guò)這次課程設(shè)計(jì)的學(xué)習(xí)讓我學(xué)會(huì)了許多，讓我對(duì)專(zhuān)業(yè)知識(shí)有了初步的了解。在這次課程設(shè)計(jì)中，首先實(shí)現(xiàn)隨機(jī)數(shù)的生成，將生成的指定數(shù)目的隨機(jī)數(shù)一一對(duì)應(yīng)的賦予定義的空數(shù)組，經(jīng)選擇語(yǔ)句分別執(zhí)行直接插入排序，折半插入排序，希爾排序，起泡排序，快速排序，簡(jiǎn)單選擇排序等6種排序?qū)?shù)組中的數(shù)值進(jìn)行排序。這次課程設(shè)計(jì)還有許多不足，如部分排序方法編程代碼過(guò)于復(fù)雜，此外，由于編程各種排序方法的區(qū)別較大，使用了不同的輸出函數(shù)，增加了程序的復(fù)雜性。此外，由于能力有限，還有無(wú)法實(shí)現(xiàn)的2種排序。但我也學(xué)到了很多東西，如，掌握一些排序方法的實(shí)現(xiàn)，熟悉了編寫(xiě)代碼的一般步驟：思考問(wèn)題，寫(xiě)出解決方案，寫(xiě)出偽代碼，完成代碼，調(diào)試程序。我從編寫(xiě)過(guò)程中，發(fā)現(xiàn)自己更多的不足，如對(duì)C語(yǔ)言的掌握不夠牢靠，對(duì)于C語(yǔ)言各種函數(shù)的調(diào)用也不夠靈活等。希望在以后的編程過(guò)程中，能更加耐心和細(xì)心，不熟悉也不要慌張，不慌不忙的進(jìn)行程序編寫(xiě)和調(diào)試。參考文獻(xiàn)1數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）嚴(yán)蔚敏 清華大學(xué)出版社 20022數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述 王路群 中國(guó)水利水電出版社 20073數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程（C語(yǔ)言版） 王國(guó)鈞 清華大學(xué)出版社 20094數(shù)據(jù)結(jié)構(gòu)題集嚴(yán)蔚敏,吳偉民編 清華大學(xué)出版社 20025C語(yǔ)言程序設(shè)計(jì)譚浩強(qiáng) 清華大學(xué)出版社6C語(yǔ)言入門(mén)經(jīng)典霍頓（美）清華大學(xué)出版社#include#include#include#define MAXE 20000typedef int KeyType;typedef struct /*記錄類(lèi)型*/KeyType key; /*關(guān)鍵字項(xiàng)*/ /InfoType data; /*其他數(shù)據(jù)項(xiàng),類(lèi)型為InfoType*/ RecType;void InsertSort(RecType R,int length);/直接插入排序void BInsertSort (RecType R,int low,int high,int length);/折半插入排序void ShellSort(RecType R,int n);/希爾排序void bubble_sort(RecType R,int length);/起泡排序int FindPos(RecType R,int low,int high);void QuickSort(RecType R,int low,int high);int SelectMinKey(RecType R,int i,int length);void SelectSort(RecType R,int length);/簡(jiǎn)單選擇排序void showSort(RecType R);/快速排序void showSort_F(RecType R);int main(void) int val;int i;RecType RMAXE;srand(unsigned)time(NULL); for(i=0;i=10;i+) Ri.key=(rand()%100+1); printf(產(chǎn)生的隨機(jī)數(shù)序列為：); for(i=0;i=10;i+) printf(%3d,Ri.key); printf(n); printf(隨機(jī)輸入1到6數(shù)字：); scanf(%d,&val); switch(val) case 1: InsertSort(R,10); printf(隨機(jī)數(shù)經(jīng)直接插入排序后：); showSort(R); break; case 2:BInsertSort(R,1,10,10); printf(隨機(jī)數(shù)經(jīng)折半插入排序后：); showSort(R); break; case 3:ShellSort(R,10); printf(隨機(jī)數(shù)經(jīng)希爾插入排序后：); showSort_F(R); break; case 4:bubble_sort(R,10); printf(隨機(jī)數(shù)經(jīng)起泡排序后：); showSort_F(R); break; case 5:QuickSort(R,0,9); printf(隨機(jī)數(shù)經(jīng)快速排序后：); showSort_F(R); case 6:SelectSort(R,10); printf(隨機(jī)數(shù)經(jīng)簡(jiǎn)單選擇排序后：); showSort_F(R); return 0;void InsertSort(RecType R,int length) / 對(duì)數(shù)組a作直接插入排序 int i,j; for(i=2;i=length;+i) if(Ri.keyRi-1.key) / 需將ai插入有序子表 R0.key=Ri.key; / 復(fù)制為哨兵 Ri.key=Ri-1.key; for(j=i-2;R0.keyRj.key;-j) Rj+1.key=Rj.key; / 記錄后移 Rj+1.key=R0.key; / 插入到正確位置 void BInsertSort (RecType R,int low,int high,int length) int m; for ( int i=2; i=length; +i ) R0.key = Ri.key; / 將Ri暫存到R0 low = 1; high = i-1; while ( low = high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0.key =high+1; -j ) Rj+1.key = Rj.key; / 記錄后移 Rhigh+1.key = R0.key; / 插入 / BInsertSortvoid ShellSort(RecType R,int n)/*希爾排序算法*/int i,j,d,k;RecType temp;d=n/2;/*d取初值n/2*/while (d0) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /*Rj與Rj+d交換*/Rj=Rj+d;Rj+d=temp;j=j-d;printf( d=%d: ,d);/*輸出每一趟