工程排序功能

Question

我讀Engineering a Sort Function(pg-1254)其中JON L. BENTLEY & M. DOUGLAS麥克羅伊討論約2型成本模型的

MIX：開銷=比較<互換

的qsort：開銷<交換<比較

(page no-1254 of Engineering a Sort Function)

任何一個可以解釋我爲什麼比較中，除了字符串的情況下第二個模型過於昂貴？ 如果比較真是太昂貴，那麼爲什麼我們不使用「自下而上堆排序」？根據維基百科

，

It is a variant of Heapsort which is particularly suitable for the sorting of very large amounts of data, if a relatively high cost per compare operation is needed and on average better than Quicksort

Answer 1

之所以比較是昂貴是在下一句子：

第二模型反映了qsort接口的一般性的，其中比較是一個 函數，而不是一個機器原語。

這也是字符串的真實。事實上，對於字符串尤其如此，因爲比較兩個字符串涉及函數調用，指針間接（再見參考的局部性）和行走兩個字符串，分鐘（m,n）字節比較，其中m ，ñ是串的長度。

如果比較成本太高，那麼爲什麼我們不使用「自下而上」？

你應該問的作者。

Answer 2

當間接訪問鍵（通過指針或類似的數組）時，交換的成本與參考信息的大小有關;比較的成本總是與密鑰的大小有關。所以交換的成本可以忽略不計。