你如何写一个惯用的Scala Quicksort函数？

Question

我最近回答了一个问题,在斯卡拉写一个快速排序功能与尝试,我会看到类似下面的地方写的代码.

def qsort(l: List[Int]): List[Int] = {
  l match {
    case Nil         => Nil
    case pivot::tail => qsort(tail.filter(_ < pivot)) ::: pivot :: qsort(tail.filter(_ >= pivot))
  }
}

我的回答得到了一些建设性的批评,指出List对于quicksort来说是一个糟糕的选择,其次是上面不是尾递归.

我尝试以尾递归的方式重写上面的内容,但没有太多运气.是否可以编写尾递归快速排序？或者,如果没有,如何以功能性的方式完成？还有什么可以做到最大化实施的效率？

Answer 1

几年前,我花了一些时间尝试尽可能地优化功能性快速排序.以下是我为香草提出的建议List[A]:

def qsort[A : Ordering](ls: List[A]) = {
  import Ordered._

  def sort(ls: List[A])(parent: List[A]): List[A] = {
    if (ls.size <= 1) ls ::: parent else {
      val pivot = ls.head

      val (less, equal, greater) = ls.foldLeft((List[A](), List[A](), List[A]())) {
        case ((less, equal, greater), e) => {
          if (e < pivot)
            (e :: less, equal, greater)
          else if (e == pivot)
            (less, e :: equal, greater)
          else
            (less, equal, e :: greater)
        }
      }

      sort(less)(equal ::: sort(greater)(parent))
    }
  }
  sort(ls)(Nil)
}

我可以通过自定义List结构做得更好.这种自定义结构基本上跟踪了列表的理想(或接近理想的)枢轴点.因此,只需访问此特殊列表属性,我就可以在恒定时间内获得更好的枢轴点.实际上,这比选择头部的标准功能方法要好得多.

事实上,上面的内容仍然非常活泼.这是"半"尾递归(你不能做一个尾递归快速排序而不会变得非常丑陋).更重要的是,它首先从尾端重建,因此比传统方法产生的中间列表要少得多.

重要的是要注意,这不是在Scala中进行快速排序的最优雅或最惯用的方式,它恰好工作得非常好.编写合并排序可能会更成功,在函数式语言中实现这通常是一种更快的算法(更不用说更清晰了).

Answer 2

我想这取决于"惯用语"是什么意思.quicksort的主要优点是非常快速的就地排序算法.所以,如果你不能在原地进行排序,你失去所有的优点-但你还是坚持了它的DIS优势.

所以,这里是我为Rosetta Code编写的一些代码.它仍然不会就地排序,但另一方面,它会对任何新集合进行排序:

import scala.collection.TraversableLike
import scala.collection.generic.CanBuildFrom
def quicksort
  [T, CC[X] <: Traversable[X] with TraversableLike[X, CC[X]]]      // My type parameters -- which are expected to be inferred
  (coll: CC[T])                                                    // My explicit parameter -- the one users will actually see
  (implicit ord: Ordering[T], cbf: CanBuildFrom[CC[T], T, CC[T]])  // My implicit parameters -- which will hopefully be implicitly available
  : CC[T] =                                                        // My return type -- which is the very same type of the collection received
  if (coll.isEmpty) {
    coll
  } else {
    val (smaller, bigger) = coll.tail partition (ord.lt(_, coll.head))
    quicksort(smaller) ++ coll.companion(coll.head) ++ quicksort(bigger)
  }