algorithm - 部分排序为 N 个未排序组的高效算法

Question

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

最简单的方法是对整个数组进行排序。但它的效率很低，特别是如果组的数量远小于项目的总数（例如将一百万个项目分成 5 个组）。

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

但我有一种直觉，可能有一种更简单、更有效的方法来解决这个问题。有什么我想念的吗？有任何想法吗？我需要它来提高我的RBush JavaScript 库（一种高效的 R*-tree 实现）中的批量插入性能。

Answer 1

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

我建议从标准快速选择开始，随机枢轴选择接近中位数（使用随机子样本技巧来估计），对于每种情况，将数组分成 2，并将您需要查找的排名元素列表划分为2也一样。继续此操作，直到您可以在当前组中找到排名元素的级别。然后切换到快速选择的 Floyd-Rivest 变体以实际找到该元素并将当前组拆分为 2。然后退出快速选择，您可以轻松地将所需的 M 个组拼凑在一起。

这种方法的预期运行时间是O(N log(M))相当不错的常数。我怀疑比这明显更好是可行的。