假设我的输入是（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
那么，这种稳定的排序如何？我不确定它是如何“用相同的键保持记录的相对顺序”。
请解释。
简单，真的：它不是每个'桶'的简单计数器，而是一个链表。
也就是说，而不是
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)。
要理解为什么计数排序是稳定的，你需要理解计数排序不仅可以用于排序整数列表，它还可以用于排序其键是整数的元素列表，并且这些元素将被排序通过他们的密钥，同时具有与每个密钥相关联的附加信息。
使用附加信息对元素进行排序的计数排序示例将帮助您理解这一点。例如，我们想按价格对三种股票进行排序：
[(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)
如果你只是对一个整数数组进行排序，你可以通过计数数组并输出“1”两次和“3”一次完成它，并且整个计数数组将在此之后变为一个全零数组。
但是在这里我们希望在排序输出中也有股票名称。我们怎样才能获得这些额外的信息（似乎count数组已经丢弃了这条信息）？那么，相关信息存储在原始未排序的数组中。在未排序的数组[（GOOG 3），（CSCO 1），（MSFT 1）]中，我们有股票名称及其价格。如果我们知道最终排序数组中哪个位置（GOOG 3），我们可以将此元素复制到排序数组中的排序位置。
要获取已排序数组中每个元素的最终位置，与排序整数数组不同，不要直接使用counts数组来输出已排序的元素。相反，计数排序还有一个额外的步骤，它计算来自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股票并且其元素被复制到已排序的数组，我们将减少count数组中的计数。
counts array: [0, 1, 2, 3]
(so that the second appearance of $1 price stock's position will be 1)
所以我们可以从后向迭代未排序的数组（这对于确保稳定性很重要），根据计数数组检查它在排序数组中的位置，并将其复制到排序数组。
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)
正如您所看到的，在对数组进行排序之后，count数组（即[0,0,2,2]）不会像整数数组那样成为全零数组。计数数组不用于表示整数出现在未排序数组中的次数，而是用于指示元素在最终排序数组中的位置。而且由于我们每次输出一个元素时都会减少计数，因此我们基本上会使具有相同键的下一个外观最终位置的元素变小。这就是为什么我们需要从后向迭代未排序的数组以确保其稳定性。
结论：
由于每个元素不仅包含一个整数作为键，而且还包含一些附加信息，即使它们的键相同，您也可以通过使用附加信息来判断每个元素是否不同，这样您就可以判断它是否是稳定的排序算法（是的，如果适当实施，它是一个稳定的排序算法）。
参考文献：
一些好的材料解释计数排序及其稳定性：
您的解决方案不是完整计数排序，并丢弃关联的值。
这是完整的计数排序算法。
计算直方图后：
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
如您所见，此算法是一种稳定的排序。将保留具有相同密钥的元素的顺序。
如果你的三个“6”值是可区分的，那么你的计数排序是错误的（它丢弃了有关值的信息，这是真正的排序不能做的，因为真正的排序只重新排序值）。
如果您的三个“6”值无法区分，则排序是稳定的，因为输入中有三个无法区分的“6”，输出中有三个。谈论他们是否已经“重新订购”是毫无意义的：他们是完全相同的。
不稳定的概念仅适用于值具有一些不参与订单的相关信息。例如，如果你正在排序指向这些整数的指针，那么你可以通过查看它们的不同地址来“区分”这三个6。那么询问任何特定种类是否稳定是有意义的。基于整数值的计数排序则不会对指针进行排序。基于指针值的计数排序不会按整数值排序，而是按地址排序。