各位神人好
想请问在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?

楼上的方法排序后，索引值头尾不就是答案了吗