两者 MRI 的 sort 和 sort_by 是 unstable . 前一段时间有一个 request 使他们稳定下来,但被拒绝了。原因:ruby使用 in-place quicksort algorithm ,如果不需要稳定性,则性能更好。注意,您仍然可以从不稳定的方法实现稳定的方法:

module Enumerable
  def stable_sort
    sort_by.with_index { |x, idx| [x, idx] }
  end

  def stable_sort_by
    sort_by.with_index { |x, idx| [yield(x), idx] }
  end
end

不,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}
]

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

更新:

马茨自己的建议(见 this page )是类似的,并且可能比上面的效率略高:

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

对于Ruby的一些实现,排序是稳定的,但是你不应该依赖它。露比排序的稳定性是定义的实现。

文档说明了什么

The documentation 说你不应该依赖稳定的排序:

结果不能保证稳定。当两个元素的比较返回0时,元素的顺序是不可预测的。

请注意,这并不能说明排序是否稳定。只是说不能保证稳定。任何给定的ruby实现都可以有一个稳定的排序,并且仍然与文档保持一致。它也可能有一个不稳定的排序,或者随时改变排序是否稳定。

鲁比到底做了什么

此测试代码打印 true 如果ruby的排序是稳定的,或者 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]
["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]

我们可以看到JRuby是不稳定的,而Linux上2.2之前的MRI是不稳定的。mri>=2.2.0是稳定的(同样,在Linux上)。

不过,这个平台很重要。虽然在Linux上MRI排序2.4.1的排序是稳定的,但是相同的版本在Windows上是不稳定的:

["x64-mingw32", "2.4.1", 111, false]

为什么MRI在Linux上排序稳定,但在Windows上不稳定?

即使在ruby实现的单一版本中,排序算法也可以更改。核磁共振至少可以使用三种不同的类型。排序例程在编译时使用 util.c 是的。看起来mri至少可以使用两个不同库中的排序。它也有自己的实现。

你该怎么办?

由于排序可能是稳定的,但不能保证是稳定的,所以不要编写依赖于ruby排序是否稳定的代码。当在不同版本、实现或平台上使用时,该代码可能会中断。

就我个人而言,我不会指望这个。不如这样做:

a.sort {|a, b| s1 = a[:int] <=> b[:int]; s1 != 0 ? s1 : a[:id] <=> b[:id] }