可以做到取a與b進行比較c與d進行比較設a>bc>d(a<b和c<d情況類似)此時需次比較取b和d比較若b>d則有序a>b>d若b<d時則有序c>d>b此時已進行了次比較再把另外兩個元素按折半插入排序方法插入到上述某個序列中共需次比較從而共需次比較
本題答案之一請參見第章的四應用題第題這裡用分治法求解再給出另一參考答案
對於兩個數x和y經一次比較可得到最大值和最小值對於三個數xyz最多經次比較可得最大值和最小值對於n(n>)個數將分成長為n和的前後兩部分A和B分別找出最大者和最小者MaxAMinAMaxBMinB最後Max={MaxAMaxB}和Min={MinAMinB}對A 使用同樣的方法求出最大值和最小值直到元素個數不超過設C(n)是所需的最多比較次數根據上述原則當n>時有如下關系式
C(n)=
通過逐步遞推可以得到C(n)=én/ù顯然當n>=時n>n/事實上én/ù是解決這一問題的比較次數的下限
假定待排序的記錄有n個由於含n個記錄的序列可能出現的狀態有n!個則描述n個記錄排序過程的判定樹必須有n!個葉子結點因為若少一個葉子則說明尚有兩種狀態沒有分辨出來我們知道若二叉樹高度是h則葉子結點個數最多為h反之若有u個葉子結點則二叉樹的高度至少為éloguù+這就是說描述n個記錄排序的判定樹必定存在一條長度為élog(n!)ù的路徑即任何一個籍助比較進行排序的算法在最壞情況下所需進行的比較次數至少是élog(n!)ù根據斯特林公式有élog(n!)ù =O(nlogn)即籍助於比較進行排序的算法在最壞情況下能達到的最好時間復雜度為O(nlogn)證畢
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23206.html
