折半插入排序比較次數時間複雜度

折半插入排序比較次數時間複雜度

折半插入排序 — 插入第N個數時比較次數時間複雜度O(nlog2（n）)：

根據算法思想有以下的推論：

每個數插入最多走了一個判定樹的深度

即log2（n-1）（取最少正整數）+1

解析：在有序數組中插入的數每次比較都是與Mid(Mid指向待比較數組中的中間位置)所指向的數進行對比，先将有序數組轉化成類似判定樹的二叉樹形式，可以得出比較的次數最多隻能是這一棵二叉樹的深度。

示例：

假設一組有序數組：1 2 3 4 5 6 7 8 9 （注意已經選過的Mid不再重選）

第一次Mid:
low=1,high=9,是以Mid=(low+high)/2=5
        建立二叉樹的根
             ⑤
           

第二次Mid:
在5的左邊low=1 high=4 Mid=(low+high)/2=2
在5的右邊low=6 high=9 Mid=(low+high)/2=7
         繼續擴充二叉樹
             ⑤
          ②     ⑦
           

第三次Mid:
在2的左邊low=1 high=1 Mid=(low+high)/2=1
在2的右邊low=3 high=4 Mid=(low+high)/2=3
在7的左邊low=6 high=6 Mid=(low+high)/2=6
在7的右邊low=8 high=9 Mid=(low+high)/2=8
         繼續擴充二叉樹
             ⑤
        ②         ⑦
    ①     ③    ⑥      ⑧
           

第四次Mid:
在3的右邊low=4 high=4 Mid=(low+high)/2=4
在8的右邊low=9 high=9 Mid=(low+high)/2=9
        繼續擴充二叉樹
            ⑤
     ②            ⑦
  ①     ③      ⑥     ⑧
          ④            ⑨
           

一直到有序數組的全部元素都有這時候就轉化完成

（任何的有序數組都能用這一方法轉化為二叉樹）

當插入一個10時：（直到沒有數和它比較時候就比較完畢，小左大右）
         ⑤        （先與5進行第一次比較，大于5再5的右邊比較）
    ②        ⑦    （與7進行第二次比較，大于7再7的右邊比較）
  ①   ③    ⑥   ⑧  （與8進行第三次比較，大于8再8的右邊較）
       ④        ⑨（與9進行第四次比較，大于9再9的右邊較，9沒有右孩子不用再比較，比較完畢）

比較次數為4次 
根據公式可得log2（10-1）（取最少正整數）+1=3+1=4
           

可以看出，在插入第N個數進入一個有序的數組時，這時有序數組已經存在了N-1個數，并且比較的次數最多也隻能是由有序數組已經存在的N-1個數所轉化成的二叉樹深度。

即log2（N-1）（取最少正整數）+1

具有n個結點的完全二叉樹的深度為「log2n」+1

是以比較次數N<=log2（n-1）（取最少正整數）+1
      n-1
令i=n, ∑ =log2(1)+1+log2(2)+1+....+log2(n-1)+1
      i=1
=log2[（n-1)！]+n
當n很大時log2[（n-1)！]≈log2（n！）
在計算機内為了友善計算log2（n！）≈n*log2（n）
log2（n！）與n*log2（n）同為一個數量級
           

可得比較次數的總時間複雜度為O(nlog2（n）)

第一次寫文章，未必正确，如有錯誤請指出，小弟一定更改。