间接插入排序
思维：当插入第 i 个元素时，后面的 i - 1 个元素曾经排好序，这时，用第 i 个元素和后面的 i - 1 个元素进行比拟，找到第 i 个元素的地位将其插入，原来地位上的元素向后顺移。
例子：
初始序列：21 25 49 25* 16 8
1 21 25 49 25* 16 8
2 21 25 49 25* 16 8
3 21 25 25* 49 16 8
4 16 21 25 25* 49 8
5 8 16 21 25 25* 49
i= 4 时间接插入排序的过程：
初始：21 25 25* 49 16 8 temp
21 25 25* 49 16 8 16
21 25 25* 49 49 8 16
21 25 25* 25* 49 8 16
21 25 25 25* 49 8 16
21 21 25 25* 49 8 16
16 21 25 25* 49 8 16
在这趟排序中，咱们能够看到 V[0] 到 V[3] 曾经排好序了，在要插入 V[4]=16 这个数时，咱们须要比拟 V[4] 与 V[3]，因为 V[4]<V[3]，须要在 V[3] 到 V[0] 之间寻找插入地位，先将 V[4]=16 找一个工作元素 temp 中暂存，以避免后面的元素把他笼罩掉。而后从前面向前顺次比拟寻找插入地位，循环变量设为 j，如果 V[j]>temp, 那么就将 V[j] 后移，直到某一个 V[j]<=temp 时或者元素序列比拟完为止。最初把暂存的 temp 的值填到第 j 个地位的后一个地位，一趟排序就完结了。
稳定性：稳固
工夫复杂度：O(n^2)
代码：
c++：
void Insert_sort(int arr[],int n) {
int i;
int j;
int temp;
for (i = 1; i < n;i++) {
temp = arr[i];
for (j = i – 1; j >= 0;j–) {
if (temp<arr[j]) {
arr[j + 1] = arr[j];// 后移比 temp 大的值
}
else
{
break;// 不须要挪动
}
}
arr[j + 1] = temp;
}
}