【数据结构】插入排序_void insertsort(sqlist *l) { for(i=2; i<=l->length

数据结构中的插入排序

参考代码如下：

/*
	名称：插入排序 
	语言：数据结构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