考虑以下问题。
我们得到一个属于两个类的元素数组：红色或蓝色。我们必须重新排列数组的元素，以便所有蓝色元素排在第一位（所有红色元素紧随其后）。必须以稳定的方式进行重新排列，这意味着必须保留蓝色元素的相对顺序（红色元素也是如此）。
是否有一种聪明的算法可以就地执行上述重新排列？
当然，非就地解决方案很简单。
一个明显的就地解决方案是将任何稳定的排序算法应用于数组。然而，在数组上使用成熟的排序算法直觉上感觉有点过头了，特别是考虑到我们只处理两类元素的事实。
任何想法都非常感谢。
问问题
423 次
3 回答
6
显然可以在 O(n) 时间和 O(1) 空间内完成。Jyrki Katajainen的论文Stable minimum space partitioning in linear time，Tomi Pasanen 声称能够做到这一点。
谷歌稳定的 0-1 排序。
于 2010-05-25T17:38:08.380 回答
1
我不知道 O(n) 算法，但这是一个在最坏情况下具有 O(n*log(n)) 复杂度的简单算法。也许它会有用。
从头切掉零，从尾切掉零，它们已经在他们的位置上。现在数组看起来像一串一，后跟一串零，然后是一串，依此类推，如下所示：1010101010
将第一个 1 序列与第一个 0 序列交换，将第三个 1 序列与第三个 0 序列交换，依此类推。它将变为：0110011001
序列的数量减少了大约两倍。重复上述过程，直到数组排序完毕。
要交换两个相邻序列，先反转第一个，然后反转第二个，然后再反转它们。
于 2010-05-25T19:58:42.740 回答
1
这在 C++ 中称为稳定分区，并且有一个标准算法：std::stable_partition。
SGI 实现根据可用内存量具有自适应行为：
- 如果可以分配 O(N) 空间，它将在 O(N) 中运行
- 它以 O(N log N) 就地交换运行
我确实想知道后者的解决方案是否在幕后使用了稳定的排序算法。
于 2010-05-26T07:21:46.857 回答