java - 在 LinkedList 中查找数字的中位数

Question

你如何找到在 Java 中存储为 LinkedList 的数字列表的中位数？我不明白维基百科所指的选择算法。如果你能解释一下，加分。

Answer 1

最好的算法是QuickSelect

阅读文章并尝试理解 QuickSort - 概念类似。

Answer 2

您基本上有两个主要选择：

1. 简单快捷的方法 - 对列表进行排序O(nlogn)。由于中位数被定义为一半的值大于它，一半的值小于它的值，所以只需取第一个n/2值 - 这就是中位数。

2. 如果这是一项对性能至关重要的任务，您可以应用各种选择算法，这些算法可以O(n)在好的情况下为您提供（但在最坏的情况下仍不能保证线性）。

无论如何，请查看 wikipedia entry on Selection Algorithms，这应该可以让您对所有可用的方法有一个很好的总结。

Answer 3

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

更有效的选择算法本质上是尽量避免对列表中您实际上不需要排序的位进行排序，以找到给定n的第n个元素。（JDK 目前不提供这种开箱即用的算法。）更新：为了扩展我之前的帖子，更有效方法的示例包括：

• 基于并行排序的选择，其初始阶段在对每个存储桶进行排序之前将数据放入多个“存储桶”，但随后（在中位数的情况下）您实际上只对中间的“存储桶”进行排序，因为精确任何一方的桶中项目的顺序都无关紧要
• 基于诸如快速排序之类的分而治之排序算法进行选择，但同样，该算法实际上并未对超出所需范围的子列表进行排序。

Answer 4

中位数是排序列表中间的数字。（对于条目数奇数的列表很容易，对于条目数为偶数的列表，它可以是两个“中间数字”之间的任意数字）

所以对列表进行排序，并找出中间的数字是什么。