二分插入排序
直接插入排序時(shí)后面的元素從后向前逐個(gè)比較尋找插入位置，有時(shí)候沒有必要這樣做，因?yàn)榇藭r(shí)需要尋找合適插入位置的當(dāng)前這個(gè)元素前面的子序列已經(jīng)有序，如果使用二分查找插入位置往往可以減少平均搜索長(zhǎng)度。對(duì)于一個(gè)待排序的隨機(jī)序列而言，用二分插入排序取代直接插入排序，盡管總的移動(dòng)元素次數(shù)不可能減少，但是可能減少總的平均比較次數(shù)。二分插入排序的平均時(shí)間復(fù)雜度為O(n2)，最壞情況下的時(shí)間復(fù)雜度為(n2)，當(dāng)待排序序列已經(jīng)有序時(shí)，排序時(shí)間復(fù)雜度為O(nlogn)。空間復(fù)雜度為O(1)。二分插入排序是否穩(wěn)定依賴于具體實(shí)現(xiàn)。
假設(shè)一個(gè)序列已經(jīng)有序，此時(shí)我們需要向這個(gè)序列里插入一個(gè)新的值，那么我們?nèi)绾握业胶线m的位置呢？
首先跟序列最中間的那個(gè)元素比較，如果比最中間的這個(gè)元素小，則插入位置在它的左邊，否則在它的右邊。以當(dāng)前最中間位置為分割點(diǎn)，如果在左邊，則當(dāng)前最中間位置是待搜索子序列的終點(diǎn)，如果在右邊，右邊鄰接的元素將是待搜索子序列的起點(diǎn)。按照這種原則，繼續(xù)尋找下一個(gè)中間位置，并繼續(xù)這種過程，直到找到合適的插入位置為止。
問題是何謂合適的插入位置？如果序列中有一個(gè)元素與當(dāng)前待插入的元素值相等，那么插入位置應(yīng)該選在該元素的前面還是后面呢？選在后面則二分插入排序穩(wěn)定，選在前面則二分插入排序不穩(wěn)定。如果序列中有多個(gè)元素與當(dāng)前待插入的元素值相等，插入位置選在哪里呢？選在最后一個(gè)的后面則二分插入排序穩(wěn)定，其它情況均不穩(wěn)定。這里的“前面”位置和“后面”位置通常被稱為上界和下界。
還有，對(duì)數(shù)組二分插入排序比較簡(jiǎn)單，那么能對(duì)鏈表進(jìn)行二分插入排序嗎？理論上沒有什么問題，如果希望代碼復(fù)用程度高的話，鏈表需要提供迭代器。問題關(guān)鍵不在于代碼復(fù)用性怎么樣，而是插入排序的速度太慢，一般不采納。
使用二分插入排序?qū)σ粋€(gè)無序序列排序的場(chǎng)合極其罕見，因?yàn)樘嗟臅r(shí)候讓一個(gè)靜態(tài)序列有序則有更快的排序算法可以選用，當(dāng)一個(gè)序列很短時(shí)，直接插入排序由于開銷小比二分插入排序要快一點(diǎn)，當(dāng)待排序序列較長(zhǎng)時(shí)有很多排序算法(本文后面會(huì)介紹一些)均比二分插入排序快得多。
1 template <typename RandomIter, typename T, typename Compare>
2 inline void linear_binary_insertion(RandomIter first, RandomIter
3 last, T value, Compare cmp)
4 {
5 RandomIter curr = upper_bound(first, last, value, cmp); // 見本主頁的原地歸并排序介紹
6 copy_backward(curr, last, last + 1); // 暫且需要用標(biāo)準(zhǔn)庫(kù)，將來也許添加該部分的代碼
7 *curr = value;
8 }
9
10 template <typename RandomIter, typename Compare>
11 void binary_insertion_sort(RandomIter first, RandomIter last, Compare cmp)
12 {
13 if(last - first < 2)
14 return;
15 for(RandomIter it = first + 1; it != last; ++it)
16 linear_binary_insertion(first, it, *it, cmp);
17 }