排序 - 插入排序 - 直接插入排序（二）

　　哨兵的作用

　　算法中引進的附加記錄R[]稱監視哨或哨兵(Sentinel)

　　哨兵有兩個作用

　　① 進人查找(插入位置)循環之前它保存了R[i]的副本使不致於因記錄後移而丟失R[i]的內容;

　　② 它的主要作用是在查找循環中監視下標變量j是否越界一旦越界(即j=)因為R[]key和自己比較循環判定條件

　　不成立使得查找循環結束從而避免了在該循環內的每一次均要檢測j是否越界(即省略了循環判定條件j>=)

　　注意

　　① 實際上一切為簡化邊界條件而引入的附加結點(元素)均可稱為哨兵

　　【例】單鏈表中的頭結點實際上是一個哨兵

　　② 引入哨兵後使得測試查找循環條件的時間大約減少了一半所以對於記錄數較大的文件節約的時間就相當可觀對於類似於

　　排序這樣使用頻率非常高的算法要盡可能地減少其運行時間所以不能把上述算法中的哨兵視為雕蟲小技而應該深刻理解並掌握

　　這種技巧

　　給定輸入實例的排序過程

　　設待排序的文件有個記錄其關鍵字分別為 為了區別兩個相同的關鍵字後一個

　　的下方加了一下劃線以示區別其排序過程見【 動畫模擬演示 】

　　算法分析

　　算法的時間性能分析

　　對於具有n個記錄的文件要進行n趟排序

　　各種狀態下的時間復雜度

　　

　　注意

　　初始文件按關鍵字遞增有序簡稱正序

　　初始文件按關鍵字遞減有序簡稱反序

　　算法的空間復雜度分析

　　算法所需的輔助空間是一個監視哨輔助空間復雜度S(n)=O()是一個就地排序

　　直接插入排序的穩定性

　　直接插入排序是穩定的排序方法

From:http://tw.wingwit.com/Article/program/sjjg/201311/23806.html