22

假设我的输入是 ( a,b并c区分相等的键)

1 6a 8 3 6b 0 6c 4

我的计数排序将另存为（丢弃a,b和c信息！！）

0(1) 1(1) 3(1) 4(1) 6(3) 8(1)

这会给我结果

0 1 3 4 6 6 6 8

那么，这种稳定的排序如何？我不确定它是如何“保持具有相等键的记录的相对顺序”的。

请解释。

4

4 回答 4

47

要理解计数排序为什么是稳定的，你需要了解计数排序不仅可以用于对整数列表进行排序，还可以用于对键为整数的元素列表进行排序，这些元素将被排序通过他们的密钥，同时拥有与他们每个人相关的附加信息。

使用附加信息对元素进行排序的计数排序示例将帮助您理解这一点。例如，我们想按价格对三只股票进行排序：

[(GOOG 3), (CSCO 1), (MSFT 1)]

这里股票价格是整数键，股票名称是它们的相关信息。

排序的预期输出应该是：

[(CSCO 1), (MSFT 1), (GOOG 3)] 
(containing both stock price and its name,
and the CSCO stock should appear before MSFT so that it is a stable sort)

将计算一个计数数组来对此进行排序（假设股票价格只能是 0 到 3）：

counts array: [0, 2, 0, 1] (price "1" appear twice, and price "3" appear once)

如果你只是对一个整数数组进行排序，你可以遍历counts数组，输出两次“1”和一次“3”就完成了，之后整个counts数组就会变成一个全零数组。

但是在这里，我们也希望在排序输出中包含股票名称。我们如何才能获得这些附加信息（似乎 counts 数组已经丢弃了这条信息）？好吧，相关信息存储在原始未排序数组中。在未排序的数组 [(GOOG 3), (CSCO 1), (MSFT 1)] 中，我们有可用的股票名称和价格。如果我们知道最终排序数组中的哪个位置（GOOG 3），我们可以将此元素复制到排序数组中的排序位置。

要获得排序数组中每个元素的最终位置，与排序整数数组不同，您不直接使用 counts 数组来输出排序后的元素。相反，计数排序有一个额外的步骤，它从计数数组计算累积和数组：

counts array: [0, 2, 2, 3] (i from 0 to 3: counts[i] = counts[i] + counts[i - 1])

这个累积和数组告诉我们每个值当前在最终排序数组中的位置。例如，counts[1]==2表示当前具有值的项目1应放置在2nd已排序数组的槽中。直观地说，因为counts[i]是从左边算起的累积和，它显示了值之前有多少较小的项目ith，它告诉您该值的位置应该在哪里ith。

如果价格为 1 美元的股票第一次出现，则应输出到排序数组的第二个位置，如果价格为 3 美元的股票第一次出现，则应输出到排序数组的第三个位置。如果出现 1 美元的股票并且它的元素被复制到排序数组中，我们将减少它在 counts 数组中的计数。

counts array: [0, 1, 2, 3] 
(so that the second appearance of $1 price stock's position will be 1)

所以我们可以从后向迭代未排序的数组（这对保证稳定性很重要），根据counts数组检查其在排序数组中的位置，并将其复制到排序数组中。

sorted array: [null, null, null]
counts array: [0, 2, 2, 3]    

iterate stocks in unsorted stocks from backwards
1. the last stock (MSFT 1)
sorted array: [null, (MSFT 1), null] (copy to the second position because counts[1] == 2)
counts array: [0, 1, 2, 3] (decrease counts[1] by 1)

2. the middle stock (CSCO 1)
sorted array: [(CSCO 1), (MSFT 1), null] (copy to the first position because counts[1] == 1 now)
counts array: [0, 0, 2, 3] (decrease counts[1] by 1)

3. the first stock (GOOG 3)
sorted array: [(CSCO 1), (MSFT 1), (GOOG 3)] (copy to the third position because counts[3] == 3)
counts array: [0, 0, 2, 2] (decrease counts[3] by 1)

如您所见，在数组排序后，counts 数组（即 [0, 0, 2, 2]）不会像排序整数数组那样变成全零数组。counts 数组不是用来告诉整数在未排序数组中出现的次数，而是用来告诉元素应该在最终排序数组中的哪个位置。而且由于我们每次输出元素时都会减少计数，因此我们实质上是使具有相同键的元素的下一次出现最终位置更小。这就是为什么我们需要从反向迭代未排序的数组以确保其稳定性。

结论：

由于每个元素不仅包含一个整数作为键，还包含一些附加信息，即使它们的键相同，您也可以通过附加信息来判断每个元素是不同的，这样您就可以判断它是否稳定排序算法（是的，如果实施得当，它是一种稳定的排序算法）。

参考：

一些解释计数排序及其稳定性的好材料：

于 2013-06-14T14:59:54.100 回答
18

真的很简单：它不是每个“桶”的简单计数器，而是一个链表。

也就是说，而不是

0(1) 1(1) 3(1) 4(1) 6(3) 8(1)

你得到

0(.) 1(.) 3(.) 4(.) 6(a,b,c) 8(.)

（这里我.用来表示桶中的一些项目）。

然后将它们转储到一个排序列表中：

0 1 3 4 6a 6b 6c 8

也就是说，当您找到一个带有 key 的项目时x，知道它可能有其他信息将其与其他具有相同键的项目区分开来，您不只是增加存储桶的计数器x（这将丢弃所有这些额外信息）。

相反，您对每个存储桶都有一个链接列表（或具有恒定时间摊销附加的类似排序的数据结构），并且在x您从左到右扫描输入时将该项目附加到存储桶列表的末尾。

因此，不是为计数器使用O(k)空间，而是最初有空列表，其长度总和将位于算法的“计数”部分的末尾。这种计数排序的变体仍将与以前一样。kO(k)nO(n + k)

于 2010-04-03T18:24:42.250 回答
8

您的解决方案不是完全计数排序，并且会丢弃关联的值。

这是完整的计数排序算法。

计算直方图后：

0(1) 1(1) 3(1) 4(1) 6(3) 8(1)

您必须计算累计和 - 每个单元格将包含多少元素小于或等于该值：

0(1) 1(2) 3(3) 4(4) 6(7) 8(8)

现在您从原始列表的末尾开始，然后倒退。

最后一个元素是4. 有 4 个元素小于或等于 4。所以4将排在第 4 位。您将计数器递减4.

0(1) 1(2) 3(3) 4(3) 6(7) 8(8)

下一个元素是6c。有 7 个元素小于或等于 6。所以6c将转到第 7 个位置。同样，您将计数器递减6.

0(1) 1(2) 3(3) 4(3) 6(6) 8(8)
                      ^ next 6 will go now to 6th position

正如你所看到的，这个算法是一个稳定的排序。具有相同键的元素的顺序将被保留。

于 2013-03-12T23:09:54.520 回答
6

如果您的三个“6”值是可区分的，那么您的计数排序是错误的（它会丢弃有关值的信息，而真正的排序不会这样做，因为真正的排序只会重新排序值）。

如果您的三个“6”值无法区分，那么排序是稳定的，因为您在输入中有三个无法区分的“6”，在输出中有三个。谈论它们是否被“重新排序”是没有意义的：它们是相同的。

非稳定性的概念仅适用于当值具有一些不参与订单的相关信息时。例如，如果您正在对指向这些整数的指针进行排序，那么您可以通过查看三个 6 的不同地址来“区分”它们。那么询问任何特定类型是否稳定将是有意义的。然后，基于整数值的计数排序不会对指针进行排序。基于指针值的计数排序不会按整数值排序，而是按地址排序。

于 2010-04-04T00:09:44.373 回答