计数排序如何稳定？ [英] How is counting sort a stable sort?

问题描述

假设我的输入是（ a ， b 和 c 区分相等的键）

Suppose my input is (a,b and c to distinguish between equal keys)

1 6a 8 3 6b 0 6c 4

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

My counting sort will save as (discarding the a,b and c info!!)

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

这将给我结果

0 1 3 4 6 6 6 8

那么，这种稳定的排序方式如何？
我不确定它是如何用相同的键保持记录的相对顺序。

So, how is this stable sort? I am not sure how it is "maintaining the relative order of records with equal keys."

请解释一下。

推荐答案

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

Simple, really: instead of a simple counter for each 'bucket', it's a linked list.

即，而不是

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

您会得到

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

（这里我用。表示存储桶中的某些项目）。

(here I use . to denote some item in the bucket).

然后将它们倒回一个排序的列表中：

Then just dump them back into one sorted list:

0 1 3 4 6a 6b 6c 8

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

That is, when you find an item with key x, knowing that it may have other information that distinguishes it from other items with the same key, you don't just increment a counter for bucket x (which would discard all those extra information).

相反，每个存储桶的nked列表（或具有固定时间摊销的类似顺序的数据结构），然后在扫描输入时将该项目附加到存储桶 x 的列表末尾从左到右。

Instead, you have a linked list (or similarly ordered data structure with constant time amortized append) for each bucket, and you append that item to the end of the list for bucket x as you scan the input left to right.

因此，不要使用 O（k）空间作为 k 计数器，您有 O（k）最初为空列表，其长度总和为 n 在算法计数部分的末尾。计数排序的这种变体仍将像以前一样是 O（n + k）。

So instead of using O(k) space for k counters, you have O(k) initially empty lists whose sum of lengths will be n at the end of the "counting" portion of the algorithm. This variant of counting sort will still be O(n + k) as before.

这篇关于计数排序如何稳定？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！