Scala 库方法 Vector.sorted 使用什么算法? [英] What algorithm is used by the Scala library method Vector.sorted?

问题描述

我一直在查看 Scala 文档 但到目前为止我还没有找到我的问题的答案，即该方法使用什么排序算法

I have been looking at the Scala documentation but so far I have found no answer to my question, namely what sorting algorithm is used by the method

scala.collection.immutable.Vector.sorted

文档说它是一种稳定的排序，但不是实际使用的算法.是归并排序吗?

The documenation says it is a stable sort, but not the actual algorithm used. Is it a merge sort?

推荐答案

sorted 方法是在 SeqLike 中实现的，似乎使用了 java.util.Arrays.sort 用于排序.它从向量构建一个数组，然后调用 Arrays.sort 然后将其转换回来，看起来.根据 Java 6 文档，因此它使用quicksort:

The sorted method is implemented in SeqLike, and seems to use java.util.Arrays.sort for its sorting. It builds an array from the vector, then invokes Arrays.sort and then converts it back, it seems. According to the Java 6 documentation, it therefore uses quicksort:

排序算法是一种经过调整的快速排序，改编自 Jon L. Bentley 和 M. Douglas McIlroy 的设计排序功能"，软件实践和经验，卷.23(11) P. 1249-1265(1993 年 11 月).该算法在许多数据集上提供 n*log(n) 性能，导致其他快速排序降级为二次性能.

The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

对于 Java 7，算法似乎发生了变化(再次引用 文档):

For Java 7, the algorithm seems to have change (again, citing the docs):

排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 的双轴快速排序.该算法在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序降级为二次性能，并且通常比传统(单轴)快速排序实现更快.

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

Scala 的 SeqLike#sorted 源 (取自 GitHub):

Scala's SeqLike#sorted source (taken from GitHub):

/** 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 arr = new ArraySeq[A](len)
    var i = 0
    for (x <- this.seq) {
      arr(i) = x
      i += 1
    }
    java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]])
    val b = newBuilder
    b.sizeHint(len)
    for (x <- arr) b += x
    b.result
  }

这篇关于Scala 库方法 Vector.sorted 使用什么算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！