二分插入排序

直接插入排序時后面的元素從后向前逐個比較尋找插入位置，有時候沒有必要這樣做，因為此時需要尋找合適插入位置的當前這個元素前面的子序列已經有序，如果使用二分查找插入位置往往可以減少平均搜索長度。對于一個待排序的隨機序列而言，用二分插入排序取代直接插入排序，盡管總的移動元素次數不可能減少，但是可能減少總的平均比較次數。二分插入排序的平均時間復雜度為O(n²)，最壞情況下的時間復雜度為(n²)，當待排序序列已經有序時，排序時間復雜度為O(nlogn)。空間復雜度為O(1)。二分插入排序是否穩定依賴于具體實現。

假設一個序列已經有序，此時我們需要向這個序列里插入一個新的值，那么我們如何找到合適的位置呢？

首先跟序列最中間的那個元素比較，如果比最中間的這個元素小，則插入位置在它的左邊，否則在它的右邊。以當前最中間位置為分割點，如果在左邊，則當前最中間位置是待搜索子序列的終點，如果在右邊，右邊鄰接的元素將是待搜索子序列的起點。按照這種原則，繼續尋找下一個中間位置，并繼續這種過程，直到找到合適的插入位置為止。

問題是何謂合適的插入位置？如果序列中有一個元素與當前待插入的元素值相等，那么插入位置應該選在該元素的前面還是后面呢？選在后面則二分插入排序穩定，選在前面則二分插入排序不穩定。如果序列中有多個元素與當前待插入的元素值相等，插入位置選在哪里呢？選在最后一個的后面則二分插入排序穩定，其它情況均不穩定。這里的“前面”位置和“后面”位置通常被稱為上界和下界。

還有，對數組二分插入排序比較簡單，那么能對鏈表進行二分插入排序嗎？理論上沒有什么問題，如果希望代碼復用程度高的話，鏈表需要提供迭代器。問題關鍵不在于代碼復用性怎么樣，而是插入排序的速度太慢，一般不采納。

使用二分插入排序對一個無序序列排序的場合極其罕見，因為太多的時候讓一個靜態序列有序則有更快的排序算法可以選用，當一個序列很短時，直接插入排序由于開銷小比二分插入排序要快一點，當待排序序列較長時有很多排序算法(本文后面會介紹一些)均比二分插入排序快得多。