引言
假如在军训期间进行由高到底进行站队时，有一同学
小明有事没到，但等他到时已经排好队，教官让他找到合适的地方站进去。当小明找到第五位同学，发现没他高，于是小明站在了该同学前面，后面的同学集体向后移动
基本思想：将一个数插入到有序的数列中
基本思路
- 直接插入排序是有两层循环嵌套来实现
- 将数组中的第一个元素看作有序所以
- 外循环
i从数组的第二个元素开始一直遍历到数组最后，并把 i 指向的元素设置为哨兵 - 内循环
j从外循环减一开始往前遍历，直到j<0 - 判断 j 指向元素与哨兵的关系，若小于哨兵，就使 j 指向的元素向后移动，直到不满足跳出内
- 循环，把哨兵插入到 j 指向的位置前面
举例
有一数组a，数组中的元素如下：
第一次：外循环 i 指向 3并当作哨兵，内循环 j 指向 6
比较 j 指向的元素与哨兵的大小，发现大于哨兵的值，所以使 j 指向的元素向后移动，接着使 j– 发现 j<0 所以不满足内循环条件，跳出内循环，并把哨兵插入到 6 的后面
第二次，外循环 i 指向 7并当作哨兵，内循环 j 指向 6
比较 j 指向的元素与哨兵的大小，发现小于哨兵的值，i 指向的元素无需移到，并结束内循环
第三次：外循环 i 指向 4并当作哨兵，内循环 j 指向 7
比较 j 指向的元素与哨兵的大小，6 、 7 都比哨兵大，使 6、7 向后移动，直到 j 指向 3 满足小于哨兵，并把哨兵插入到 3 的前面
第四次：把 2 插入到 3 的后面
第五次 : 把 1 插入到 2 的后面
上述步骤即为直接插入排序
代码如下
void InsertSort(int *nums,int numsSize)
{
int i,j,tmp;
for (i=1;i<numsSize;i++)
{
tmp = nums[i];
for (j=i-1;j>=0;j--)
{
if (tmp < nums[j])
nums[j+1] = nums[j];
else
break;
}
nums[j+1] = tmp; //注意：赋值给 j+1 而不是 j
}
}