【数据结构】插入排序

数据结构中的插入排序

参考代码如下：

/*
	名称：插入排序 
	语言：数据结构C语言版 
	编译环境：VC++ 6.0
	日期： 2014-3-26 
*/
#include <stdio.h>
#include <malloc.h>
#include <windows.h>


typedef int KeyType;	// 定义关键字类型为整型
typedef int InfoType;	// 定义其它数据项的类型

// 记录类型
typedef struct
{
	KeyType key;		// 关键字项
	InfoType otherinfo;	// 其它数据项
}RedType;

#define MAXSIZE 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");
}

/*	
	对顺序表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]; // 复制为哨兵
			
			for(j = i-1; (*L).r[0].key < (*L).r[j].key; --j)
				(*L).r[j+1]=(*L).r[j];	// 记录后移
			
			(*L).r[j+1] = (*L).r[0];	// 插入到正确位置
			
			print(*L);	// 打印线性表 
		}
}

/*
	对顺序表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 = i-1;
		
		// 在r[low..high]中折半查找有序插入的位置
		while(low <= high)
		{
			m = (low + high) / 2;	// 折半
			if((*L).r[0].key < (*L).r[m].key)
				high = m-1;	// 小于插入点在低半区
			else
				low = m + 1; 	// 其他插入点在高半区
		
		}
		for(j = i-1;j >= high+1; --j)
			(*L).r[j+1] = (*L).r[j];	// 记录后移
		
		(*L).r[high+1] = (*L).r[0];		// 插入
		
		print(*L); 
	}
}

void P2_InsertSort(SqList *L)
{
	int i,j,first,final;
	RedType *d;

	// 生成L.length个记录的临时空间
	d = (RedType*)malloc((*L).length*sizeof(RedType));

	// 设L的第1个记录为d中排好序的记录(在位置[0])
	d[0] = (*L).r[1];

	// first、final分别指示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数
				组的元素)
			*/
			first = (first - 1 + (*L).length) % (*L).length;
			// 设d为循环向量
			d[first] = (*L).r[i];
		}
		else if((*L).r[i].key > d[final].key)
		{
			/*
				待插记录大于d中最大值，插到d[final]之后(不需移动d数
				组的元素) 
			*/
			final=final+1;
			d[final]=(*L).r[i];
		}
		else
		{
			/*
				待插记录大于d中最小值，小于d中最大值，插到d的中
				间(需要移动d数组的元素) 
			*/
			j = final++;	// 移动d的尾部元素以便按序插入记录
			while((*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, 线性关系
	for(i = 1;i <= (*L).length; i++)
		(*L).r[i] = d[(i+first-1)%(*L).length];
}

// 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比， 
// 作了以下修改： 
// 1.前后记录位置的增量是dk,而不是1; 
// 2.r[0]只是暂存单元,不是哨兵。当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=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]; // 插入 
			}
}

// 按增量序列dlta[0..t-1]对顺序表L作希尔排序。
void ShellSort(SqList *L,int dlta[],int t)
{
	int k;
	for(k=0;k<t;++k)
	{
		ShellInsert(L,dlta[k]); // 一趟增量为dlta[k]的插入排序 
		printf("第%d趟排序结果: ",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}; // 增量序列数组

	// 给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


/*************测试折半插入排序*******************/
#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);

	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, 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)

请按任意键继续. . .


*************测试折半插入排序*******************

排序前:
(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)

请按任意键继续. . .


*************测试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)

请按任意键继续. . .


*************测试希尔排序*******************


排序前:
(49, 1) (38, 2) (65, 3) (97, 4) (76, 5) (13, 6) (27, 7) (49, 8)

第1趟排序结果: (13, 6) (27, 7) (49, 8) (97, 4) (76, 5) (49, 1) (38, 2) (65, 3)

第2趟排序结果: (13, 6) (27, 7) (49, 8) (38, 2) (65, 3) (49, 1) (97, 4) (76, 5)

第3趟排序结果: (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)

请按任意键继续. . .


*/