查找LinkedList中数字的中位数

Question

如何找到在Java中存储为LinkedList的数字列表的中值？我不明白维基百科引用的选择算法。奖励积分，如果你能解释这一点。

Answer 1

最好的算法是QuickSelect

阅读这篇文章，并试图了解快速排序 - 这个概念是相似的。

Answer 2

如果您想要快速编程的方式，请对列表进行排序并选择中间元素（或两个中间元素的平均值）。

更高效的选择算法本质上尽量避免排序，你实际上并不需要进行排序，找到ñ个元素为您给出ñ列表位。 （JDK中目前不提供这样的算法开箱即用的。）更新：只是在我先前的职位扩大，更有效的方法的例子将包括：

• 在parallel sort，其初始选择基础阶段在将每个桶分类之前将数据放入多个“桶”中，但是之后（在中间值的情况下），只对实际中间的“桶”进行排序，因为桶中任何一方的物品的精确顺序是不相关
• 以分治法排序算法（如Quicksort）为基础进行选择，但是算法实际上并未对超出所需范围的子列表进行排序。

Answer 3

中位数是排序列表中间的数字。 （易于列出不均匀数量的条目，对于具有偶数条目的列表，它可以是包括在两个“中间数字”之间的任何数字）

因此，对列表进行排序，并找出什么中间数字是。

Answer 4

主要通过两种主要选择：

1. 容易和快速的方法 - 按照O(nlogn)列表。由于中位数被定义为值的一半大于它的值，一半的值较小，所以只取n/2 th值 - 这是中位数。

2. 如果这是一个性能至关重要的任务，那么可以应用各种选择算法，这些算法可以在很好的情况下给出O(n)（但仍然无法保证最坏情况下的线性）。

在任何情况下，检查出Selection Algorithms的Wikipedia条目，应该给你的所有可用的方法好圆​​式。