无法将QuickSort应用于ArrayBuffer以在Scala中进行排序

Question

我对Scala中的QuickSort很困惑.根据规范,QuickSort只能应用于Array,但不能应用于ArrayBuffer.并且QuickSort将在场中进行排序,即将更改原始阵列.

val intArray = Array(7,1,4,6,9)           //> intArray  : Array[Int] = Array(7, 1, 4, 6, 9)
Sorting.quickSort(intArray)
intArray.mkString("<"," and ",">")        //> res4: String = <1 and 4 and 6 and 7 and 9>

现在我无法理解为什么我不能用ArrayBuilder做同样的事情.这背后有什么理由吗？如果我想用QuickSort算法对ArrayBuilder进行排序,那么scala提供的选项是什么？谢谢你的帮助.

Answer 1

我相信你的问题的答案可以通过检查Scala的源代码找到,以确定你可以从ArrayBuffer附带的内置函数中获得什么行为:sortWith,sortBy等.

这些函数来自定义特征"SeqLike"(您可以通过在ScalaDoc中浏览到该类来检查源代码,然后单击源代码旁边的链接:文档顶部的"Seqlike".

无论如何大多数与排序相关的代码都被推掉了这个函数:

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

这基本上是复制数组并使用Java.util.Arrays.Sort对其进行排序.所以下一个问题就变成了,"这里的Java做什么？" 我好奇,api描述:

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

所以我认为基本的答案是scala在很大程度上依赖于Java的内置快速排序,你可以使用任何Seq函数(sorted,sortWith,sortBy),其性能优于或等于数组快速排序函数.你可能会在"复制"阶段获得一点性能,但是类只是指针(它不是克隆对象)所以除非你拥有数百万个项目,否则你不会失去太多.