尋找7位數字中位數的比較數

Question

我可以通過12次比較找到中位數。但我想知道最少的比較數量以及如何去做。

Answer 1

Donald Knuth在第三卷「計算機程序設計藝術」的「最小比較選擇」中有一章。

克努特說：「[選擇在比較中的最小號]沒有通用的方法是尚未明顯」，但他給出了接近最低的一般方法。我們可以看到V 4（7）= 10（也就是說，你可以使用至多10次比較找到7項中的第4大項），算法（「手工找到通過試驗和錯誤「）在練習5.3.3-10的解決方案中給出。

Answer 2

如果允許並行比較（現代CPU可能會爲你做這個），你可以使用一個sorting network解決的六個步驟的問題。