算法描述：

1.从第一个元素开始，该元素可以认为已经被排序；（j=0的那个元素）

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

10, 5, 2, 4, 7

5, 10, 2, 4, 7

2, 5, 10, 4, 7

2, 4, 5, 10, 7

2, 4, 5, 7, 10

3.如果元素（已排序）大于新元素，将该元素移到下一位置；(10,5 => 5,10)

4.重复步骤3，直到已经找到已排序元素小于或等于新元素的位置；

5.将新元素插入到该位置中；

6.重复步骤2。

#include<stdio.h>void insertionsort(int a[],int n){    int i,j,key;    for ( j = 1;j < n;j++)    {        key = a[j];        i = j-1;        while ( i >= 0 && a[i]>key)        {            a[i+1]=a[i];            i -= 1;        }        a[i+1]=key;    }}int main(){    int a[]={10,5,2,4,7};    insertionsort(a,5);        for ( int i = 0;i < 5;i++)        printf("%d ",a[i]);    return 0;}

View Code

插入排序，好比是洗扑克一样，我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的适当位置，例如：
排序前： [92], 77, 67, 8, 6, 84, 55, 85, 43, 67  -- 将数组分为两部分，第一个元素为一组
第 1 次排序：[77 92] 67 8 6 84 55 85 43 67     -- 将后一组的第一个元素 77 插入前一组的适当位置
第 2 次排序：[67 77 92] 8 6 84 55 85 43 67     -- 将后一组的第一个元素 67 插入前一组的适当位置
第 3 次排序：[8 67 77 92] 6 84 55 85 43 67     -- 将后一组的第一个元素 8 插入前一组的适当位置 
第 4 次排序：[6 8 67 77 92 84] 55 85 43 67      -- 将后一组的第一个元素 6 插入前一组的适当位置
第 5 次排序：[6 8 67 77 84 92 55] 85 43 67      -- 将后一组的第一个元素 84 插入前一组的适当位置
第 6 次排序：[6 8 55 67 77 84 92 85] 43 67      -- 将后一组的第一个元素 55 插入前一组的适当位置
第 7 次排序：[6 8 55 67 77 84 85 92 43] 67      -- 将后一组的第一个元素 85 插入前一组的适当位置
第 8 次排序：[6 8 43 55 67 77 84 85 92] 67      -- 将后一组的第一个元素 43 插入前一组的适当位置
第 9 次排序：[6 8 43 55 67 67 77 84 85 92]      -- 将后一组的第一个元素 67 插入前一组的适当位置

#include <stdio.h>
#define len 5
int a[len] = { 10, 5, 2, 4, 7 };
void insertion_sort(void)
{
int i, j, key;
for (j = 1; j < len; j++)
{
printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]);
key = a[j];
i = j - 1;
while (i >= 0 && a[i] > key)
{
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]);
}

int main()
{
insertion_sort();
return 0;
}

#include <stdio.h>
#define len 5
int a[len] = { 10, 5, 2, 4, 7 };
void insertion_sort(void)
{
int i, j, key;
for (j = 1; j < len; j++)
{

key = a[j];
i = j - 1;
while (i >= 0 && a[i] > key)
{
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]);
}

int main()
{
insertion_sort();
return 0;
}

#include <stdio.h>
#define len 5
int a[len] = { 10, 5, 2, 4, 7 };
void insertion_sort(void)
{
int i, j, key;
for (j = 1; j < len; j++)
{
key = a[j];
i = j - 1;
while (i >= 0 && a[i] > key)
{
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
}

int main()
{
insertion_sort();

printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]);
return 0;
}