Bucket-Sort的这种实现是否被认为是“in-place”？

考虑以下实施斗排序：Bucket-Sort的这种实现是否被认为是“in-place”？

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是一个常数，即使它是一个大的。所以我猜这是根据这个定义“就地”，但我不确定。

因此，考虑到上述算法和“原地”的定义，这种实现是否被认为是原地？

来源

2009-09-27 KingNestor

http://en.wikipedia.org/wiki/In-place_algorithm – 2009-09-27 21:37:22

Bucketsort绝对不是“就地”排序算法。

整体思路是，元素自己排序，因为他们被转移到桶。在最糟糕的情况下（连续值，但不重复），所需的额外空间与原始数组一样大。

来源

2009-09-27 21:15:20

但是这个数量是一个常量，不管它是否大于原始数组，是吗？在这种情况下，它会属于这个定义吗？ – KingNestor 2009-09-27 21:16:56

“in-place”的定义存在争用，这就是为什么我提供了自己的。 – KingNestor 2009-09-27 21:20:39

水桶N仅界定通过对输入序列S的长度n因为在S每一个项目可能有不同的密钥（映射键后）的数。因此，该算法需要线性的额外空间，因此不在原地。如果密钥未重新映射，则额外空间将由n解除绑定。

来源

2009-09-27 21:39:01

您列出的算法决定不在位。

您还有另一个指针（B），它必须是GROW与S的大小相同，但由于任何原因不适用于S。正因为如此，你必须至少有O（S）额外的空间。仅仅因为你从S中删除值并不能防止在另一个变量B中仍然需要相同数量的空间。

也仅仅因为桶的数量可能不变并不意味着您可以忘记所有元素在S中必须在不同的地方结束（B）。请注意len（S）> N的情况。

如果您想进行就地排序，您需要将所有元素保存在S中，并将它们四处乱洗，以使恒定的额外空间成为临时的持有者一个交换例程，如果您使用递归解决方案，可能还有一些堆栈内存。

来源

2009-09-28 01:53:40

Bucket-Sort的这种实现是否被认为是“in-place”？

回答

相关问题