对长整数列表排序是否比每次取最大值的效率更高？

这个说法不是绝对成立，需要结合你需要获取最大值的次数判断：

• 如果你需要把列表中所有元素按从大到小的顺序全部取出（也就是要执行n次取最大值操作）：这个说法成立。每次遍历取最大值的总时间复杂度是O(n²)，全列表排序的时间复杂度是O(n log n)，当n足够大时，O(n log n)的效率远高于O(n²)，就算加上n次弹出元素的O(n)开销，整体复杂度依然是O(n log n)，优势非常明显。
• 如果你只需要取前k个最大值，且k远小于n：这时候排序方案的效率反而更低。比如你只需要取1个最大值，直接单次遍历找最大值的复杂度只有O(n)，远低于排序的O(n log n)。

如果你的使用场景是需要不定次数获取当前最大值，可以选择大顶堆（最大堆）结构：

• 初始建堆的时间复杂度为O(n)
• 每次弹出最大值的时间复杂度为O(log n)
• 总时间复杂度为O(n + k log n)，k为取最大值的次数，适配性比前两种方案都更高，k较小时比排序效率高，k接近n时和排序方案效率基本持平。

内容的提问来源于stack exchange，提问作者Patrick_Chong