如何在线性时间内对2个可能值的元素进行"排序"？

Question

假设我有一个函数f和元素数组.

函数返回A或B任何元素; 你可以用这种方式想象元素ABBAABABAA.

我需要根据函数对元素进行排序,结果是: AAAAAABBBB

A值的数量不必等于B值的数量.元素的总数可以是任意的(不固定).请注意,您不对字符进行排序,您可以对具有单个char表示的对象进行排序.

更多的东西:

• 排序应该采取线性时间 - O(n),
• 它应该在适当的地方进行,
• 它应该是一个稳定的类别.

有任何想法吗？

---

注意:如果上述情况不可能,那么您是否有牺牲上述要求之一的算法的想法？

Answer 1

在其他给定约束下可能无法实现稳定排序，因此这里有一个不稳定排序，类似于快速排序的分区步骤。

1. 有 2 个迭代器，一个从左侧开始，一个从右侧开始。
2. B当右侧 有一个迭代器时，递减该迭代器。
3. A当左侧 有一个迭代器时，增加迭代器。
4. 如果迭代器没有相互交叉，则交换它们的元素并从 2 开始重复。