algorithm - 从 Intro 到 Algorithms 的计数排序的奇怪步骤

Question

这似乎是一本非常普通的书(Cormen、Leiserson、Rivest、Stein)，所以希望有人能够提供帮助。第八章给出了计数排序的算法。在您拥有输入数组 A 并且找到数组 C 的大小从 0 到 k 的范围内是有意义的。然后使 C[i] 包含 A 中等于 i 的元素数。例如:

A: [2,5,3,0,2,3,0,3]
C: [2,0,2,3,0,1]

但在这之后他们使得 C[i] 包含小于或等于 i 的元素数。例如:

C: [2,2,4,7,7,8]

为什么这是必要的？难道你不能只遍历原始 C 并从中得到一个排序数组吗？您知道每个数字的确切计数，因此您可以按顺序将每个数字的正确数量放入 B 并得到一个排序数组。将 C 从第一种形式转换为第二种形式是否会以某种方式使其稳定？

Answer 1

我想你打算用中间体 C 做以下事情(使用索引 1 数组):

i = 1
for k = 1 to len(C)
  for j = 1 to C[i]
    B[i] = k
    i = i + 1

这似乎是合理的，并且具有相同的渐近运行时间。但是，请考虑这样一种情况，您要对其进行排序的项的键不仅是单个整数，而且还附加了一些其他数据。计数算法使排序稳定；保留具有相同键的项目的相对顺序(参见 the Wikipedia article )。如果您只分配 C 的索引的输出，您将失去对一般数据进行排序的能力。 .因此，为什么排序通过 B[C[A[j]]] <- A[j] 分配元素.

对于其他好奇的人，这是原始算法的完成:

# C[i] now contains the number of elements equal to i.
for i = 1 to k
  C[i] <- C[i] + C[i-1]
# C[i] now contains the number of elements less than or equal to i.
for j = length[A] downto 1
  B[C[A[j]]] <- A[j]
  C[A[j]] <- C[A[j]] - 1

为了解释最后一部分的递减，我引用了书，里面也解释了排序的稳定性:

Because the elements might not be distinct, we decrement C[A[j]] each time we place a value A[j] into the B array. Decrementing C[A[j]] causes the next input element with a value equal to A[j], if one exists, to go to the position immediately before A[j] in the output array.

此外，如果我们这样做，我想我们将无法调用它 COUNTING-SORT不再是因为它不会计算少于输入数组中任何特定项目的项目数量(正如他们定义的那样)。 :)