哪个算法可以使用仅 O(N) 步骤在原地完成稳定的二进制分区？

Question

我正在学习这篇论文：线性时间稳定最小空间划分

它似乎关键的部分在于：

算法B在O(nlog₂n)时间和固定额外空间（constant extra space）内稳定排序大小为n的位数组，但仅需O(n)次操作。

然而，该论文并没有描述算法B，只是提及了另一篇我无法访问的论文。虽然我可以找到几种在时间限制内进行排序的方法，但我很难找到一种保证O(N)次操作且又不需要超过常量空间的方法。

那么，算法B是什么？换句话说，给定

boolean Predicate(Item* a);  //returns result of testing *a for some condition

是否有一个函数B(Item* a, size_t N);用少于nlog₂n个Predicate调用，使用Predicate作为排序关键字来稳定地对a进行排序，并仅执行O(N)次写入到a？

- AShelly

---

在 "List of Proof Techniques" 中，证明方法之一为"Proof by ghost reference"： 引用的参考文献中甚至没有任何与所引用定理类似的内容。 - corsiKa

有趣的链接，但不适用。参考文献是J.I. MUNRO、V. RAMAN等人的“稳定原地排序和最小数据移动”。谷歌搜索显示，该组合还发表了几篇相关主题的论文，包括“快速稳定的原地排序，具有O(n)数据移动。Algorithmica 16, 151-160。”所以我认为这是一种真正的技术（至少在理论上）。但我仍然找不到一个版本来证明它实际上是可行的。 - AShelly

啊，糟糕。重新阅读你的问题，你是对的，它不适用。不过，有趣（也很悲哀）的是，这些在论文和讲座中出现的例子有多少。如果我在大学时有这个列表，那会更有趣。 - corsiKa

或许值得在http://cstheory.stackexchange.com/上询问。 - Steve

Answer 1

我倾向于说这是不可能的。每当你计算O(n log n)数量的信息，但没有（1）地方可以存储它（常量空间），也没有（2）立即使用它的地方（O(n)移动），就会出现一些奇怪的情况，可能涉及大量使用堆栈（可能未包含在空间分析中，尽管应该包括在内）。

如果你将临时信息存储在一个整数的许多位中，或者类似于松鼠的东西，那么可能是可能的。（因此，在实践中为O(1)，但在理论上为O(log n)。）

基数排序不太适用，因为你必须调用谓词来创建数字，如果你不记忆比较的传递性，那么你将调用它O(n^2)次。（但是要记忆化需要每个项的平摊空间为O(log n)，我想。）

QED-缺乏想象力的证明 :)

- Spencer Tipping

---

我确定这将涉及一些位打包，根据我所阅读的有关该主题的论文中所能了解到的。只是我还不能完全弄清楚如何做。 - AShelly

Answer 2

这是我目前的进展。这是一个循环排序的版本，它使用位数组来保存分区测试的结果，并动态计算目标位置。它执行稳定的二进制分区，需要N次比较，< N次交换，并且需要精确分配2N个位的存储空间。

int getDest(int i, BitArray p, int nz)
{   bool b=BitArrayGet(p,i);
    int below = BitArrayCount1sBelow(p,i);  //1s below
    return (b)?(nz+below):i-below;
}

int BinaryCycleSort(Item* a, int n, BitArray p)
{
   int i, numZeros = n-BitArrayCount1sBelow(p,n);
   BitArray final = BitArrayNew(n);
   for (i=0;i<numZeros;i++)
      if (!BitArrayGet(final,i))
      {  int dest= GetDest(i,p,numZeros);
         while (dest!=i)                
         {  SwapItem(a+i,a+dest); 
            BitArraySet(final,dest);
            dest = getDest(dest,p,numZeros);
         }
         BitArraySet(final,dest);
      }
   return numZeros;
}

int BinaryPartition(Item* a, int n, Predicate pPred)
{ 
   int i;
   BitArray p = BitArrayNew(n);
   for (i=0;i<n;i++)
      if (pPred(a+i)) BitArraySet(p,i);
   return BinaryCycleSort(a,n,p);
}

使用这些辅助工具：

typedef uint32_t BitStore;
typedef BitStore* BitArray;
BitArray BitArrayNew(int N); //returns array of N bits, all cleared
void BitArraySet(BitArray ba, int i); //sets ba[i] to 1
bool BitArrayGet(BitArray ba, int i); //returns ba[i]
int BitArrayCount1sBelow(BitArray ba, int i) //counts 1s in ba[0..i)

显然这不是常数空间。但我认为这可能被用作最终目标的构建块。整个数组可以使用大小为B位的固定大小BitArray分成N/B块。在执行稳定合并时，是否有一些方法可以重复使用相同的位？

- AShelly

Answer 3

基数排序 不是吗？

O(kN)

- fabrizioM

---

我想看看你如何在常数空间开销的情况下实现它。此外，原帖明确提到使用谓词而不是整数映射。 - ltjax

基于布尔谓词的排序本质上是一位基数排序。我知道如何进行原地或稳定排序，但两者都不知道怎么做。 - AShelly

如果您无法计算所有元素的前缀和，那么您可以在线性时间内（使用线性额外内存）计算出每个元素“排序后”的稳定索引。然后，您只需要一些巧妙的方法来交换元素，以便您只需要交换每对元素一次。我猜这是困难的部分，但也许可以在n log n中实现？ - zerm

@zerm，实际上，一旦你有了索引，那么实现O(N)交换就很容易了。看看我的答案-你可以将_getDest(i,..)_实现为return prefixIndex[i];。我看到的问题是在常量空间中存储前缀和。即使使用理想的位打包，100万个前缀和的存储空间也约为240万字节。 - AShelly

@AShelly，是的，我想那就是问题所在。我一直在考虑不存储完整的前缀，但这会退化成类似冒泡排序的东西。然而，我并不确定——也许只有二进制数据存在时，冒泡排序之类的复杂度可以降低...嗯... - zerm

@AShelly：我可以在原地进行排序并保持稳定，但代价是 NlogN 的执行时间。 还挺漂亮的。如果目标是将所有大写字母移到前面，所有小写字母移到后面等，可以先按字母对进行排序。然后将两个已排序的 N 个字母组转换为一个排序的 2N 字母组，观察是否第一组以 p 个小写字母结束，第二组以 q 个大写字母开始，则只需要将适当的(p + q)个字母向右旋转q个位置（或向左旋转p个位置）。很巧妙，对吧？ - supercat