直接插入排序（Insertion Sort）
基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
直接插入排序图像解释
代码实现C语言版
#include<stdio.h>
void InsertSort(int R[], int n)
{
int i, j, k;
int temp;
for(i=1; i<n; i++)
{
j = i - 1;
temp = R[i];
while(j>=0 && temp < R[j])
{
R[j+1] = R[j];
j--;
}
R[j+1] = temp;
printf("the %d times:", i);
for(k=0; k<9; k++)
{
printf("%d ", R[k]);
}
printf("\n");
}
}
int main()
{
int a[9] = {9, 3, 1, 4, 2, 7, 8, 6, 5};
int i;
printf("begin\n");
printf("before:");
for(i=0; i<9; i++)
{
printf("%d ", a[i]);
}
printf("\n\n");
printf("InsertSort...\n");
InsertSort(a, 9);
printf("\nafter:");
for(i=0; i<9; i++)
{
printf("%d ", a[i]);
}
printf("\nend\n");
return 0;
}
输出结果：
插入排序C语言版输出结果
