间接插入排序
思维：当插入第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;
}
}