5

我对 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 提供的选项是什么？感谢所有帮助。

4

1 回答 1

5

我相信可以通过检查 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 的 Dual-Pivot Quicksort。该算法在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序降低到二次性能，并且通常比传统的（单轴）快速排序实现更快。

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

于 2013-08-25T18:47:21.670 回答