插入排序就简单了，类似于打扑克，我们搬到的牌会把它插入到之前已经拍好序的牌堆中，过程如下：
代码直接上：
void insertSort(int a[],int length){
for(int j = 1;j <= length-1;++j){
int key = a[j];
int i = j - 1;
while(i >= 0 && a[i] > key){
a[i+1] = a[i];
--i;
}
a[i+1] =key;
}
}插入排序最佳情况是数组已经排好序啦；最坏情况当然是数组逆序了。最坏情况下插入排序的代价是O(n^2)。原文：http://blog.csdn.net/yu_sun90/article/details/38904721