《數(shù)據(jù)結(jié)構(gòu)C語言版 插入排序》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語言版 插入排序（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、#include #include /* 數(shù)據(jù)結(jié)構(gòu)C語言版 插入排序 P265-P272 編譯環(huán)境：VC++6.0 日期：2011年2月16日 */ typedef int KeyType; // 定義關(guān)鍵字類型為整型 typedef int InfoType; // 定義其它數(shù)據(jù)項的類型 　// 記錄類型 typedef struct { KeyType key; // 關(guān)鍵字項 InfoType otherinfo; // 其它數(shù)據(jù)項 }RedType; #define MAXSI

2、ZE 20 // 一個用作示例的小順序表的最大長度 // 順序表類型 typedef struct { RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元 int length; // 順序表長度 }SqList; 　 // 打印順序表 void print(SqList L) { int i; for(i = 1; i <= L.length; i++) printf("(%d, %d) ", L.r[i].key, L.r[i].otherinfo); printf("\n\n"); } 　

3、 /* 算法10.1 P265 對順序表L作直接插入排序。 */ void InsertSort(SqList *L) { int i, j; // 升序排序 for( i = 2; i <= (*L).length; ++i) if((*L).r[i].key < (*L).r[i-1].key) { 　 (*L).r[0] = (*L).r[i]; // 復(fù)制為哨兵 for(j = i-1; (*L).r[0].key < (*L).r[j].key; --j) (*L).r[j+1]=(*L).r[j];

4、 // 記錄后移 (*L).r[j+1] = (*L).r[0]; // 插入到正確位置 print(*L); // 打印線性表 } } /* 算法10.2 P267 對順序表L作折半插入排序。 */ 　void BInsertSort(SqList *L) { int i,j,m,low,high; for(i = 2; i <= (*L).length; ++i) { (*L).r[0] = (*L).r[i]; // 將L.r[i]暫存到L.r[0] low = 1; high =

5、i-1; // 在r[low..high]中折半查找有序插入的位置 while(low <= high) { m = (low + high) / 2; // 折半 if((*L).r[0].key < (*L).r[m].key) high = m-1; // 小于插入點在低半?yún)^(qū) else low = m + 1; // 其他插入點在高半?yún)^(qū) 　 } for(j = i-1;j >= high+1; --j) (*L).r[j+1] = (*L).r[j]; // 記錄后移 (*L)

6、.r[high+1] = (*L).r[0]; // 插入 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)); // 設(shè)L的第1個記錄為d中排好序的記錄(在位置[0]) d[0] = (*L).r[1]; // first、final分別

7、指示d中排好序的記錄的第1個和最后1個記錄的位置 first = final = 0; 　 for(i = 2; i <= (*L).length; ++i) { // 依次將L的第2個～最后1個記錄插入d中 if((*L).r[i].key < d[first].key) { /* 待插記錄小于d中最小值，插到d[first]之前(不需移動d數(shù) 組的元素) */ first = (first - 1 + (*L).length) % (*L).length; // 設(shè)d為循環(huán)向量 d[first]

8、 = (*L).r[i]; } else if((*L).r[i].key > d[final].key) { /* 待插記錄大于d中最大值，插到d[final]之后(不需移動d數(shù) 組的元素) 　 */ final=final+1; d[final]=(*L).r[i]; } else { /* 待插記錄大于d中最小值，小于d中最大值，插到d的中 間(需要移動d數(shù)組的元素) */ 　 j = final++; // 移動d的尾部元素以便按序插入記錄 whi

9、le((*L).r[i].key < d[j].key) { d[(j+1)%(*L).length] = d[j]; j = (j-1+(*L).length) % (*L).length; } d[j+1] = (*L).r[i]; } } // 把d賦給L.r, 線性關(guān)系 for(i = 1;i <= (*L).length; i++) (*L).r[i] = d[(i+first-1)%(*L).length]; } 　 // 算法10.4 P272 // 對順序表L作一趟希爾插入排序。本算法是和一趟直接插入排

10、序相比， // 作了以下修改： // 1.前后記錄位置的增量是dk,而不是1; // 2.r[0]只是暫存單元,不是哨兵。當(dāng)j<=0時,插入位置已找到。 void ShellInsert(SqList *L,int dk) { int i,j; for(i=dk+1;i<=(*L).length;++i) if ((*L).r[i].key < (*L).r[i-dk].key) { // 需將(*L).r[i]插入有序增量子表 (*L).r[0]=(*L).r[i]; // 暫存在(*L).r[0] for(j=

11、i-dk;j>0&&((*L).r[0].key < (*L).r[j].key);j-=dk) (*L).r[j+dk]=(*L).r[j]; // 記錄后移，查找插入位置 　 (*L).r[j+dk]=(*L).r[0]; // 插入 } } // 算法10.5 P272 // 按增量序列dlta[0..t-1]對順序表L作希爾排序。 void ShellSort(SqList *L,int dlta[],int t) { int k; for(k=0;k

12、]); // 一趟增量為dlta[k]的插入排序 printf("第%d趟排序結(jié)果: ",k+1); print(*L); } 　} #define N 8 #define T 3 int main() { RedType d[N] = { { 49, 1}, { 38, 2}, { 65, 3}, { 97, 4}, { 76, 5}, { 13, 6}, { 27, 7}, { 49, 8} }; SqList L; int i; int dt[T] = { 5, 3, 1}; // 增量序列數(shù)組 // 給

13、L.r賦值 　 for(i = 0; i < N; i++) L.r[i+1]=d[i]; L.length = N; printf("排序前:\n"); print(L); /*************測試直接插入排序*******************/ #if 0 printf("\n直接插入排序的過程\n"); InsertSort(&L); printf("\n直接插入排序后:\n"); 　 print(L); #endif /*************測試折半插入排序*******************/ #

14、if 0 printf("\n折半插入排序的過程\n"); BInsertSort(&L); printf("\n折半插入排序后:\n"); print(L); 　#endif /*************測試2路插入排序*******************/ #if 0 P2_InsertSort(&L); printf("\n2路插入排序后:\n"); print(L); #endif /*************測試希爾排序*******************/ #if 0 ShellSort(&L,dt,T);

15、printf("\n希爾排序后:\n"); 　 print(L); #endif system("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,

16、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)

17、(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) (

18、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

19、) (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,

20、 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趟排序結(jié)果: (13, 6) (27, 7) (49, 8) (97, 4) (76, 5) (49, 1) (38, 2) (65, 3) 第2趟排序結(jié)果: (13, 6) (27, 7) (49, 8) (38, 2) (65, 3) (49, 1) (97, 4) (76, 5) 　第3趟排序結(jié)果: (13, 6) (27, 7) (38, 2) (49, 8) (49, 1) (65, 3) (76, 5) (97, 4) 希爾排序后: (13, 6) (27, 7) (38, 2) (49, 8) (49, 1) (65, 3) (76, 5) (97, 4) 請按任意鍵繼續(xù). . . 　*/