直接插入排序（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语言版输出结果