二分插入排序

直接插入排序时后面的元素从后向前逐个比较寻找插入位置，有时候没有必要这样做，因为此时需要寻找合适插入位置的当前这个元素前面的子序列已经有序，如果使用二分查找插入位置往往可以减少平均搜索长度。对于一个待排序的随机序列而言，用二分插入排序取代直接插入排序，尽管总的移动元素次数不可能减少，但是可能减少总的平均比较次数。二分插入排序的平均时间复杂度为O(n²)，最坏情况下的时间复杂度为(n²)，当待排序序列已经有序时，排序时间复杂度为O(nlogn)。空间复杂度为O(1)。二分插入排序是否稳定依赖于具体实现。

假设一个序列已经有序，此时我们需要向这个序列里插入一个新的值，那么我们如何找到合适的位置呢？

首先跟序列最中间的那个元素比较，如果比最中间的这个元素小，则插入位置在它的左边，否则在它的右边。以当前最中间位置为分割点，如果在左边，则当前最中间位置是待搜索子序列的终点，如果在右边，右边邻接的元素将是待搜索子序列的起点。按照这种原则，继续寻找下一个中间位置，并继续这种过程，直到找到合适的插入位置为止。

问题是何谓合适的插入位置？如果序列中有一个元素与当前待插入的元素值相等，那么插入位置应该选在该元素的前面还是后面呢？选在后面则二分插入排序稳定，选在前面则二分插入排序不稳定。如果序列中有多个元素与当前待插入的元素值相等，插入位置选在哪里呢？选在最后一个的后面则二分插入排序稳定，其它情况均不稳定。这里的“前面”位置和“后面”位置通常被称为上界和下界。

还有，对数组二分插入排序比较简单，那么能对链表进行二分插入排序吗？理论上没有什么问题，如果希望代码复用程度高的话，链表需要提供迭代器。问题关键不在于代码复用性怎么样，而是插入排序的速度太慢，一般不采纳。

使用二分插入排序对一个无序序列排序的场合极其罕见，因为太多的时候让一个静态序列有序则有更快的排序算法可以选用，当一个序列很短时，直接插入排序由于开销小比二分插入排序要快一点，当待排序序列较长时有很多排序算法(本文后面会介绍一些)均比二分插入排序快得多。