Lazy Quicksort tại Scala

Question

Có thể thực hiện this điều gì đó trong Scala không?

Answer 1

Có!

Scala hỗ trợ "lazy vals" như một cách để hoãn tính toán giá trị cho đến khi nó thực sự được sử dụng. Phần lớn thư viện Scala 2.8 có khả năng làm việc với các bộ sưu tập được xác định lười biếng.

Answer 2

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

Nó có thể được thực hiện với quan điểm là tốt, mặc dù đó là ràng buộc để được chậm hơn nhiều:

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