arrays - 将项目就地分类为段

Question

我有一个n 类型T 项目的数组，以及一个分类函数f(t)，它为每个项目分配一个类别数，从 O 到 k-1。 (k 是类别数)。目标是将数组分成 k 段，每个类别一个，然后重新排列项目，使它们都在正确的段中。

使用两个不同的输入和输出数组，我可以在 O(n) 内完成，但我需要就地完成(即使用交换作为基本操作)，如果可能的话，使用可并行算法。

一个想法是一个接一个地进行分段(首先将全 0 交换到开头的分段 [O, i0]，然后全 1(从 i0 ) 到一个新的段之后，等等)。这将是 O(n * k)(随着 n 变小)，但不可并行化。

另一种方法是使用 O(n log n) 的排序算法，它可能是可并行的，但这可能不是最优的，因为大多数项目比较相等.

我的问题是什么是解决这个问题的好方法，以及在文献中如何称呼这个问题？

Answer 1

快速说明一下，此问题与 - 但不完全相同 - Dutch national flag problem .在这个问题中，您有一个数组，其中包含三种不同颜色(红色、白色和蓝色)的球，目标是重新排序元素以使它们排序，以便红色排在第一位，然后是白色，然后是蓝色。

利用荷兰国旗问题的思路，我认为你可以相对高效和原地解决这个问题。例如，您可能希望使用专门设计用于处理重复元素的快速排序变体。 Bentley-McIlroy 3-way partitioning algorithm ，例如，专门设计用于处理有很多重复键的输入，并执行快速排序，其中分区方案将元素分为三组 - 小于键的元素、大于键的元素和等于键的元素- 然后只对“较少”和“较大”组进行排序。如果您有一个数组，其中只有 k 个不同的值，那么运行时间预计为 O(n log k)，因为每次递归调用都将在一个子数组上进行，子数组中的不同键的数量大约是其中的一半。这不是 O(n)，但它确实就地工作并且并行化非常好(让不同的线程处理每个子数组)。