Scala库方法Vector.sorted使用什么算法？

发布时间：2020-12-16 08:50:04 所属栏目：安全来源：网络整理

导读：我一直在看 Scala documentation,但到目前为止我没有找到我的问题的答案,即该方法使用了什么排序算法 scala.collection.immutable.Vector.sorted 该文档说它是一种稳定的排序,但不是实际使用的算法.它是合并排序吗？解决方法已排序的方法在SeqLike中实现,

我一直在看 Scala documentation,但到目前为止我没有找到我的问题的答案,即该方法使用了什么排序算法

scala.collection.immutable.Vector.sorted

该文档说它是一种稳定的排序,但不是实际使用的算法.它是合并排序吗？

解决方法

已排序的方法在SeqLike中实现,并且似乎使用java.util.Arrays.sort进行排序.它从向量构建一个数组,然后调用Arrays.sort,然后将其转换回来.根据 Java 6 documentation,它因此使用quicksort：

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,该算法似乎有所改变(再次引用the docs)：

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!