一、插入排序

依次对第i个记录进行排序，将当前无序区的第一个记录Array[i]插入到有序区Array[0..i-1]的合适位置。插入排序的关键在于如何将一个新记录ri插入到已排序部分序列R'中。而一次插入操作设计到两个方面：找到序列中应插入的位置和如何移动序列中那些已排好序的记录以便插入新记录。 
     下图对序列{45，34，78，12，34，32，29，64}进行插入排序的动画显示：