arrays - QuickSort 不能应用于 ArrayBuffer 在 Scala 中就地进行排序

Question

我对 Scala 中的 QuickSort 有点困惑。根据规范，QuickSort 只能应用于 Array，而不能应用于 ArrayBuffer。 QuickSort 将在 Place 进行排序，即会更改原始数组。

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)) 性能，导致其他快速排序降级为二次性能，并且通常比传统(单轴)快速排序实现更快。

所以我认为基本的答案是 scala 严重依赖于 Java 的内置快速排序，您可以使用任何 Seq 函数(sorted、sortWith、sortBy)，其性能优于或等于数组快速排序函数。在“复制”阶段您可能会受到一些性能影响，但类只是指针(它不是克隆对象)，因此除非您拥有数百万个项目，否则您不会损失太多。