1000个无序整数最多要比较多少次才可以找到最大值 (c语言面试问题)

Question

如题 告诉我方法 还有找到第2大数要多少次比较

Answer 1

应该是最少比较次数吧，最多的话不就可以反复比较了？
不重复比较的话每个数都和别的数比较一次，对多可以比较(999+0)*1000/2次
冒泡排序，选择排序都是(999+0)*1000/2次，插入排序小于(999+0)*1000/2次

找最第二大数我觉得可以记下max1最大,max2第二，然后顺序扫描数组，和max1比较，如果元素比max1大,就max2=max1,max1=该元素，所以只要比较999次就行了

Answer 2

999次：将1000个数随便排列，将第一个数与第二个数比较，将较大数放在第二个数的位置；再将第二个数与第三个数比较，将较大数放在第三个数的位置；依次往下，就将这1000个数从小到大排列起来，共用999次比较，因此经排列后最后一个数就是最大值，倒数第二个数就是第二大数。

Answer 3

如果你问具体的几次我没去算，这里考察下复杂性，
找到最大和第二大都只要o(n)次。
同时存在线性时间（o(n)）的选择算法找出第k大的数，这个你可以去学习算法设计。