插入排序的基本思想是：对于数组前边部分已经是排好序的了，对于接下来的元素查找其在前面的位置，插入之。如下图中1 2 4 7 已经排好序，接下来找到2的位置，插入到1和3之间。之后同样处理4和9.
参考程序（C语言实现）如下：
#include<stdio.h>
void Insection_Sort(int *A, int array_size)
{
int i,j,k,tmp;
for(i=1; i<array_size; i++)
{
tmp = A[i];
j = i-1;
while(j>=0 && A[j]>tmp)
{
A[j+1] = A[j];
j--;
}
A[j+1] = tmp;
}
}
int main()
{
int A[7] = {4, 7, 1, 3}, i;
Insection_Sort(A, 4);
for(i=0; i<7; i++)
{
printf("%d ", A[i]);
}
printf("\n");
return 0;
}
排序过程中执行过程如下图：
原文：http://www.cnblogs.com/2014acm/p/3916311.html