algorithm - Bucket-Sort的此实现是否被视为“就地”？

考虑以下bucket sort的实现：

Algorithm BucketSort(S)
   input:  Sequence S of items with integer keys in range [0,N-1]
   output: Sequence S sorted in nondecreasing order of keys.

   let B be an array of N sequences, each of which is initially empty
   for each item x in S do
       let k be the key of x
       remove x from S and insert it at the end of bucket (sequence) B[k].
   for i←0 to N-1 do
       for each item x in sequence B[i] do
           remove x from B[i] and insert it at the end of S.

这一实施是否被视为“到位”？
我的教科书对“就地”给出了以下定义：
记住排序算法是
如果它只使用常量
除此之外的内存量
需要排序的对象。
现在，我知道上面的算法使用o（n+n）内存，其中n是范围的上界。但是，我可能错了，我认为n是一个常数，即使它是一个大的常数。所以我猜按照这个定义它是“到位的”，但我不确定。
因此，考虑到上述算法和“就地”的定义，是否考虑就地实现？

最佳答案

你所列出的算法显然没有到位。
您有另一个指针（b），它必须增长到与s相同的大小，但由于任何原因没有与s在一起。因此，您必须至少有o（s）个额外空间。仅仅因为要从s中删除这些值并不能避免在另一个变量b中仍然需要相同的空间量。
同样，因为bucket的数量可能是恒定的，并不意味着您可以忘记S中的所有元素都必须在不同的地方结束（B）注意len（S）>N的情况。
如果要进行就地排序，则需要将所有元素保留在S中，并对它们进行无序排列，以便常量额外空间是交换例程的临时持有者，如果使用递归解决方案，则可能是一些堆栈内存。