直接插入排序的主要消耗在比较次数以及结点的移动。
如果想要改善直接插入排序的时间消耗，可以减少比较次数和减少结点移动次数。
二分插入排序是减少比较次数的有效手段。直接插入排序中，a[j]的插入位置是采取和a[j-1]……a[0]的逐次比较来确定，最多可能比较j次。注意到a[0]……a[j-1]已经是排好序的序列，可以通过二分查找法，更快速地确定a[j]的插入位置。
二分插入排序中，比较次数总的代价为O(NlogN)。但是移动次数并没有减少，依然是O(N^2)，没有从根本上解决问题。
直接插入排序的主要消耗在比较次数以及结点的移动。
如果想要改善直接插入排序的时间消耗，可以减少比较次数和减少结点移动次数。
二分插入排序是减少比较次数的有效手段。直接插入排序中，a[j]的插入位置是采取和a[j-1]……a[0]的逐次比较来确定，最多可能比较j次。注意到a[0]……a[j-1]已经是排好序的序列，可以通过二分查找法，更快速地确定a[j]的插入位置。
二分插入排序中，比较次数总的代价为O(NlogN)。但是移动次数并没有减少，依然是O(N^2)，没有从根本上解决问题。