數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 插入排序

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

1、#include #include /*數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 插入排序 P265-P272編譯環(huán)境：VC+6.0日期：2011年2月16日 */typedef int KeyType;/ 定義關(guān)鍵字類(lèi)型為整型typedef int InfoType;/ 定義其它數(shù)據(jù)項(xiàng)的類(lèi)型/ 記錄類(lèi)型typedef structKeyType key;/ 關(guān)鍵字項(xiàng)InfoType otherinfo;/ 其它數(shù)據(jù)項(xiàng)RedType;#define MAXSIZE 20/ 一個(gè)用作示例的小順序表的最大長(zhǎng)度/ 順序表類(lèi)型typedef structRedType rMAXSIZE+1;/ r0閑置或用作哨兵單元int

2、length;/ 順序表長(zhǎng)度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對(duì)順序表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; / 復(fù)制為哨兵for(j =

3、 i-1; (*L).r0.key (*L).rj.key; -j)(*L).rj+1=(*L).rj;/ 記錄后移(*L).rj+1 = (*L).r0;/ 插入到正確位置print(*L);/ 打印線性表 /*算法10.2 P267 對(duì)順序表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 =

4、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個(gè)記錄的臨時(shí)空間d = (RedType*)malloc(*L).length*sizeof(RedType);/ 設(shè)L的第1個(gè)記錄為d中排好序的記錄(在位置0)d0 = (*L).r1

5、;/ first、final分別指示d中排好序的記錄的第1個(gè)和最后1個(gè)記錄的位置first = final = 0;for(i = 2; i = (*L).length; +i)/ 依次將L的第2個(gè)最后1個(gè)記錄插入d中 if(*L).ri.key dfinal.key)/*待插記錄大于d中最大值，插到dfinal之后(不需移動(dòng)d數(shù)組的元素) */final=final+1;dfinal=(*L).ri;else/*待插記錄大于d中最小值，小于d中最大值，插到d的中間(需要移動(dòng)d數(shù)組的元素) */j = final+;/ 移動(dòng)d的尾部元素以便按序插入記錄while(*L).ri.key dj.k

6、ey)d(j+1)%(*L).length = dj;j = (j-1+(*L).length) % (*L).length;dj+1 = (*L).ri;/ 把d賦給L.r, 線性關(guān)系for(i = 1;i = (*L).length; i+)(*L).ri = d(i+first-1)%(*L).length;/ 算法10.4 P272/ 對(duì)順序表L作一趟希爾插入排序。本算法是和一趟直接插入排序相比， / 作了以下修改： / 1.前后記錄位置的增量是dk,而不是1; / 2.r0只是暫存單元,不是哨兵。當(dāng)j=0時(shí),插入位置已找到。 void ShellInsert(SqList *L,in

7、t 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對(duì)順序表L作希爾排序。void ShellSort(SqList *L,int dlta,int t)int k;for(k=0;kt;+k)ShellInsert(L,dltak); / 一趟增量為dltak的插入排序 printf(第%d趟排

8、序結(jié)果: ,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; / 增量序列數(shù)組/ 給L.r賦值for(i = 0; i N; i+)L.ri+1=di;L.length = N;printf(排序前:n);print(L);/*測(cè)試直接插入排序*/#if 0printf(n直接插入排序的過(guò)程n);InsertSort(&L);printf(n直接插入

9、排序后:n);print(L);#endif/*測(cè)試折半插入排序*/#if 0printf(n折半插入排序的過(guò)程n);BInsertSort(&L);printf(n折半插入排序后:n);print(L);#endif/*測(cè)試2路插入排序*/#if 0P2_InsertSort(&L);printf(n2路插入排序后:n);print(L);#endif/*測(cè)試希爾排序*/#if 0ShellSort(&L,dt,T);printf(n希爾排序后:n);print(L);#endifsystem(pause);return 0;/*輸出效果：*測(cè)試直接插入排序*排序前:(49, 1) (38,

10、 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)直接插入排序的過(guò)程(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

11、, 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)請(qǐng)按任意鍵繼續(xù). . .*測(cè)試折半插入排序*排序前:(49, 1) (38, 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)折半插入排序的過(guò)程(38, 2) (49, 1) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7)

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

13、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)請(qǐng)按任意鍵繼續(xù). . .*測(cè)試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)

14、 (76, 5) (97, 4)請(qǐng)按任意鍵繼續(xù). . .*測(cè)試希爾排序*排序前:(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)請(qǐng)按任意鍵繼續(xù). . .*/