如何将函数insert-sort代码更改为tail递归

Question

最近我通过函数式编程风格实现了insert_sort算法,它变得更加简洁和声明.问题是如何将其更改为尾递归,如果列表的大小增加到10000,代码将抛出异常.

def InsertSort(xs: List[Int]): List[Int] = xs match {
    case Nil => Nil
    case x::rest => 
       def insert (x: Int, sorted_xs:List[Int]) :List[Int] = sorted_xs match{
           case Nil => List(x)
           case y::ys => if  (x <= y) x::y::ys else y::insert(x,ys)
       }
       insert(x,InsertSort(rest))
 }

Answer 1

刚刚介绍累加器:

 @tailrec def InsertSort(xs: List[Int], acc: List[Int] = Nil): List[Int] = 
  if (xs.nonEmpty) {
    val x :: rest = xs
    @tailrec 
    def insert(x: Int, sorted_xs: List[Int], acc: List[Int] = Nil): List[Int] =
      if (sorted_xs.nonEmpty) { 
        val y :: ys = sorted_xs
        if (x <= y) acc ::: x :: y :: ys else insert(x,ys, acc :+ y)
      } else acc ::: List(x)
    InsertSort(rest, insert(x, acc))
  } else acc

:::并将:+O(n)作为默认List实现,因此最好使用一些更合适的集合(如ListBuffer).您也可以使用foldLeft而不是显式递归来重写它.

更快的选择(有foldLeft,没有:+):

 @tailrec
 def insert(sorted_xs: List[Int], x: Int, acc: List[Int] = Nil): List[Int] =
   if (sorted_xs.nonEmpty) { 
     val y::ys = sorted_xs
     if (x <= y) acc.reverse ::: x :: y :: ys else insert(ys, x, y :: acc)
   } else (x :: acc).reverse

 scala> List(1,5,3,6,9,6,7).foldLeft(List[Int]())(insert(_, _))
 res22: List[Int] = List(1, 3, 5, 6, 6, 7, 9)

最后用span(比如在@ roterl的答案中,但span速度要快一些 - 它只会在> x找到之前遍历集合):

 def insert(sorted_xs: List[Int], x: Int) = if (sorted_xs.nonEmpty) { 
    val (smaller, larger) = sorted_xs.span(_ < x)
    smaller ::: x :: larger
 } else x :: Nil

 scala> List(1,5,3,6,9,6,7).foldLeft(List[Int]())(insert)
 res25: List[Int] = List(1, 3, 5, 6, 6, 7, 9)