查找 LinkedList 中数字的中位数
如何找到 Java 中存储为 LinkedList 的数字列表的中位数？ 我不明白维基百科提到的选择算法。 如果你能解释这一点，就加分。
How do you find the median of a list of numbers stored as a LinkedList in Java? I don't understand the Selection Algorithm that Wikipedia refers to. Bonus points if you can explain that.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
最好的算法是 QuickSelect
阅读文章并尝试理解快速排序——概念是相似的。
The best algorithm is QuickSelect
Read the article and try to understand QuickSort - The concept is similar.
如果您想要一种快速编程方式，请对列表进行排序并选择中间元素（或两个中间元素的平均值）。
更高效的选择算法本质上会尝试避免对列表中实际上不需要排序的位进行排序，以找到给定 n 的第 n 个元素。 （JDK 目前不提供这样的开箱即用的算法。） 更新： 只是为了扩展我之前的文章，更有效的方法的示例包括：
If you want a quick-to-program way, sort the list and choose the middle element (or mean of the two middle elements).
More efficient selection algorithms essentially try to avoid sorting bits of the list that you don't actually need to sort to find the nth element for your given n. (The JDK doesn't currently provide such an algorithm out of the box.) Update: just to expand on my earlier post, examples of more efficient methods would include:
您基本上有两个主要选择：
简单快速的方法 - 在
O(nlogn)中对列表进行排序。 由于中位数被定义为一半值比它大、一半比它小的值，因此只需取第 n/2 个值 - 这就是中位数。如果这是一项对性能至关重要的任务，您可以应用各种选择算法，这些算法在好的情况下可以为您提供
O(n)（但在最坏的情况下仍然无法保证线性）。无论如何，请查看选择算法上的维基百科条目，这应该可以让您对所有可用的方法有一个很好的总结。
You have basically two major options:
Easy and quick method - sort the list in
O(nlogn). Since the median is defined as the value which half the values are larger than it, and half are smaller, just take then/2th value - that's the median.If this is a performance crucial task, you can apply various selection algorithms which can give you
O(n)in good cases (but still cannot guarantee linearity in worst-cases).In any case, check out the wikipedia entry on Selection Algorithms, that should give you a good round-up on all the available methods.
中位数是排序列表中间的数字。 （对于条目数量为奇数的列表很容易，对于条目数量为偶数的列表，它可以是两个“中间数字”之间的任意数字）
所以对列表进行排序，并找出中间数字是什么） 是。
The median is the number in the middle of the sorted list. (Easy for a list with an uneven number of entries, for a list with an even number of entries it can be any number between the two "middle numbers" both included)
So sort the list, and figure out what the middle number(s) are.