对于 Ruby 的某些实现,排序是稳定的,但您不应该依赖它。Ruby 的 sort 的稳定性由实现定义。
文档说明
文档 表示您不应该依赖 sort 是稳定的:
结果不能保证稳定。当两个元素比较返回 0 时,元素的顺序是不可预测的。
请注意,这并没有说 sort 是否稳定。它只是说不能保证 sort 是稳定的。任何给定的 Ruby 实现都可能具有稳定的 sort,并且仍然与文档一致。它也可能有不稳定的 sort,或者在任何时间更改 sort 是否稳定。
Ruby 实际上做了什么
此测试代码将打印出 true
(如果 Ruby 的 sort 是稳定的)或 false
(如果不稳定):
Foo = Struct.new(:value, :original_order) do
def <=>(foo)
value <=> foo.value
end
end
size = 1000
unsorted = size.times.map do |original_order|
value = rand(size / 10)
Foo.new(value, original_order)
end
sorted = unsorted.sort
stably_sorted = unsorted.sort_by do |foo|
[foo.value, foo.original_order]
end
p [RUBY_PLATFORM, RUBY_VERSION, RUBY_PATCHLEVEL, sorted == stably_sorted]
这是我在 Linux 系统上安装的所有 Ruby 版本的结果:
["java", "1.8.7", 357, false]
["java", "1.9.3", 551, false]
["java", "2.3.3", 0, true]
["java", "2.5.7", 0, true]
["x86_64-linux", "1.8.7", 374, false]
["x86_64-linux", "1.8.7", 374, false]
["x86_64-linux", "1.8.7", 376, false]
["x86_64-linux", "1.9.3", 392, false]
["x86_64-linux", "1.9.3", 484, false]
["x86_64-linux", "1.9.3", 551, false]
["x86_64-linux", "2.0.0", 643, false]
["x86_64-linux", "2.0.0", 648, false]
["x86_64-linux", "2.1.0", 0, false]
["x86_64-linux", "2.1.10", 492, false]
["x86_64-linux", "2.1.1", 76, false]
["x86_64-linux", "2.1.2", 95, false]
["x86_64-linux", "2.1.3", 242, false]
["x86_64-linux", "2.1.4", 265, false]
["x86_64-linux", "2.1.5", 273, false]
["x86_64-linux", "2.1.6", 336, false]
["x86_64-linux", "2.1.7", 400, false]
["x86_64-linux", "2.1.8", 440, false]
["x86_64-linux", "2.1.9", 490, false]
["x86_64-linux", "2.2.0", 0, true]
["x86_64-linux", "2.2.1", 85, true]
["x86_64-linux", "2.2.2", 95, true]
["x86_64-linux", "2.2.3", 173, true]
["x86_64-linux", "2.2.4", 230, true]
["x86_64-linux", "2.2.5", 319, true]
["x86_64-linux", "2.2.6", 396, true]
["x86_64-linux", "2.3.0", 0, true]
["x86_64-linux", "2.3.1", 112, true]
["x86_64-linux", "2.3.2", 217, true]
["x86_64-linux", "2.3.3", 222, true]
["x86_64-linux", "2.4.0", 0, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.1", 111, true]
["x86_64-linux", "2.4.2", 198, true]
["x86_64-linux", "2.4.5", 335, true]
["x86_64-linux", "2.4.9", 362, true]
["x86_64-linux", "2.5.0", 0, true]
["x86_64-linux", "2.5.3", 105, true]
["x86_64-linux", "2.5.7", 206, true]
["x86_64-linux", "2.6.0", 0, true]
["x86_64-linux", "2.6.2", 47, true]
["x86_64-linux", "2.6.3", 62, true]
["x86_64-linux", "2.6.4", 104, true]
["x86_64-linux", "2.6.5", 114, true]
["x86_64-linux", "2.6.6", 146, true]
["x86_64-linux", "2.7.0", 0, true]
["x86_64-linux", "2.7.1", 83, true]
["x86_64-linux", "2.7.2", 137, true]
["x86_64-linux", "3.0.0", 0, true]
["x86_64-linux", "3.0.0", -1, true]
["x86_64-linux", "3.0.1", 64, true]
["x86_64-linux", "3.0.2", 107, true]
["x86_64-linux", "3.0.3", 157, true]
["x86_64-linux", "3.1.0", 0, true]
["x86_64-linux", "3.1.1", 18, true]
["x86_64-linux", "3.1.2", 20, true]
["x86_64-linux", "3.1.3", 185, true]
["x86_64-linux", "3.2.0", 0, true]
["x86_64-linux", "3.2.1", 31, true]
我们可以看到JRuby不稳定,而MRI在2.2之前在Linux上也不稳定。 在Linux上,MRI> = 2.2.0是稳定的(同样地)。
尽管上述结果显示在Linux上MRI 2.4.1中sort是稳定的,但在Windows上相同版本是不稳定的。
["x64-mingw32", "2.4.1", 111, false]
MRI在Linux上的排序为什么是稳定的,而在Windows上不稳定?
即使在Ruby实现的单个版本中,排序算法也可能会发生变化。MRI至少可以使用三种不同的排序方式。排序例程是在编译时使用util.c中的一系列#ifdefs选择的。看起来MRI有能力使用至少两个不同库的排序。它还有自己的实现。
你应该怎么做?
由于排序可能是稳定的,但不能保证稳定,因此不要编写依赖于Ruby排序稳定性的代码。当在不同的版本、实现或平台上使用时,该代码可能会出现问题。