O(1)空间中的计数排序

Question

我有以下计数排序，但空间复杂度对我来说太高了，我正在寻找一种在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(空间。假设k<=A.length，如何将算法的空间复杂度提高到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循环(。

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

请注意，在一般情况下(其中k不一定是<= |A|(，这并不容易。此外，仅仅因为输出阵列B已经被提供给我们作为输入；技巧"；将其用于我们的内部使用，从而不必分配任何新的内存。