采用直接插入排序算法因為記錄序列已基本有序直接插入排序比較次數少且由於少量次序不對的記錄與正確位置不遠使直接插入排序記錄移動次數也相對較少故選直接插入排序算法
各帶標號語句的頻度()n ()n ()(n+)(n)/ ()n(n)/ ()n
時間復雜度O(n⊃) 屬於直接選擇排序
將r+(即第個)後的元素向後移動並將放入r+處結果為
()使用二分法插入排序所要進行的比較次數與待排序的記錄的初始狀態無關不論待排序序列是否有序已形成的部分子序列是有序的二分法插入首先查找插入位置插入位置是判定樹查找失敗的位置失敗位置只能在判定樹的最下兩層上
()一些特殊情況下二分法插入排序要比直接插入排序要執行更多的比較例如在待排序序列已有序的情況下就是如此
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23195.html
