直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

/* 对顺序表L作直接插入排序 */

void InsertSort(SqList *L)；

直接插入排序代码：

// test.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

typedef int Status; 

#define MAXSIZE 10000  /* 用于要排序数组个数最大值，可依据须要改动 */

typedef struct

{

	int r[MAXSIZE+1];	/* 用于存储要排序数组，r[0]用作哨兵或暂时变量 */

	int length;			/* 用于记录顺序表的长度 */

}SqList;

void print(SqList L)

{

	int i;

	for(i=1;i<L.length;i++)

		printf("%d,",L.r[i]);

	printf("%d",L.r[i]);

	printf("\n");

}

/* 交换L中数组r的下标为i和j的值 */

void swap(SqList *L,int i,int j)

{

	int temp=L->r[i];

	L->r[i]=L->r[j];

	L->r[j]=temp;

}

/* 对顺序表L作直接插入排序 */

void InsertSort(SqList *L)

{

	int i,j;

	for(i=2;i<=L->length;i++)

	{

		if (L->r[i]<L->r[i-1]) /* 需将L->r[i]插入有序子表 */

		{

			L->r[0]=L->r[i]; /* 设置哨兵 */

			for(j=i-1;L->r[j]>L->r[0];j--)

				L->r[j+1]=L->r[j]; /* 记录后移 */

			L->r[j+1]=L->r[0]; /* 插入到正确位置 */

		}

	}

}

#define  N 9

int _tmain(int argc, _TCHAR* argv[])

{

	int d[N]={9,1,5,8,3,7,4,6,2};

	SqList L0;

	int i;

	for(i=0;i<N;i++)

		L0.r[i+1]=d[i];

	L0.length=N;

	printf("排序前:\n");

	print(L0);

	InsertSort(&L0);

	printf("排序后:\n");

	print(L0);

	getchar();

	return 0;

}

直接插入排序的基本思想：

首先默认第一个元素L->r[1]元素组成的序列已经有序。然后依次往这个有序表中插入数据。直到终于完毕排序。

循环控制：i=2->Length;

若当前元素L->r[i]小于有序表中最后一个元素L->r[i-1]，则进进行插入排序。否则，当前元素位置不变。有序表加1；

进入直接插入排序后：

step1:设置哨兵。令L->r[0]=L->r[i];

step2:将第一个不小于哨兵的元素至第i-1个元素依次后移一个位置（循环j=1-1,j--）；

step3:在空出的位置上插入哨兵元素，L->r[j+1]=L->r[0]; /* 插入到正确位置 */