algorithm – Scala中的通用快速排序

发布时间：2020-12-16 09:02:56 所属栏目：安全来源：网络整理

导读：我最近一直在玩 Scala并且正在考虑如何在其中实现一个通用版本的quicksort(只是为了更好地感受语言) 我想出了类似的东西 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

我最近一直在玩 Scala并且正在考虑如何在其中实现一个通用版本的quicksort(只是为了更好地感受语言)

我想出了类似的东西

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

}

这不像我想要的那样通用,因为我必须明确说明如何对元素进行排序而不是仅仅做类似的事情

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

如何告诉编译器T只需要实现大于运算符,可以通过此函数进行排序？

问候

解决方法

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!