思想：每次将一个待排序的数据按照大小插入到前面已经排好序的适当位置，直到全部数据插入完成为止。
图解：有哨兵的情况
代码：
//直接插入排序（不带哨兵）
void insertsort(int A[], int n) {//排序49,38,65,97,76,13,27,49
int i, j, temp;
for (i = 1; i < n; i++) //从第二个元素开始与第一个元素比较，一直比到第n个元素(下标为n-1)
if (A[i] < A[i - 1]) {
temp = A[i];//后面的元素小于前面的元素，将后一个元素提出来赋给temp
for (j = i - 1; j >= 0 && A[j] > temp; j--)//从后往前找插入位置
A[j + 1] = A[j];//使用for循环将大于temp前面的元素依次往后挪
A[j + 1] = temp;
//临界情况是挪完数后，j--,j目前指向第一个大于temp的数，这时把temp给j后面的一个元素，刚好是一个空位
}
}
//直接插入排序（带哨兵）
void insertsort(int A[], int n) {
int i, j;
for(i=2;i<=n;i++)//第二个元素下标为2，第n个元素下表为n,要加等于号
if (A[i] < A[i - 1]) {
A[0] = A[i];//若A[i]的值小于前驱，把它放到A[0]位置
for (j = i - 1; A[j] > A[0]; j--) {//把大于A[0]的值的元素往后挪
A[j + 1] = A[j];
A[j + 1] = A[0];//复制到插入位置
}
}
}
哨兵的优点是不用每轮循环都判断j大于等于0。。
