哪种算法可以只需要 O(N) 次移动就可以进行稳定的就地二进制划分？

Question

我试图理解这篇论文：稳定的最小空间分区 在线性时间内。

似乎该主张的一个关键部分是

算法 B 对大小为 n 的位数组进行稳定排序 O(nlog₂n) 时间和恒定的额外空间，但仅进行 O(n) 移动。

然而，该论文没有描述该算法，而只是引用了另一篇我无法访问的论文。我可以找到多种方法在时间范围内进行排序，但我很难找到一种保证 O(N) 次移动而不需要超过恒定空间的方法。

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

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

一个函数 B(Item* a, size_t N);，它使用 Predicate 作为排序键对 a 进行稳定排序对 Predicate 的调用少于 nlog₂n，并且仅对 a 执行 O(N) 写入？

Answer 1

我很想说这是不可能的。每当您计算 O(n log n) 数量的信息，但 (1) 无处存放它（恒定空间），并且 (2) 无处立即使用它（O(n) 移动）时，就会出现一些奇怪的情况上，可能涉及堆栈的大量使用（可能不包括在空间分析中，尽管它应该包括在内）。

如果您将临时信息存储在一个整数的许多位中，或者类似的东西，这可能是可能的。 （所以实际上是 O(1)，但理论上是 O(log n)。）

基数排序并不能完全做到这一点，因为你必须调用谓词来创建数字，并且如果你不记住传递性进行比较，然后您将调用它 O(n^2) 次。 （但我认为，要记住每个项目需要 O(log n) 摊销空间。）

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

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 个块。在执行稳定合并时是否有某种方法可以重用这些相同的位？

Answer 3

不是 RadixSort 吗？

O(kN)