算法描述：
假定n是数组的长度，
首先假设第一个元素被放置在正确的位置上，这样仅需从1到n-1范围内对剩余元素进行排序。对于每次遍历，从0到i-1范围内的数组元素已经被排好序，每次遍历的任务是：通过扫描前面已排序的子列表，将位置i处的元素定位到从0到i的子列表之内的正确的位置上。将arr[i]复制为一个名为target的临时元素。向下扫描列表，比较这个目标值target与arr[i-1]、arr[i-2]的大小，依次类推。这个比较过程在小于或等于目标值的第一个元素(arr[j])处停止，或者在列表开始处停止（j=0）。在arr[i]小于前面任何已排序元素时，后一个条件（j=0）为真，因此，这个元素会占用新排序子列表的第一个位置。在扫描期间，大于目标值target的每个元素都会向右滑动一个位置（arr[j]=arr[j-1]）。一旦确定了正确位置j，
目标值target（即原始的arr[i]）就会被复制到这个位置。与选择排序不同的是，插入排序将数据向右滑动，并且不会执行交换。
代码实现(java)：
public class InsertSort {
public void sort(int [] a){
for(int i=1;i<a.length;i++)
{
int target = a[i];
int j=i-1;
for( ; j>=0&&target<a[j];j--)
{
a[j+1] = a[j];
}
a[j+1] = target;
}
}
}
利用插入排序的思想可以解决数组中的奇数与偶数顺序的调整（调整数组顺序使奇数位于偶数前面，调整后奇数与偶数相对位置不变）等问题。
原文：http://www.cnblogs.com/lizhonghai0209/p/5058293.html