algorithm - 计数排序如何稳定？

Question

假设我的输入是(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

那么，这种稳定的排序方式如何？
我不知道它是如何“用相同的键维护记录的相对顺序”的。

请解释。

Answer 1

确实简单:它是一个链表，而不是每个“桶”的简单计数器。

也就是说，代替

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

也就是说，当您发现一个带有x键的项目时，知道它可能还有其他信息可以将其与具有相同键的其他项目区分开，那么，您不仅会增加存储桶x的计数器(这会丢弃所有这些额外的信息) 。

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

因此，您无需在O(k)计数器中使用k空间，而是让O(k)最初为空列表，其长度总和在算法的“计数”部分的末尾将为n。这种计数排序的变体仍将像以前一样是O(n + k)。