从Intro to Algorithms计算排序的奇怪步骤

Question

这似乎是一本非常常见的书(科尔曼，雷瑟森，里维斯特，斯坦因)，所以希望有人能提供帮助。在第八章中，给出了计数排序的算法。这是有意义的，在这里你有输入数组A，你可以找到数组C的大小从0到k的范围。然后使Ci包含A中等于i的元素的数量。例如：

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

但在此之后，它们使Ci包含小于或等于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

这似乎是合理的，并且具有相同的渐近运行时间。但是，考虑这样一种情况:您正在排序的项的关键字不只是单个整数，而是附加了一些其他数据。这就是为什么排序通过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

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

因为元素可能不是不同的，所以每次将值A[j]放入B数组中时，我们都会递减C[A[j]]。减少C[A[j]]会导致下一个值等于A[j]的输入元素(如果存在)转到输出数组中A[j]之前的位置。

另外，如果我们这样做了，我猜我们就不能再叫它COUNTING-SORT了，因为它不会计算小于输入数组中任何特定项的项数(正如他们定义的那样)。:)