记号说明：a[k:r]是指序列a[k] a[k+1] a[k+2] … a[r]。

为了讨论简单，假设待排序的每个记录是一个整数，这个整数就是排序码。

直接插入排序：先将第一个记录看作是一个有序的记录序列，然后从第二个记录开始，依次将未排序的记录插入到这个有序的记录序列中去，直到整个文件中的全部记录排序完毕。

举例说明： 假设待排序的序列是：46,58,15,45,90,18，下面的描述中[ ]中的序列是有序序列，[ ]后面的记录是待排序的。

排序过程是：i从1到n-1执行“将a[i]插入到a[0..i-1]得到从小到大的排列a[0..i]”。

示例过程如下：

初始a[0:0]是一个有序序列：[46] 58 15 45 90 18；

将a[1]插入a[0:0]得到a[0:1]：[46 58] 15 45 90 18；

将a[2]插入a[0:1]得到a[0:2]: [15 46 58] 45 90 18；

将a[3]插入a[0:2]得到a[0:3]: [15 45 46 58] 90 18；

将a[4]插入a[0:3]得到a[0:4]：[15 45 46 58 90] 18；

将a[5]插入a[0:4]得到a[0:5]：[15 18 45 46 58 90]；

将a[i]插入到a[0:i-1]得到a[0:i]的方法是：

• 首先将a[i]放入临时变量temp：temp = a[i]；
• 然后a[i-1],a[i-2],…依次与temp比较，若大于temp，则往后移动一个位置；
• 最后一个腾出的位置放置temp的值。

详细代码

#include<stdio.h>
#include<stdlib.h>

void DirecInsSort(int* a, int n)//直接插入排序函数
{
    int i, j,temp;

    for (i = 1; i < n; i++) {//第一个数默认排序好了,而他的下标是0，所以从1开始
        if (a[i] < a[i - 1])//如果大于就直接加入，就是相当于排好了
        {
            temp = a[i];
            for (j = i - 1; j >= 0 && temp < a[j]; j--)//从已经排好的序列，从后往前检查
            {
                a[j + 1] = a[j];//往后移一个位置
            }
            a[j + 1] = temp;
        }
    }
}

void SortPrint(int* a, int n)
{
    int i;
    printf("sort result:");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
}
int main()
{
    int n;
    scanf("%d", &n);//有多少个数要排序
    int i;
    int* a = (int*)malloc(sizeof(int) * n);//申请空间，其实就是数组，但这里不同的是你可以动态创建你需要的空间，避免了空间浪费。
    //也可以直接int a[100],但注意100这个数必须比n大，
    //由于不知道n的数，所以一般会用100等大的多的数，避免空间不足，但会浪费空间，主要区别就是这个
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    DirecInsSort(a, n);
    SortPrint(a, n);
    free(a);//申请完空间，记得释放，不记得就算了
}