5

这似乎是一本非常普通的书（Cormen、Leiserson、Rivest、Stein），因此希望有人能够提供帮助。第8章给出了计数排序算法。输入数组 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 从第一种形式转换为第二种形式是否会使其稳定？

4

1 回答 1

4

我想您建议对中间体执行以下操作C（使用索引 1 数组）：

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

这似乎是合理的，并且具有相同的渐近运行时间。但是，请考虑您要对其进行排序的项不仅是单个整数，而且还附加了一些其他数据的情况。计数算法使排序稳定；具有相同键的项目的相对顺序被保留（参见Wikipedia 文章）。如果仅从 的索引分配输出，您将失去对一般数据进行排序的能力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，因为它不会计算小于输入数组中任何特定项目的项目数（正如他们定义的那样）。:)

于 2013-02-21T06:16:41.617 回答