我有一个n 类型T 项目的数组，以及一个分类函数f(t)，它为每个项目分配一个类别数，从 O 到 k-1。 (k 是类别数)。 目标是将数组分成 k 段，每个类别一个，然后重新排列项目，使它们都在正确的段中。
使用两个不同的输入和输出数组，我可以在 O(n) 内完成，但我需要就地完成(即使用交换作为基本操作)，如果可能的话，使用可并行算法。
一个想法是一个接一个地进行分段(首先将全 0 交换到开头的分段 [O, i0]，然后全 1(从 i0) 到一个新的段之后，等等)。这将是 O(n * k)(随着 n 变小)，但不可并行化。
另一种方法是使用 O(n log n) 的排序算法，它可能是可并行的，但这可能不是最优的，因为大多数项目比较相等.
我的问题是什么是解决这个问题的好方法，以及在文献中如何称呼这个问题？
最佳答案
快速说明一下，此问题与 - 但不完全相同 - Dutch national flag problem .在这个问题中，您有一个数组，其中包含三种不同颜色(红色、白色和蓝色)的球，目标是重新排序元素以使它们排序，以便红色排在第一位，然后是白色，然后是蓝色。
利用荷兰国旗问题的思路，我认为你可以相对高效和原地解决这个问题。例如，您可能希望使用专门设计用于处理重复元素的快速排序变体。 Bentley-McIlroy 3-way partitioning algorithm ，例如，专门设计用于处理有很多重复键的输入，并执行快速排序，其中分区方案将元素分为三组 - 小于键的元素、大于键的元素和等于键的元素- 然后只对“较少”和“较大”组进行排序。如果您有一个数组，其中只有 k 个不同的值，那么运行时间预计为 O(n log k)，因为每次递归调用都将在一个子数组上进行，子数组中的不同键的数量大约是其中的一半。这不是 O(n)，但它确实就地工作并且并行化非常好(让不同的线程处理每个子数组)。
关于arrays - 将项目就地分类为段，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26455603/