概念：
插入排序(InsertionSort)，就是将数据一个个得插入到合理的位置的排序方式。
方法：
假设有5，4，2，3，1，6，9，7，8这9个数字，需要对他们进行排序。
第一步从n=1开始，需要0，1位置的两个元素比较大小，对比4，5的大小，4小于5交换他们的顺序，此时结果为4，5，2，3，1，6，9，7，8。
第二步n=2，此时已经存在4，5两个数据，则需要与4，5都比较大小，首先与5比较大小，2小于5，交换2，5的顺序，然后再与4比较大小，2小于4再交换2，4的顺序，此时结果为2，4，5，3，1，6，9，7，8。
第三步n=3，根据步骤三，依次与5，4，2比较大小，并交换位置，此时结果为2，3，4，5，1，6，9，7，8。
以此类推，直到所有的数据都被按顺序排好。
复杂度：待补充
C代码：
#include<stdio.h>
#define MAX_ARRAY_LEN 9
void insertSort(int *array, int n)
{
int i, j, tmp;
for(i = 1; i < n; i++)
{
j = i - 1;
tmp = array[i];//当前数据
//对比小于i的数据，如果大于当前数据就将其向后移动一位,找到插入当前数据的位置
while(j >= 0 && array[j] > tmp)
{
array[j+1] = array[j];
j--;
}
array[j+1] = tmp; //保存当前值
}
}
void my_printf(int *array, int n)
{
int i;
for(i = 0; i < n; i++)
{
printf("%d", array[i]);
}
printf("\n");
}
int main(void)
{
int test_array[MAX_ARRAY_LEN] = {5, 4,2, 3, 1, 6, 9, 7, 8};
my_printf(test_array, MAX_ARRAY_LEN);
insertSort(test_array, MAX_ARRAY_LEN);
my_printf(test_array, MAX_ARRAY_LEN);
return 0;
}