从简介到算法的计数排序中的怪异步骤

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

这看起来是合理的，并且具有相同的渐近运行时间。但是，请考虑这样一种情况，您要排序的键的项目不仅仅是单个整数，而且还附加了一些其他数据。计数算法使排序稳定；保留具有相同键的项目的相对顺序（请参阅维基百科文章）。如果您只分配 的索引的输出，您将失去对一般数据进行排序的能力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

为了解释最后一部分的递减，我引用了这本书，这本书也解释了排序的稳定性：

由于元素可能不不同，因此C[A[j]]每次将值放入A[j]数组时都会递减B。递减C[A[j]]会导致值等于 的下一个输入元素A[j]（如果存在）转到A[j]输出数组中紧邻之前的位置。

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