數據結構C語言版 插入排序.doc

#include #include /*數據結構C語言版 插入排序 P265-P272編譯環(huán)境：VC+6.0日期：2011年2月16日 */typedef int KeyType;/ 定義關鍵字類型為整型typedef int InfoType;/ 定義其它數據項的類型/ 記錄類型typedef structKeyType key;/ 關鍵字項InfoType otherinfo;/ 其它數據項RedType;#define MAXSIZE 20/ 一個用作示例的小順序表的最大長度/ 順序表類型typedef structRedType rMAXSIZE+1;/ r0閑置或用作哨兵單元int length;/ 順序表長度SqList;/ 打印順序表 void print(SqList L)int i;for(i = 1; i = L.length; i+)printf(%d, %d) , L.ri.key, L.ri.otherinfo);printf(nn);/*算法10.1 P265對順序表L作直接插入排序。*/void InsertSort(SqList *L)int i, j;/ 升序排序 for( i = 2; i = (*L).length; +i)if(*L).ri.key (*L).ri-1.key)(*L).r0 = (*L).ri; / 復制為哨兵for(j = i-1; (*L).r0.key (*L).rj.key; -j)(*L).rj+1=(*L).rj;/ 記錄后移(*L).rj+1 = (*L).r0;/ 插入到正確位置print(*L);/ 打印線性表 /*算法10.2 P267 對順序表L作折半插入排序。 */void BInsertSort(SqList *L)int i,j,m,low,high;for(i = 2; i = (*L).length; +i)(*L).r0 = (*L).ri; / 將L.ri暫存到L.r0low = 1;high = i-1;/ 在rlow.high中折半查找有序插入的位置while(low = high)m = (low + high) / 2;/ 折半if(*L).r0.key = high+1; -j)(*L).rj+1 = (*L).rj;/ 記錄后移(*L).rhigh+1 = (*L).r0;/ 插入print(*L); / 2路插入排序 P267 void P2_InsertSort(SqList *L)int i,j,first,final;RedType *d;/ 生成L.length個記錄的臨時空間d = (RedType*)malloc(*L).length*sizeof(RedType);/ 設L的第1個記錄為d中排好序的記錄(在位置0)d0 = (*L).r1;/ first、final分別指示d中排好序的記錄的第1個和最后1個記錄的位置first = final = 0;for(i = 2; i = (*L).length; +i)/ 依次將L的第2個最后1個記錄插入d中 if(*L).ri.key dfinal.key)/*待插記錄大于d中最大值，插到dfinal之后(不需移動d數組的元素) */final=final+1;dfinal=(*L).ri;else/*待插記錄大于d中最小值，小于d中最大值，插到d的中間(需要移動d數組的元素) */j = final+;/ 移動d的尾部元素以便按序插入記錄while(*L).ri.key dj.key)d(j+1)%(*L).length = dj;j = (j-1+(*L).length) % (*L).length;dj+1 = (*L).ri;/ 把d賦給L.r, 線性關系for(i = 1;i = (*L).length; i+)(*L).ri = d(i+first-1)%(*L).length;/ 算法10.4 P272/ 對順序表L作一趟希爾插入排序。本算法是和一趟直接插入排序相比， / 作了以下修改： / 1.前后記錄位置的增量是dk,而不是1; / 2.r0只是暫存單元,不是哨兵。當j=0時,插入位置已找到。 void ShellInsert(SqList *L,int dk)int i,j;for(i=dk+1;i=(*L).length;+i)if (*L).ri.key 0&(*L).r0.key (*L).rj.key);j-=dk)(*L).rj+dk=(*L).rj; / 記錄后移，查找插入位置 (*L).rj+dk=(*L).r0; / 插入 / 算法10.5 P272/ 按增量序列dlta0.t-1對順序表L作希爾排序。void ShellSort(SqList *L,int dlta,int t)int k;for(k=0;kt;+k)ShellInsert(L,dltak); / 一趟增量為dltak的插入排序 printf(第%d趟排序結果: ,k+1);print(*L);#define N 8#define T 3int main()RedType dN = 49, 1, 38, 2, 65, 3, 97, 4, 76, 5, 13, 6, 27, 7, 49, 8;SqList L;int i;int dtT = 5, 3, 1; / 增量序列數組/ 給L.r賦值for(i = 0; i N; i+)L.ri+1=di;L.length = N;printf(排序前:n);print(L);/*測試直接插入排序*/#if 0printf(n直接插入排序的過程n);InsertSort(&L);printf(n直接插入排序后:n);print(L);#endif/*測試折半插入排序*/#if 0printf(n折半插入排序的過程n);BInsertSort(&L);printf(n折半插入排序后:n);print(L);#endif/*測試2路插入排序*/#if 0P2_InsertSort(&L);printf(n2路插入排序后:n);print(L);#endif/*測試希爾排序*/#if 0ShellSort(&L,dt,T);printf(n希爾排序后:n);print(L);#endifsystem(pause);return 0;/*輸出效果：*測試直接插入排序*排序前:(49, 1) (38, 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)直接插入排序的過程(38, 2) (49, 1) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)(38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (13, 6) (27, 7) (49, 8)(13, 6) (38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (27, 7) (49, 8)(13, 6) (27, 7) (38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (49, 8)(13, 6) (27, 7) (38, 2) (49, 1) (49, 8) (65, 3) (76, 5) (97, 4)直接插入排序后:(13, 6) (27, 7) (38, 2) (49, 1) (49, 8) (65, 3) (76, 5) (97, 4)請按任意鍵繼續(xù). . .*測試折半插入排序*排序前:(49, 1) (38, 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)折半插入排序的過程(38, 2) (49, 1) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)(38, 2) (49, 1) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)(38, 2) (49, 1) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)(38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (13, 6) (27, 7) (49, 8)(13, 6) (38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (27, 7) (49, 8)(13, 6) (27, 7) (38, 2) (49, 1) (65, 3) (76, 5) (97, 4) (49, 8)(13, 6) (27, 7) (38, 2) (49, 1) (49, 8) (65, 3) (76, 5) (97, 4)折半插入排序后:(13, 6) (27, 7) (38, 2) (49, 1) (49, 8) (65, 3) (76, 5) (97, 4)請按任意鍵繼續(xù). . .*測試2路插入排序*排序前:(49, 1) (38, 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)2路插入排序后:(13, 6) (27, 7) (38, 2) (49, 1) (49, 8) (65, 3) (76, 5) (97, 4)請按任意鍵繼續(xù). . .*測試希爾排序*排序前:(49, 1) (38, 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)第1趟排序結果: (13, 6) (27, 7) (49, 8) (97, 4) (76, 5) (49, 1) (38, 2) (65, 3)第2趟排序結果: (13