Ruby中的排序稳定吗? [英] Is sort in Ruby stable?

问题描述

sort在Ruby中稳定吗?也就是说，对于与sort绑定的元素，它们之间的相对顺序是否保留为原始顺序?例如，给定:

Is sort in Ruby stable? That is, for elements that are in a tie for sort, is the relative order among them preserved from the original order? For example, given:

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

是否可以保证我们始终如一?

is it guaranteed that we always get 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},
]

在具有:id值:d，:f的元素之间以及:b，:e，:g和:c，:h之间的相对顺序没有任何变化?如果是这样，在文档中的什么位置进行了描述?

without any variation for the relative order among the elements with the :id value :d, :f, and among :b, :e, :g, and among :c, :h? If that is the case, where in the documentation is it described?

此问题可能与此问题有关.

推荐答案

MRI 的排序和请求使它们稳定，但被拒绝了.原因:Ruby使用就地快速排序算法，如果不需要稳定性，该算法会表现更好.请注意，您仍然可以从不稳定方法中实现稳定方法:

Both MRI's sort and sort_by are unstable. Some time ago there was a request to make them stable, but it was rejected. The reason: Ruby uses an in-place quicksort algorithm, which performs better if stability is not required. Note that you can still implement stable methods from unstable ones:

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中的排序稳定吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！