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

#include <stdio.h>#include <malloc.h>/*數(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ù)項(xiàng)的類型/ 記錄類型typedef structKeyType key;/ 關(guān)鍵字項(xiàng)InfoType otherinfo;/ 其它數(shù)據(jù)項(xiàng)RedType;#define MAXSIZE 20/ 一個(gè)用作示例的小順序表的最大長(zhǎng)度/ 順序表類型typedef structRedType 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; +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 = (*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路插入排序 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;/ 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 < 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的尾部元素以便按序插入記錄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í),插入位置已找到。 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 P272/ 按增量序列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 = 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直接插入排序的過程n");InsertSort(&L);printf("n直接插入排序后:n");print(L);#endif/*測(cè)試折半插入排序*/#if 0printf("n折半插入排序的過程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, 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)請(qǐng)按任意鍵繼續(xù). . .*測(cè)試折半插入排序*排序前:(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)請(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) (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ù). . .*/