直接插入排序：
输入： n 个数{ a1 , a2 , a3 , a4 , ……，aN }。
输出: 输入序列的一个排列（即重新排列）{ a'1 , a'2 , a'3 ,……, a'N }，使得 a'1≤a'2≤a'3≤……≤a'N。
首先，插入排序的工作机理与很多人打牌时，整理手中牌时的做法差不多。在开始摸牌时，我们的左手是空的，
牌面朝下放在桌上。接着，依次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张
牌的正确位置，要将它与手中已有的每一张从左到右地进行比较，如图 所示，无论什么时候，左手中的牌
都是排好序的，而这些牌都是原先在桌上那副牌里最先被拿起的最顶上面的一些牌。
由此看出，一趟直接插入排序的算法思想是: 每次将无序区的第一个记录按关键字插入到有序区的合适位置，并将有序区长度加1。
假如记录个数为8，输入关键字序列为（56，68，25，45，90，38，10，72），每次插入后的结果见下图。图中带括号“ [ ” " ] "的序列部分为妃递减序列，其余部分为
无序区。8 个记录的排序，经过 7 趟直接插入排序即可完成。
由图可见，第 i 趟插入排序若需将记录 a[i + 1] 插入到有序区 a[ 1.2...i] 中，插入前应先执行以下两步：
查找插入位置。从有序序列的位置 1 到 i ，依次判断是否为记录 a[ i + 1] 的插入位置 j，代码为：
j = 0; do { j++; } while(a[j] < a[i+1]);
2.移动记录空出插入位置。将有序区中从位置 i 到 j 的记录依次向后移动一个位置，空出插入位置 j ，代码为：
key = a[i + 1];//先将记录a[i + 1]保存在空闲的 0 号单元
k = i+1; do{ k--; a[k+1] = a[k];}while( k > j);
若将判断插入位置的次序改为 i 到 1，则上述两步的代码合并为
key = a[i+1]; j = i+1;
do{ j--; a[j+1] = a[j];
}while( j > 1; && key < a[j -1];)
具体代码（C语言）：
#include<stdio.h>
int main()
{
int i,j,key;
int a[10];
printf("input 10 numberd :
"); //输入
for(i = 0;i < 10; i++) //数组
scanf("%d",&a[i]);
printf("
");
for(i = 0; i < 10; i++)
if(a[i + 1] < a[i])//将a[i + 1]插入有序序列
{
key = a[i + 1];//先将a[i + 1]保存在关键字key中
j = i + 1;
do{
j--;
a[j + 1] = a[j];//记录后移
}while(key < a[j - 1]);//判断是否继续移动
a[j] = key; //插入
}
printf("the sorted numbers:
");
for(i = 0;i < 10; i++) //输出数组
printf("%d ",a[i]);
printf("
");
return 0;
}
输入/输出：
直接排序只需要一个记录的空间，其空间复杂度为O(1)。
最好情况下，待排记录有序，关键字比较次数为n - 1,移动记录为 0。
最坏情况下，待排记录逆序，时间复杂度为O(n2)。