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

1、#include <stdio.h>#include <malloc.h>/*數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言版 插入排序 p265-p272編譯環(huán)境：vc+6.0日期：2011年2月16日 */typedef int keytype;/ 定義關(guān)鍵字類型為整型typedef int infotype;/ 定義其它數(shù)據(jù)項(xiàng)的類型/ 記錄類型typedef structkeytype key;/ 關(guān)鍵字項(xiàng)infotype otherinfo;/ 其它數(shù)據(jù)項(xiàng)redtype;#define maxsize 20/ 一個(gè)用作示例的小順序表的最大長(zhǎng)度/ 順序表類型typedef structredty

2、pe rmaxsize+1;/ r0閑置或用作哨兵單元int 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;

3、+i)if(*l).ri.key < (*l).ri-1.key)(*l).r0 = (*l).ri; / 復(fù)制為哨兵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 對(duì)順序表l作折半插入排序。 */void binsertsort(sqlist *l)int i,j,m,low,high;for(i = 2; i <= (*l).length; +i)(*l).r0 =

4、(*l).ri; / 將l.ri暫存到l.r0low = 1;high = i-1;/ 在rlow.high中折半查找有序插入的位置while(low <= high)m = (low + high) / 2;/ 折半if(*l).r0.key < (*l).rm.key)high = m-1;/ 小于插入點(diǎn)在低半?yún)^(qū)elselow = m + 1; / 其他插入點(diǎn)在高半?yún)^(qū)for(j = i-1;j >= high+1; -j)(*l).rj+1 = (*l).rj;/ 記錄后移(*l).rhigh+1 = (*l).r0;/ 插入print(*l); / 2路插入排序 p26

5、7 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;/ 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 <

6、dfirst.key)/* 待插記錄小于d中最小值，插到dfirst之前(不需移動(dòng)d數(shù)組的元素)*/first = (first - 1 + (*l).length) % (*l).length;/ 設(shè)d為循環(huán)向量dfirst = (*l).ri;else 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的尾部元素以便按序插

7、入記錄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, 線性關(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í),插

8、入位置已找到。 void shellinsert(sqlist *l,int dk)int i,j;for(i=dk+1;i<=(*l).length;+i)if (*l).ri.key < (*l).ri-dk.key)/ 需將(*l).ri插入有序增量子表 (*l).r0=(*l).ri; / 暫存在(*l).r0for(j=i-dk;j>0&&(*l).r0.key < (*l).rj.key);j-=dk)(*l).rj+dk=(*l).rj; / 記錄后移，查找插入位置 (*l).rj+dk=(*l).r0; / 插入 / 算法10.5 p27

9、2/ 按增量序列dlta0.t-1對(duì)順序表l作希爾排序。void shellsort(sqlist *l,int dlta,int t)int k;for(k=0;k<t;+k)shellinsert(l,dltak); / 一趟增量為dltak的插入排序 printf("第%d趟排序結(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

10、= 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直接插入排序后:n");print(l);#endif/*測(cè)試折半插入排序*/#if 0printf("n折半插入排序的過(guò)程n");binsertsort(&l);printf(&

11、quot;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, 2) (65, 3) (97, 4) (76, 5)

12、 (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, 4) (49, 8)(13, 6) (27, 7)

13、 (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) (49, 8)(38, 2) (49, 1) (65,

14、 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,

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