对于一系列值，如何在 Boost Accumulators 中找到排序后的中间 50% 的序列？
例如，假设我有以下序列，
25、21、9、13、17、19、12、29、50、97、10、11。
我想要的中间50%的数据如下:
13、17、19、21。
当然，可以对序列进行排序，现在变成了
9、10、11、12、13、17、19、21、25、29、50、97。
然后可以收集中间 50% 的数据。
现在，累加器框架是否在内部存储和排序序列？如果是，是否可以检索驻留在特定索引中的值？
阅读自here ，我认为 Accumulators 框架不存储原始数据，这个框架不适合我要解决的问题。
在写这篇文章时，我发现尝试使用累加器来完成此任务有点愚蠢。但是，我将它用于其他目的，并且我期待累加器中的解决方案。
现在，是否有可能构建一个数据结构，以一种数据结构的大小几乎不超过序列大小的一半的方式有效地维护当前且已排序的中间 50% 数据？
想了想，我想可能无法设计出这样的数据结构。起初，我认为某些值可以被永久遗忘/丢弃，假设它们永远不会出现在排序后的中间 50% 中。但是，这种假设可能是错误的，某些值可能会重新出现在已排序的中间 50% 中，具体取决于序列中尚未到达的值。
最佳答案
正如 @Adam Rosenfeld 指出的，您正在寻找霍尔选择算法，它是快速排序的一种变体。
他没有指出的是，只要稍加小心，您就可以让它在选择过程中将您关心的元素放在正确的位置。
选择算法将数据划分为小于和大于所选元素的数据。例如，假设您有一个包含 100 个元素的数组，并且您想要第 25 个元素。它会排列元素，使数组中的第一个到第 24 个元素小于第 25 个元素，然后将是第 25 个元素，然后是较大的元素。但每一侧的元素仅根据该元素进行排序，而不是相互比较。
您仍然可以利用这一点快速获得中间 50%:首先选择第 25 个百分位数。然后仅将第 25rds 上方的部分指定为输入，并查找跨该部分的 2/3rds 元素。这将为您提供第 25th、第 75th 和(重要的部分)所有值在这些元素之间的元素也将排列在这些元素之间(尽管在该范围内，顺序基本上是随机的)。
关于data-structures - 查找排序后的序列的中间 50%(在 Boost Accumulators 或其他数据结构中)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3878776/