O(1) space 中的计数排序

Question

我有以下计数排序，但是 space 复杂度对我来说太高了，我正在寻找一种方法来实现 space 复杂度为 O(1)

MyCountingSort(A, B, k)
    for i = 0 to k
       do G[i] = 0
    for j = 0 to length[A]
        do G[A[j]] = G[A[j]] + 1
    for i = 1 to k
       do G[i] = G[i] + G[i-1]
    for j = length(A) to 1
       do B[G[A[j]]] = A[j]
       G[A[j]] = G[A[j]] - 1

目前，算法正在分配 O(k) space。假设 k<=A.length，我如何才能将算法 space 的复杂度提高到 O(1)？

Answer 1

我在这里假设 A 是您的输入数组，B 是您的输出数组。因此，|A| = |B|。我进一步假设 k 是我们可能遇到的最大值数（例如，如果 A 仅包含从 1 到 k 或从 0 到 k-1)。如果您在提问时指定此类详细信息，这将对我们有所帮助，但我猜这或多或少就是您要问的。 :)

因为我们有非常方便的附加约束 k <= |A|，我们可以使用我们给定的数组 A 和 B 作为索引数组的中间存储。本质上，在您的代码中使 B 您的 G 并在其上执行 1st 和 2nd 循环。然后我们进行累积加法（3rd 循环）。

完成此操作后，我们可以将 B 复制回 A。最后，我们用最终排序的数组覆盖 B（代码中的 4th 循环）。

这样，除了已经给定的输入参数外，没有分配内存。通常，算法的 space 复杂度被定义为与算法的输入无关。由于我们只是回收输入数组而不是自己分配任何东西，因此该算法确实具有 O(1) space 复杂度。

请注意，在一般情况下（k 不一定是 <= |A|），事情不会这么容易。此外，只是因为输出数组 B 已经作为输入提供给我们，我们可以利用这个“技巧”将它用于我们的内部使用，因此不必分配任何新内存.

O(1) space 中的计数排序

Counting sort in O(1) space

algorithm

sorting

big-o

complexity-theory

counting-sort