我写了一个递归版本:如何实现尾递归快速排序在斯卡拉
def quickSort[T](xs: List[T])(p: (T, T) => Boolean): List[T] = xs match{
case Nil => Nil
case _ =>
val x = xs.head
val (left, right) = xs.tail.partition(p(_, x))
val left_sorted = quickSort(left)(p)
val right_sorted = quickSort(right)(p)
left_sorted ::: (x :: right_sorted)
}
但我不知道如何把它变成尾recurisive。任何人都可以给我一个建议吗?
你不能 - 算法的思想是在较小的任务中打破工作,递归执行它们,然后将结果放在一起。因为后者是nessecarily在快速排序中最后一个thibg,它不能是尾递归。 – Ingo 2012-02-12 08:45:16
这个类似的问题,但在OCaml可能会帮助:http://stackoverflow.com/questions/5634083/implementing-a-tail-recursive-version-of-quick-sort-in-f-ocaml – perelman 2012-02-12 08:47:00
对不起,我不不知道OCaml – 2012-02-12 08:47:41