Một quicksort chung trong Scala

Question

Tôi đã được chơi đùa với Scala thời gian gần đây và đã suy nghĩ về làm thế nào để thực hiện một phiên bản generic của quicksort trong nó (chỉ để có được một cảm giác tốt hơn cho ngôn ngữ)

tôi đã đưa ra một cái gì đó như thế này

object Main { 
    def qs[T](a: List[T], f: (T, T) => Boolean): List[T] = { 
    if (a == Nil) return a 
    val (l, g) = a drop 1 partition (f(a(0),(_:T))) 
    qs(l, f) ::: List(a(0)) ::: qs(g, f) 
    } 

    def main(args: Array[String]): Unit = { 
    val a = List(5,3,2,1,7,8,9,4,6) 
    val qsInt = qs(_: List[Int], (_: Int) > (_: Int)) 
    println(qsInt(a)) 
    } 

} 

Đây không phải là chung chung kiểu như tôi muốn nó được, vì tôi phải nói rõ làm thế nào để đặt hàng các yếu tố chứ không phải sau đó chỉ cần làm một cái gì đó giống như

val (l, g) = a drop 1 partition (a(0) >) 

Làm thế nào tôi có thể nói với trình biên dịch rằng T chỉ cần thực hiện toán tử lớn hơn để có thể sắp xếp theo hàm này?

Trân

Answer 1

def qsort[T <% Ordered[T]](list: List[T]): List[T] = { 
    list match { 
    case Nil => Nil  
    case x::xs =>   
    val (before, after) = xs partition (_ < x) 
    qsort(before) ++ (x :: qsort(after)) 
    } 
} 

Answer 2

Kể từ Rogercovered trường hợp Ordered, hãy để tôi trang trải Ordering:

def qsort[T](list: List[T])(implicit ord: Ordering[T]): List[T] = list match { 
    // import ord._ // enables "_ < x" syntax 
    case Nil => Nil 
    case x :: xs => 
    val (before, after) = xs partition (ord.lt(_, x)) 
    qsort(before) ::: x :: qsort(after) 
} 

Sử dụng Ordering có hai ưu điểm chính:

1. Loại T không cần có ong n được tạo thành Ordered.
2. Người ta có thể dễ dàng cung cấp thứ tự thay thế.

Ví dụ, trên Scala 2.8:

def sortIgnoreCase(strs: List[String]) = { 
    val myOrdering = Ordering.fromLessThan { (x: String, y: String) => 
    x.toLowerCase < y.toLowerCase 
    } 
    qsort(strs)(myOrdering) 
}