部分排序为N个未排序组的有效算法

Question

我正在寻找一种有效的算法来执行以下操作：给定N个项目的数组，以某种方式对它进行排序，以便项目以M个相等组进行排序，其中每个组是未排序，但组之间彼此排序（一个组中的所有元素都小于下一个组的任何元素）。

最简单的方法是对整个数组进行排序。但效率不高，特别是如果组数远远小于项目总数（例如，将100万项分为5组）。

目前我已经决定使用quickselect算法（具体来说，它是Floyd-Rivest variation）将数组排序为2个未分类的组，然后将其应用M-1次。一个显着的改进可能是采用分而治之的方法来快速选择，首先将数组分成两组，然后对每一组进行排序等等，直到我们有M组。一种泛化的unordered partial sorting问题。

但我有一种直觉，认为可能有一种更简单，更有效的方法解决问题。有什么我失踪？有任何想法吗？我需要在我的RBush JavaScript library（一种高效的R *树实现）中提高批量插入性能。

Answer 1

这里是重述的问题。您需要同时查找M-1个排名元素，并使用它们将该数组划分为M个未排序的组。

我建议与选择为接近中值随机枢轴标准quickselect开始（做随机子样本特技来估计），对于每种情况下将所述阵列分成2和也除以排列表您还需要查找2个元素。继续进行下去，直到您找到您当前组中找到排名元素的级别。然后切换到快速选择的Floyd-Rivest变体，以实际找到该元素并将当前组拆分为2.然后从快速选择中退出，您可以轻松拼凑出所需的M个组。

该方法的预期运行时间为O(N log(M))，具有相当不错的常量。我怀疑这比那个好得多。