Scala的Lazy Quicksort [英] Lazy Quicksort in Scala

问题描述

是否可以在Scala中进行这种事情 ?

Is it possible to do this sort of thing in Scala?

推荐答案

def quicksort[A](xs: Stream[A])(implicit o: Ordering[A]): Stream[A] = {
  import o._ 
  if (xs.isEmpty) xs else {
      val (smaller, bigger) = xs.tail.partition(_ < xs.head)
      quicksort(smaller) #::: xs.head #:: quicksort(bigger)
  }
}

它也可以用视图来完成，尽管它肯定会慢得多:

It can be done with views as well, though it's bound to be much slower:

def quicksort[A](xs: List[A])(implicit o: Ordering[A]) = {
  import o._
  def qs(xs: SeqView[A, List[A]]): SeqView[A, Seq[_]] = if (xs.isEmpty) xs else {
    val (smaller, bigger) = xs.tail.partition(_ < xs.head)
    qs(smaller) ++ (xs.head +: qs(bigger))
  }
  qs(xs.view)
}

这篇关于Scala的Lazy Quicksort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！