ruby - Ruby 中的排序稳定吗？

Question

Ruby 中的 sort 稳定吗？也就是说，对于 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?如果是这样，它在文档的哪个位置进行了描述？

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

Answer 1

两者都是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