9.6.1　插入排序

排序思想：把待排序的元素按其值的大小逐个插入到一个已经排好序的序列中，直到所有的元素插入完为止。

排序过程，如图9-39所示：

图9-39　插入排序

二分插入排序

将直接插入排序中寻找a［i］插入位置的方法改为二分查找，然后再一次性向右移动元素。

二分插入排序减少了比较次数，特别是当要排序的数据很大时，这个效果将更加明显。