时间复杂度：O(N^2)； 空间复杂度：O(1) ； 稳定性：稳定
设数组a[0...N-1]
1.初始时，我们把arr[0]自认为有序区，无序区为arr[1...N-1]，令i=1 。 2.将arr[i]插入到arr[0...i-1]的有序区中，无序区元素依次向后移，形成arr[0...i]的有序区。 3.i++，重复第二部操作，知道i=N-1为止。
有此思路可以写出代码（从小到大排）
void InsertSort1(int arr[], int n)
{
int i,j,k,temp;
for(i = 1; i < n; i++)
{
//为arr[i]在有序区arr[0...i-1]找到一个合适的插入位置
for(j = i -1; j>=0; j--)
{
if(arr[j] < arr[i])
break;
}
//已找到合适插入位
if(j != i-1)
{
temp = arr[i];
//插入位后面元素依次往后移
for(k = i-1; k>j; k--)
{
arr[k+1] = arr[k];
}
//arr[i]插入合适的位置
arr[k+1] = temp;
}
}
}
不过很容易看出，代码不简洁，我们是找出了插入位，然后再回过头来进行移动，感觉很麻烦。仔细想一下为什么 不在查找的过程中把移动的事给干了，反正一次移一个跟最后一起移动效果是一样的，还减少了一次for循环，而且 代码量减少并变清晰了.
void InsertSort2(int arr[], int n)
{
//i从1到n-1遍历
for(int i = 1; i < n; i++)
{
int j = i-1;
int temp = arr[i]; //将无序区的第一个元素保存
while(j>=0 && arr[j] > temp)
{//每比较一次，如果没找到插入位置
arr[j+1] = arr[j]; //元素往后移一个
j--;
}
//当找到插入位置时,以上while结束，将temp插入
arr[j+1] = temp;
}
} 这样代码就清晰多了。
直接插入排序还有一种利用“哨兵”。也就是数据元素从1到N，arr[0]用来保存a[i]，并且用来“监视”下标j是否越界 下面是运用严蔚敏老师那本数据结构书的思路写下的代码：
void InsertSort3(int arr[], int n)
{
int i, j;
//这里i就是从2开始了，因为默认a[1]为有序
for(i = 2; i
其实与第二种方法差不多。这里就不用考虑j是否大于0了，因为最后j=0，所以一定有arr[0]>=arr[j]则循环也也结束了。