algorithm - 计数排序的归纳证明？

Question

我正在介绍计数排序算法，我了解它是如何工作的，但我想知道是否有具体的方法可以证明计数排序是一种稳定的算法。我有一个关于如何归纳证明这一点的想法，但我不确定如何去做。

for i = 1 to k
    C[i] = 0

for j = 1 to n
   C[A[j]] = C[A[i]] + 1

for i = 2 to k
   C[i] = C[i] + C[i-1]

for j=n to 1
   B[C[A[j]]] = A[j]
   C[A[j]]--

我假设证明将从数组只有一个元素的基本情况开始

基本情况 n = 1，未排序数组 A[1] = a1，排序数组 B[1] = a1

归纳步骤: ??? 我不确定如何处理这种类型的归纳证明。

Answer 1

要通过数学归纳法证明计数排序是稳定排序，您必须做三件事:

1. 选择一个基本案例并证明您的声明在该基本案例中是正确的。
2. 假设对于大小不超过 k 的所有问题实例，声明都是正确的。这是一个很强的归纳法，但我们不妨这样做，因为这样可以少担心一件事。
3. 展示下一个更大尺寸的问题实例必须如何保持声明的真实性。

我们的基本情况也可能是空数组和大小为 1 的数组。任何排序算法在这些方面都非常稳定。

归纳假设同样容易陈述:计数排序在所有不超过 k 个元素的数组上都是稳定的。

归纳步骤是棘手的部分。考虑一个大小为 k+1 的数组。这个数组有一个最大的最后一个元素(在按照排序标准最大的元素中，有一个元素出现在数组的最后)。考虑通过从大小为 k+1 的数组中删除此元素并将出现在其右侧的元素向左移动以填充间隙而获得的大小为 k 的数组。根据归纳假设，计数排序在这个大小为 k 的数组上是稳定的。为了证明计数排序在大小为 k+1 个元素的数组上是稳定的，因此我们必须仅证明计数排序不能将最大的最后一个元素放在任何相同大小的元素之前。要证明这是真的，请注意当构造输出数组 B 时，j 假定值 n、n-1、…、1 以降序排列，因此在与我们最大的最后一个元素具有相同值的所有元素中，它会首先到达我们的元素。因此，保证将此元素放置在 B 中的右侧，而不是放置具有相同值的任何其他元素，因为 C[A[j]] 在构造 B 的循环中递减，从不递增。