logo标签列表

Ruby中的sort方法是否稳定？

rubysorting
48

sort在Ruby中是稳定的吗？也就是说，对于那些在sort中并列的元素，它们之间的相对顺序是否与原始顺序相同？例如，给定以下内容：

a = [
  {id: :a, int: 3},
  {id: :b, int: 1},
  {id: :c, int: 2},
  {id: :d, int: 0},
  {id: :e, int: 1},
  {id: :f, int: 0},
  {id: :g, int: 1},
  {id: :h, int: 2},
]

我们是否保证始终获得for？

a.sort_by{|h| h[:int]}

以下内容

[
  {id: :d, int: 0},
  {id: :f, int: 0},
  {id: :b, int: 1},
  {id: :e, int: 1},
  {id: :g, int: 1},
  {id: :c, int: 2},
  {id: :h, int: 2},
  {id: :a, int: 3},
]

如果对于具有:d、:f值的元素以及:b、:e、:g值的元素和:c、:h值的元素之间的相对顺序没有任何变化，那么这种情况在文档的哪个部分中进行了描述？

这个问题可能与这个问题有关。

13
有些排序算法是稳定的。 - mu is too short
我得到了这个答案：[{:id=>:f, :int=>0}, {:id=>:d, :int=>0}, {:id=>:e, :int=>1}, {:id=>:b, :int=>1}, {:id=>:g, :int=>1}, {:id=>:c, :int=>2}, {:id=>:h, :int=>2}, {:id=>:a, :int=>3}] - beck03076
我认为真正的答案是“未指定，因此取决于实现”。 - mu is too short
@muistooshort，我刚意识到这在MRI中并不是保证的，这应该是常态。感谢您让我了解这个术语。 - sawa
在 Windows 7 上使用 MRI 2.3.0 没有问题。 - peter
显示剩余5条评论
4个回答
65

无论是MRI的sort还是sort_by都是不稳定的。一段时间以前有一个请求使它们变得稳定，但被拒绝了。原因是：Ruby使用的是就地快速排序算法，如果不需要稳定性，则性能更好。请注意，您仍然可以从不稳定的方法中实现稳定的方法：

module Enumerable
  def stable_sort_by
    sort_by.with_index { |x, idx| [yield(x), idx] }
  end
end
1
引用Wikipedia的话：“快速排序是一种比较排序算法，在高效实现中，它不是稳定排序。” - Stefan
3
此外，如果任何排序实现在其契约中没有明确说明它是稳定的，那么依赖它是稳定的行为总是错误的。 - dbenhur
1
你的 stable_sort 实现没有遵守接受比较器的 sort 签名。 - John Dvorak
1
Ruby的排序有时候是稳定的（但你不应该依赖它）。我认为这种有时稳定的情况在这个答案被创建时并不存在。请参阅我的答案以获取详细信息。 - Wayne Conrad
20
不，Ruby自带的排序不是稳定的。如果你需要稳定的排序，可以使用以下代码。如果你经常使用它，最好为它创建一个方法。
a.each_with_index.sort_by {|h, idx| [h[:int], idx] }.map(&:first)

基本上，它跟踪每个项目的原始数组索引，并在h[:int]相同时将其用作决胜卡。

更多信息，供好奇者参考：

据我所知，在使用不稳定排序时，使用原始数组索引作为决胜者是确保稳定性的唯一方法。项目的实际属性（或其他数据）无法告诉您它们的原始顺序。

您的示例有些人为，因为:id键在原始数组中按升序排序。假设原始数组按:id降序排序；您希望在决胜时结果中的:id也按降序排列：

[
 {:id=>:f, :int=>0},
 {:id=>:d, :int=>0},
 {:id=>:g, :int=>1},
 {:id=>:e, :int=>1},
 {:id=>:b, :int=>1},
 {:id=>:h, :int=>2},
 {:id=>:c, :int=>2},
 {:id=>:a, :int=>3}
]

使用原始索引也可以处理这个问题。

更新：

Matz自己的建议（请参见此页面）与上述方法类似，可能比上述方法稍微更有效：

n = 0
ary.sort_by {|x| n+= 1; [x, n]}
16

对于 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排序稳定性的代码。当在不同的版本、实现或平台上使用时，该代码可能会出现问题。

1
“恰好是”稳定的与“保证是”稳定的完全不同。除非你想在更改Ruby版本或平台时出现无预警的错误，否则我的建议是忽略那些偶然稳定的实现。 - Dave Slutzkin
@DaveSlutzkin 我同意。我说过这句话（“但你不应该依赖它”），但如果你没有听懂，那可能是我表达不够清楚。我会加上更多的话。 - Wayne Conrad
-4

就我个人而言，我不会指望这个。不如试试这样做：

a.sort {|a, b| s1 = a[:int] <=> b[:int]; s1 != 0 ? s1 : a[:id] <=> b[:id] }
4
这既没有回答我的问题，也不会得出跟我的问题是肯定回答一样的结果。 - sawa
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接