algorithm - Bucket-Sort 的这个实现是否被认为是 "in-place"？

Question

考虑桶排序的以下实现:

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.

此实现是否被视为“就地”？

我的教科书对“就地”给出了以下定义:

Remember that a sorting algorithm is in-place if it uses only a constant amount of memory in addition to that needed for the objects being sorted.

现在，我知道上述算法使用 O(n+N) 内存，其中 N 是范围的上限。然而，我可能错了，我认为 N 是一个常数，即使它很大。所以我猜根据这个定义它是“就地”的，但我不确定。

那么鉴于上述算法和“就地”的定义，这个实现是否被认为是就地？

Answer 1

您列出的算法显然不合适。

您有另一个指针 (B)，它必须 GROW 到与 S 相同的大小，但由于任何原因不在 S 的位置。因此，您必须至少有 O(S) 个额外空间。仅仅因为您从 S 中删除值并不能阻止您在另一个变量 B 中仍然需要相同数量的空间。

同样，仅仅因为桶的数量可能是恒定的并不意味着您可以忘记 S 中的所有元素必须在不同的位置 (B) 结束。注意 len(S) > N 的情况。

如果你想进行就地排序，你需要将所有元素保留在 S 中并将它们随机排列，这样恒定的额外空间是交换例程的临时持有者，如果你正在使用，则可能是一些堆栈内存递归解决方案。