Scala排序稳定吗？ [英] Is scala sorting stable?

问题描述

Scala集合具有 sortBy 方法。该方法稳定吗？

Scala collections have sortBy method. Is that method stable?

def sortList(source : List[Int]) : List[Int] =
  source.sortBy(_ % 2)

该示例是否始终保留订单？

Would that example always preserve order?

推荐答案

是的，它很稳定。来自scala源代码的引用：

Yes, it's stable. Reference from scala source code:

https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/SeqLike.scala#L627

def sortBy[B](f: A => B)(implicit ord: Ordering[B]): Repr = sorted(ord on f)

/** Sorts this $coll according to an Ordering.
 *
 *  The sort is stable. That is, elements that are equal (as determined by
 *  `lt`) appear in the same order in the sorted sequence as in the original.
 *
 *  @see [[scala.math.Ordering]]
 *
 *  @param  ord the ordering to be used to compare elements.
 *  @return     a $coll consisting of the elements of this $coll
 *              sorted according to the ordering `ord`.
 */
def sorted[B >: A](implicit ord: Ordering[B]): Repr = {
  val len = this.length
  val b = newBuilder
  if (len == 1) b ++= this
  else if (len > 1) {
    b.sizeHint(len)
    val arr = new Array[AnyRef](len)  // Previously used ArraySeq for more compact but slower code
    var i = 0
    for (x <- this) {
      arr(i) = x.asInstanceOf[AnyRef]
      i += 1
    }
    java.util.Arrays.sort(arr, ord.asInstanceOf[Ordering[Object]])
    i = 0
    while (i < arr.length) {
      b += arr(i).asInstanceOf[A]
      i += 1
    }
  }
  b.result()
}

这篇关于Scala排序稳定吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！