一.直接插入排序（Straight Insertion Sort）
排序的过程如下：给定无需序列：（3，6，9，7，1，8，2，4）
① 3，6，9，7，1，8，2，4 （将6插入到有序序列3中）
② 3，6，9，7，1，8，2，4 （将9插入到有序序列3，6中）
③ 3，6，9，7，1，8，2，4 （将7插入到有序序列3，6，9中）
④ 3，6，7，9，1，8，2，4 （将1插入到有序序列3，6，7，9中）
⑤ 1，3，6，7，9，8，2，4 （将8插入到有序序列1，3，6，7，9中）
⑥ 1，3，6，7，8，9，2，4 （将2插入到有序序列1，3，6，7，8，9中）
⑦ 1，2，3，6，7，8，9，4 （将4插入到有序序列1，2，3，6，7，8，9中）
⑧ 1，2，3，4，6，7，8，9 (排序成功)
#include<stdio.h>
#define M 100
int R[M]; void insertSort(int n)
{
int i,j;
for (i=;i<=n;i++)
{
if (R[i]<R[i-])
{
R[]=R[i];
j=i-;
do
{
R[j+]=R[j];
j--; }
while (R[]<R[j]);
}
R[j+]=R[];
}
}
int main()
{
int i,n; scanf("%d",&n);
for (i=;i<=n;i++)
{
scanf("%d",&R[i]);
} printf("before sort numbers \n"); for (i=;i<=n;i++)
{
printf("%4d",R[i]);
} insertSort(n);/*调用直接插入了排序*/
printf("\n after sort numbers \n");
for (i=;i<=n;i++)
{
printf("%4d",R[i]);
} }
#include<stdio.h>
#define M 100
int R[M]; void insertSort(int n)
{
int i,j;
for (i=;i<=n;i++)
{ if(R[i]<R[i-]) { R[]=R[i]; for(j=i-;R[]<R[j];--j) R[j+]=R[j]; R[j+]=R[]; } }
}
int main()
{
int i,n; scanf("%d",&n);
for (i=;i<=n;i++)
{
scanf("%d",&R[i]);
} printf("before sort numbers \n"); for (i=;i<=n;i++)
{
printf("%4d",R[i]);
} insertSort(n);/*调用直接插入了排序*/
printf("\n after sort numbers \n");
for (i=;i<=n;i++)
{
printf("%4d",R[i]);
} }
二，直接插入排序（ straight insertion sort ）是一种最简单的排序方法。它的基本操作是将一个记录插入到一个长度为 m （假设）的有序表中，使之仍保持有序，从而得到一个新的长度为 m ＋ 1 的有序表。
此算法外循环 n-1 次，在一般情况下内循环平均比较次数的数量级为Ｏ(n) ，所以算法总时间复杂度为Ｏ(n2) 。
插入排序的过程中比较的过程就是一个查找的过程，为了更加快速的找到“合适的位置”，可以使用高效些的查找算法，例如和折半查找结合，就形成了 折半插入排序。