基本思想：取序列中的第i个元素，（在取到第i个元素之前，第i个元素前面的序列已经经过排序，成为有序序列，第i个元素及其之后的序列即为无序序列），将第i个元素与之前的有序序列中的元素依次进行比较，并将其插入到合适的位置，由此对原序列中的每一个元素进行上述操作，即可得到有序序列
因为在获取待插入元素的时候要对数组进行一次遍历，而每遍历到一个元素又要将其与之前的有序序列中的元素进行比较，又要进行一次遍历，因此最差的时间复杂度为O(N^2)，即当整个数组刚好与所要求的排序序列顺序相反；与之对应的则是最优时间复杂度为O(N)，即整个数组的序列与所要求的顺序序列一致，相当于只进行一次遍历
空间复杂度为O(1),且算法稳定性稳定（即原序列中的两个相等元素的先后次序在排序前后并不会发生改变）
而对于上面的直接插入排序算法属于边比较，边搬移元素，比较简单，很容易想通，但是效率也比较低，而最容易想到的优化方案，就是先找插入位置，在进行元素的搬移，这样一来，在找插入元素的时候由于是有序序列，可以采用二分查找来进行相应的优化
代码如下：
int BinarySearch(int arr[],int size,int data)
{
int left=0;
int right=size;
while(left<right)
{
int mid=(left&right)+((left^right)>>1);
if(arr[mid]>data)
right=mid;
else
left=mid+1;
}
return left;
}
void InsertSort(int arr[],int size)
{
assert(arr);
int i=1;
for(;i<size;i++)
{
int pos=BinarySearch(arr,i,arr[i]);
int data=arr[i];
int end=i;
while(end>pos)
{
arr[end]=arr[end-1];
end--;
}
arr[pos]=data;
}
}
这样一来，时间复杂度可以为O(NlogN)
对于插入排序而言，无论有没有加入二分查找进行优化，它都是比较适用于数据量小，而且序列接近所要的顺序的数据序列
