在Ruby中稳定？
在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}, ]
是保证，我们总是得到
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}, ]
元素之间的相对顺序没有任何变化:id值:d ， :f ，其中:b ， :e ， :g ，其中:c ， :h ？ 如果是这样的话，在文档中描述的地方是什么？
这个问题可能会或可能不会与这个问题有关 。
MRI的sorting和sorting都不稳定 。 前一段时间有一个要求使它们稳定的请求 ，但是被拒绝了; 原因是Ruby使用了原地快速sortingalgorithm ，如果不需要稳定性，那么它的性能会更好。 请注意，您仍然可以从不稳定的方法实现稳定的方法：
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的内置sorting不稳定。
如果你想稳定sorting，这应该工作。 如果你打算经常使用它，你可能想创build一个方法。
a.each_with_index.sort_by {|h, idx| [h[:int], idx] }.map(&:first)
基本上，它跟踪每个项目的原始数组索引，并且当h[:int]相同时将其用作打破平局。
更多信息，对于好奇：
据我所知，使用原始数组索引作为决胜是保证使用不稳定sorting时稳定的唯一方法。 项目的实际属性（或其他数据）不会告诉你它们的原始顺序。
你的例子有点做作，因为:id键在原始数组中按升序sorting。 假设原始数组按照:idsorting: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} ]
使用原始索引也会处理这个。
更新：
马茨自己的build议（见本页 ）是相似的，可能会比上面更有效率：
n = 0 ary.sort_by {|x| n+= 1; [x, n]}
对于Ruby的一些实现，sorting是稳定的，但是你不应该依赖它。 Ruby的sorting稳定性是实现定义的。
什么文件说
文件说，你不应该依赖稳定的sorting：
结果不能保证稳定。 当两个元素的比较返回0时，元素的顺序是不可预知的。
请注意，这并不说明sorting是否稳定。 它只是说它不能保证稳定。 任何给定的Ruby实现可以有一个稳定的sorting，并仍然与文档一致。 它也可能有一个不稳定的sorting，或者随时改变sorting是否稳定。
Ruby实际上做了什么
如果Ruby的sorting是稳定的，这个testing代码将打印true如果不是，
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是不稳定的，在2.2之前的Linux上，MRI是不稳定的。 MRI> = 2.2.0是稳定的（再次，在Linux上）。
但是平台很重要。 虽然上面的结果表明在Linux上MRI 2.4.1中的sorting是稳定的，但在Windows上相同的版本是不稳定的：
["x64-mingw32", "2.4.1", 111, false]
为什么在Linux上MRI的sorting是稳定的，但在Windows上却不行？
即使在一个Ruby实现的单一版本中，sortingalgorithm也可以改变。 MRI可以使用至less三种不同的种类。 sorting例程在编译时使用util.c中的一系列#ifdefs来select。 它看起来像MRI有能力使用至less从两个不同的图书馆sorting。 它也有自己的实现。
你应该怎么做？
由于sorting可能是稳定的，但不能保证稳定，所以不要编写依赖Rubytypes稳定的代码。 在不同的版本，实现或平台上使用时，该代码可能会中断。
我个人不会指望这一点。 如何做这样的事情：
a.sort {|a, b| s1 = a[:int] <=> b[:int]; s1 != 0 ? s1 : a[:id] <=> b[:id] }
