《數(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 struct
{
KeyType key; // 關(guān)鍵字項(xiàng)
InfoType otherinfo; // 其它數(shù)據(jù)項(xiàng)
}RedType;
#define MAXSI
2、ZE 20 // 一個(gè)用作示例的小順序表的最大長(zhǎng)度
// 順序表類(lèi)型
typedef struct
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長(zhǎng)度
}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
對(duì)順序表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
對(duì)順序表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; // 小于插入點(diǎn)在低半?yún)^(qū)
else
low = m + 1; // 其他插入點(diǎn)在高半?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個(gè)記錄的臨時(shí)空間
d = (RedType*)malloc((*L).length*sizeof(RedType));
// 設(shè)L的第1個(gè)記錄為d中排好序的記錄(在位置[0])
d[0] = (*L).r[1];
// first、final分別
7、指示d中排好序的記錄的第1個(gè)和最后1個(gè)記錄的位置
first = final = 0;
for(i = 2; i <= (*L).length; ++i)
{
// 依次將L的第2個(gè)～最后1個(gè)記錄插入d中
if((*L).r[i].key < d[first].key)
{
/*
待插記錄小于d中最小值，插到d[first]之前(不需移動(dòng)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òng)d數(shù)
組的元素)
*/
final=final+1;
d[final]=(*L).r[i];
}
else
{
/*
待插記錄大于d中最小值，小于d中最大值，插到d的中
間(需要移動(dòng)d數(shù)組的元素)
*/
j = final++; // 移動(dòng)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
// 對(duì)順序表L作一趟希爾插入排序。本算法是和一趟直接插入排
10、序相比，
// 作了以下修改：
// 1.前后記錄位置的增量是dk,而不是1;
// 2.r[0]只是暫存單元,不是哨兵。當(dāng)j<=0時(shí),插入位置已找到。
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]對(duì)順序表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);
/*************測(cè)試直接插入排序*******************/
#if 0
printf("\n直接插入排序的過(guò)程\n");
InsertSort(&L);
printf("\n直接插入排序后:\n");
print(L);
#endif
/*************測(cè)試折半插入排序*******************/
#
14、if 0
printf("\n折半插入排序的過(guò)程\n");
BInsertSort(&L);
printf("\n折半插入排序后:\n");
print(L);
#endif
/*************測(cè)試2路插入排序*******************/
#if 0
P2_InsertSort(&L);
printf("\n2路插入排序后:\n");
print(L);
#endif
/*************測(cè)試希爾排序*******************/
#if 0
ShellSort(&L,dt,T);
15、printf("\n希爾排序后:\n");
print(L);
#endif
system("pause");
return 0;
}
/*
輸出效果：
*************測(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,
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)
請(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, 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)
請(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,
20、 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ù). . .
*/
數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 插入排序
