Laz*_*zer 17 sorting algorithm stable-sort
假设我的输入是(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
那么,这种稳定的排序如何？我不确定它是如何"用相同的键保持记录的相对顺序".
请解释.
nyb*_*bon 40
要理解为什么计数排序是稳定的,你需要理解计数排序不仅可以用于排序整数列表,它还可以用于排序其键是整数的元素列表,并且这些元素将被排序通过他们的密钥,同时具有与每个密钥相关联的附加信息.
使用附加信息对元素进行排序的计数排序示例将帮助您理解这一点.例如,我们想按价格对三种股票进行排序:
[(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)
正如您所看到的,在数组排序后,counts数组(即[0,0,2,2])不会像整数数组那样成为全零数组.计数数组不用于表示整数出现在未排序数组中的次数,而是用于指示元素在最终排序数组中的位置.而且由于我们每次输出一个元素时都会减少计数,因此我们基本上会使具有相同键的下一个外观最终位置的元素变小.这就是为什么我们需要从后向迭代未排序的数组以确保其稳定性.
结论:
由于每个元素不仅包含一个整数作为键,而且还包含一些附加信息,即使它们的键相同,您也可以通过使用附加信息来判断每个元素是否不同,这样您就可以判断它是否是稳定的排序算法(是的,如果适当实施,它是一个稳定的排序算法).
参考文献:
一些好的材料解释计数排序及其稳定性:
pol*_*nts 14
简单,真的:它不是每个'桶'的简单计数器,而是一个链表.
也就是说,而不是
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)像以前一样.
您的解决方案不是完整计数排序,并丢弃关联的值.
这是完整的计数排序算法.
计算直方图后:
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”，在输出中有三个。谈论它们是否已“重新排序”毫无意义：它们是相同的。
仅当值具有一些不参与该顺序的关联信息时，才会使用非稳定性的概念。例如，如果您正在对指向这些整数的指针进行排序，则可以通过查看它们的不同地址来“讲述三个”之间的差异。那么有意义的是询问任何特定的分类是否稳定。这样，基于整数值的计数排序就不会对指针进行排序。基于指针值的计数排序不会按整数值对它们进行排序，而是按地址对它们进行排序。