插入排序的算法思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适合位置上，直到所有待排序记录全部插入为止。
例如，打扑克牌在抓牌时，每抓一张牌，就插入到合适的位置，直到抓完牌为止，即得到一个有序序列。
可以选择不同的方法在已排好序的记录中寻找插入位置。根据查找方法的不同，有多种插入排序的方法 ，这里介绍三种方法：直接插入排序，折半插入排序和希尔排序。
一.直接插入排序直接插入排序是一种最简单的排序方法，其基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的，记录数量增1的有序表。
【算法描述】（ 伪代码）
#define MAXSIZE 20//顺序表的最大长度
typedef int KeyType;//定义关键字类型为整形
typedef struct{
KeyType key;//关键字项
InfoType otherinfo;//其他数据项
}RedType;//记录类型
typedef struct{
RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元
int length;//顺序表长度
}SqList;//顺序表类型
//升序排序
void InsertSort(SqList &L)
{//对顺序表做直接插入排序
for(i=2;i<=L.length;i++)
if(L.r[i].key
【具体代码实现】
#include
#include
#include
#include
#define MAXSIZE 30000
typedef struct
{
int key;
int compare;
}RedType;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}SqList;
long long count=0;
//-----------生成三万个随机数------------
void sjs(SqList &L)
{
srand((unsigned)time(NULL));
for(int i=1;i<=MAXSIZE;i++)
{
int a=rand()%(MAXSIZE+1);
L.r[i].key=a;
}
}
//-----插入排序算法-------
void InsertSort(SqList &L)
{
int j;
L.length =(MAXSIZE);
for(int i=2;i<=L.length ;i++)
{
if(L.r[i].key
运行结果为：
【算法分析】
（1）时间复杂度
直接插入排序的时间复杂度为O（）
（2）空间复杂度
直接插入排序只需一个记录的辅助空间r[0]，所以空间复杂度为O(1)。
【算法特点】
（1）稳定排序。
（2）算法简便，容易实现
（3）也适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针。
（4）更适用于基本有序的情况，当初始记录无序，n较大时，此算法复杂度较高，不宜采用。
二.折半插入排序
【算法描述】（伪代码）
#define MAXSIZE 20//顺序表的最大长度
typedef int KeyType;//定义关键字类型为整形
typedef struct{
KeyType key;//关键字项
InfoType otherinfo;//其他数据项
}RedType;//记录类型
typedef struct{
RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元
int length;//顺序表长度
}SqList;//顺序表类型
//升序排序
void InsertSort(SqList &L)
{//对顺序表做直接插入排序
for(i=2;i<=L.length;i++)
{
L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中
low=1;high=i-1;//置查找区间的初值
while(low<=high)
{
m=(low+high)/2;//折半
if(L.r[0].key=high+1;j--)//记录后移
L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}
}
【具体代码实现】
//折半查找排序
#include
#include
#define MAXSIZE 20
typedef struct{
int key;
//还可以添加其他数据型
}RedType;
typedef struct {
RedType r[MAXSIZE+1] ;
int length;
}SqList;
void BInsertSort(SqList &L)
{//对顺序表L做折半插入排序
for(int i=2;i=high+1;j--)
{
L.r[j+1]=L.r[j];
}
L.r[high+1]=L.r[0];
}
}
int main()
{
SqList L;
printf("输入数据的个数为：n");
scanf("%d",&L.length);
printf("请输入数据（用空格隔开）n");
for(int i=1;i<=L.length;i++)
{
scanf("%d",&L.r[i].key);
}
BInsertSort(L);
printf("排序的结果为：n");
for(int i=1;i<=L.length;i++)
{
printf("%d ",L.r[i].key);
}
}
运行结果为：
【算法分析】
（1）时间复杂度： O（）
(2) 空间复杂度：与直接插入排序相同，只需要一个记录的辅助空间，所以空间复杂度为O（1）
【算法特点】
（1）稳定排序。
（2）因为要进行折半查找，所以只能用于顺序结构，不能用于链式结构。
（3）适合初始记录无序，n较大时的情况。
三.希尔排序
希尔排序又称“缩小增量排序”，是插入排序的一种。直接插入排序，当待排序的记录个数较少且待排序序列的关键字基本有序时，效率较高。希尔排序基于以上两点，从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。但希尔排序是非稳定排序算法。
【算法步骤】
希尔排序实质上是采用分组插入的方法。其基本思想是：先将整个待排序列分割成几组，从而减少参与直接插入排序的数据量，对每组分别进行直接插入排序，然后增加每组的数据量，重新分组。这样当经过几次分组排序后，整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
举例：已知待排序的关键字序列为｛49，38，65，97，76，13，27，49，55，04｝，则用希尔排序法进行排序的过程为（增量选取5，3，1）：
【具体代码实现】
//希尔排序
#include
#include
#define MAXSIZE 20
typedef struct{
int key;
//还可以添加其他数据型
}RedType;
typedef struct {
RedType r[MAXSIZE+1] ;
int length;
}SqList;
void ShellInsert(SqList &L,int dk)
{
int j,i;
for(i=dk+1;i<=L.length;i++)
if(L.r[i].key0&& L.r[0].key
【算法分析】
（1）时间复杂度：有人在大量的试验基础上推出：当n在某一个特定范围内，希尔排序所需的比较和 移动次数约为n^1.3
(2)空间复杂度：O(1)
【算法特点】
（1）排序方法不稳定。
（2）只能用于顺序，不能用于链式。
（3）1记录总的比较次数和移动次数都比直接插入排序要少，n越大，效果越明显 。
