二分法插入排序:二分法插入排序，簡稱二分排序，是在插入第i個元素時，對前 -百科知識中文網

算法思想簡單描述：

二分法沒有排序，只有查找。所以當找到要插入的位置時。移動必須從最後一個記錄開始，向後移動一位，再移動倒數第2位，直到要插入的位置的記錄移後一位。

二分插入排序是穩定的與二分查找的複雜度相同；

最好的情況是當插入的位置剛好是二分位置所用時間為O(log₂n);

最壞的情況是當插入的位置不在二分位置所需比較次數為O(n)，無限逼近線性查找的複雜度。

S<=∑n「log₂n「-2^n「log₂n「+1

k= 1

平均時間O(n^2)

1、二分法查找插入位置

如果R<R[m]成立，那右指針就要向左移動中間指針一位，否則，左指針要向右移動中間指針一位。反覆查找，直到左指針大於右指針時停止。

2、後移，有點迷惑，什麼時候需要後移呢？有哪些記錄需要移動呢？

雖然我們很清楚的知道，我們需要後移那些排序碼大於R的記錄，但難免會問自己這樣幾個問題。其實它相當於需要移動從i-1到左指針的記錄。

3、插入

由1中得到的左指針其實就是元素要插入的位置。