46

sortRuby 稳定吗？也就是说，对于与 并列的元素，它们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元素之间的相对顺序没有任何变化 如果是这种情况，文档在哪里描述？

这个问题可能与这个问题有关，也可能无关。

4

4 回答 4

60

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

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
于 2013-03-15T22:17:11.690 回答
18

不，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]}
于 2013-03-21T16:10:26.310 回答
11

对于 Ruby 的某些实现，排序是稳定的，但您不应该依赖它。Ruby 排序的稳定性是由实现定义的。

文件说什么

文档说你不应该依赖排序是稳定的：

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

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

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]
["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]

我们可以看到 JRuby 是不稳定的，2.2 之前的 MRI 在 Linux 上是不稳定的。MRI >= 2.2.0 是稳定的（同样，在 Linux 上）。

不过，平台很重要。虽然上面的结果表明，在 Linux 上的 MRI 2.4.1 中排序是稳定的，但在 Windows 上相同的版本是不稳定的：

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

为什么 MRI 的排序在 Linux 上是稳定的，而在 Windows 上却不是？

即使在单个版本的 Ruby 实现中，排序算法也可以改变。MRI可以使用至少三种不同的类型。排序例程是在编译时使用util.c中的一系列 #ifdefs 选择的。看起来 MRI 能够使用来自至少两个不同库的排序。它也有自己的实现。

你应该怎么做？

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

于 2017-06-11T17:14:55.893 回答
-4

我个人不会指望这一点。如何做这样的事情：

a.sort {|a, b| s1 = a[:int] <=> b[:int]; s1 != 0 ? s1 : a[:id] <=> b[:id] }
于 2013-03-15T21:49:13.560 回答