代码之家 › 专栏 › 技术社区 › Don Mackenzie

如何编写一个惯用的scala快速排序函数?

scala

Don Mackenzie · 技术社区 · 14 年前

我最近回答了 question 尝试在scala中编写QuickSort函数时,我看到了下面的代码。

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

我的回答受到了一些建设性的批评,指出列表对于快速排序来说是一个糟糕的选择,其次,上面的内容并不是尾部递归的。

我试图用递归的方式重新编写上面的内容,但运气不太好。是否可以编写尾部递归快速排序?或者,如果不是的话,如何以一种实用的方式来完成呢?此外,如何才能最大限度地提高实施效率?

4 回复 | 直到 11 年前

Daniel Spiewak 14 年前

几年前,我花了一些时间尽可能地优化功能快速排序。下面是我为香草做的 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中使用最优雅或最惯用的快速排序方法,它正好可以很好地工作。在编写合并排序时,您可能会获得更多的成功,这通常是一种在函数语言中实现的更快的算法(更不用说更干净)。

Daniel C. Sobral 14 年前

我想这取决于你所说的“惯用语”是什么意思。快速排序的主要优点是它是一种非常快速的就地排序算法。所以,如果你不能在适当的地方分类,你就失去了它的所有优势——但是你仍然坚持它 数字化信息系统 优势。

这是我为罗塞塔代码写的一些关于这个主题的代码。它仍然没有进行排序,但是,另一方面,它对任何新的集合进行排序:

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

0xReinventor 12 年前

碰巧,我最近试图解决这个完全相同的问题。我希望将经典算法(即进行就地排序的算法)转换为尾部递归形式。

如果您仍然感兴趣,可以在这里看到我推荐的解决方案:

Quicksort rewritten in tail-recursive form - An example in Scala

本文还包含将初始实现转换为尾部递归形式所遵循的步骤。

Vladimir Kostyukov 11 年前

我做了一些实验,试图用一种纯粹的功能风格来写Quicksort。这是我得到的( Quicksort.scala ):

def quicksort[A <% Ordered[A]](list: List[A]): List[A] = {
  def sort(t: (List[A], A, List[A])): List[A] = t match {
    case (Nil, p, Nil) => List(p)
    case (l, p, g) =>  partitionAndSort(l) ::: (p :: partitionAndSort(g))
  }

  def partition(as: List[A]): (List[A], A, List[A]) = {
    def loop(p: A, as: List[A], l: List[A], g: List[A]): (List[A], A, List[A]) = 
      as match {
        case h :: t => if (h < p) loop(p, t, h :: l, g) else loop(p, t, l, h :: g)
        case Nil => (l, p, g)
      }

    loop(as.head, as.tail, Nil, Nil)
  }

  def partitionAndSort(as: List[A]): List[A] = 
    if (as.isEmpty) Nil
    else sort(partition(as))

  partitionAndSort(list)
}