各位神人好
想請問在int array[5000]裡
如何用最少的compare次數
找出最大 最小 次大 次小的值
有沒有小於下列5000*4次 compare的找法
(找每一個數都用暴力法)
for(i=0;i<5000;i++)
if(array[i] > Max)
Max = array[i]
感謝

概念: 一個數沒比過不會知道他是不是最大

同時找最大與最小，有 5000*3/2 次比較的方法。找最大與次大，有 n + log_2 n 次比較的方法。所以看來應該有 5000*3/2 + 2*log_2 5000 次比較的方法找到這四個資料，只是程式寫起來或許比較麻煩。

sorting network 這是超級困難的問題

sorting network 的限制應該太強了吧因為 sorting network 不能依照之前比較的結果來選擇下一次要比較的元素

對耶 那麼 樓上說的這種情況 有沒有專有名詞？

decision tree?

都n log n 了 幹嘛不直接quick sort?

樓上的方法排序後，索引值頭尾不就是答案了嗎