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
那么，这个稳定排序是如何实现的呢？ 我不确定它是如何“保持相等键值记录的相对顺序”的。
请解释一下。
[(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 array: [0, 2, 2, 3] (i from 0 to 3: counts[i] = counts[i] + counts[i - 1])
counts [1] == 2 意味着当前值为 1 的项应该放置在排序数组的第 2 个插槽中。直观地说，因为 counts [i] 是从左边开始的累计总和，它显示了前面有多少比 ith 值小的项，这告诉您 ith 值的位置应该在哪里。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)
结论：
由于每个元素不仅包含一个整数作为键，还包含一些附加信息，即使它们的键相同，您也可以使用附加信息来判断每个元素是否不同，因此您将能够确定它是否是稳定的排序算法（如果适当实现，则是稳定的排序算法）。
参考资料：
一些解释计数排序及其稳定性的好材料：
非常简单：每个“桶”不再使用简单的计数器，而是使用一个链接列表。
也就是说，与其使用
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的列表末尾。
因此，你不是使用k个计数器的O(k)空间，而是使用k个最初为空的列表，其长度总和在算法的“计数”部分结束时将为n。这个变体的计数排序仍然是以前的O(n+k)。
你的解决方案不是完整的计数排序，并且丢弃了相关的值。
这里是完整的计数排序算法。
在计算直方图之后：
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。小于或等于6的元素有7个。所以6c将进入第7个位置。然后，您会将计数器减去6。0(1) 1(2) 3(3) 4(3) 6(6) 8(8)
^ next 6 will go now to 6th position
正如您所看到的，这个算法是一种稳定排序。具有相同关键字的元素的顺序将被保留。