在不排序列表的情况下查找未排序列表的第N个项目

在不排序列表的情况下查找未排序列表的第N个项目

排序至少需要O（nlogn）运行时间-
有非常有效的选择算法可以在线性时间内解决您的问题。

Partition-based selection

（有时是

Quickselect

），它基于quicksort（递归分区）的思想，是一个很好的解决方案（请参阅伪代码的链接+另一个示例）。