如何實現尾遞歸快速排序在斯卡拉

我寫了一個遞歸版本：如何實現尾遞歸快速排序在斯卡拉

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。任何人都可以給我一個建議嗎？

來源

2012-02-12 愛國者

你不能 - 算法的思想是在較小的任務中打破工作，遞歸執行它們，然後將結果放在一起。因爲後者是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

任何遞歸函數都可以轉換爲使用堆而不是堆棧來跟蹤上下文。該過程被稱爲trampolining。

以下是Scalaz如何實現它。

object TrampolineUsage extends App { 

    import scalaz._, Scalaz._, Free._ 

    def quickSort[T: Order](xs: List[T]): Trampoline[List[T]] = { 
    assert(Thread.currentThread().getStackTrace.count(_.getMethodName == "quickSort") == 1) 
    xs match { 
     case Nil => 
     return_ { 
      Nil 
     } 
     case x :: tail => 
     val (left, right) = tail.partition(_ < x) 
     suspend { 
      for { 
      ls <- quickSort(left) 
      rs <- quickSort(right) 
      } yield ls ::: (x :: rs) 
     } 
    } 
    } 

    val xs = List.fill(32)(util.Random.nextInt()) 
    val sorted = quickSort(xs).run 
    println(sorted) 

    val (steps, sorted1) = quickSort(xs).foldRun(0)((i, f) => (i + 1, f())) 
    println("sort took %d steps".format(steps)) 
}

當然，你需要使用一個非常大的結構或非常小的堆棧與非尾遞歸鴻溝實際問題和征服算法，因爲你可以處理2種堆棧^ N個元素N的深度

http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html

UPDATE

scalaz.Trampoline是（多）更一般的結構的一種特殊情況，Free 。它被定義爲type Trampoline[+A] = Free[Function0, A]。實際上可以更一般地編寫quickSort，所以它通過Free中使用的類型構造函數進行參數化。這個例子展示了這是如何完成的，以及如何使用相同的代碼來使用堆棧，堆或者同時進行綁定。

https://github.com/scalaz/scalaz/blob/scalaz-seven/example/src/main/scala/scalaz/example/TrampolineUsage.scala

來源

2012-02-12 12:56:22 retronym

'暫停'從哪裏來？ git「蹦牀」上的源代碼在哪裏？我無法找到一個'Trampoline.scala'文件。 – huynhjl 2012-02-12 17:00:05

https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/Free.scala – retronym 2012-02-12 17:05:17

天真的快速排序不保證分而治之。例如，OP的算法在「List.range（0,10000）.reverse」中斷。 – 2012-02-12 17:49:57

尾遞歸要求傳遞工作，已完成和工作待辦事項，在前進的每一步。所以你只需要在工作堆上封裝你的工作而不是堆棧。你可以使用一個列表作爲一個堆棧，這很簡單。下面是一個實現：

def quicksort[T](xs: List[T])(lt: (T,T) => Boolean) = { 
    @annotation.tailrec 
    def qsort(todo: List[List[T]], done: List[T]): List[T] = todo match { 
    case Nil => done 
    case xs :: rest => xs match { 
     case Nil => qsort(rest, done) 
     case x :: xrest => 
     val (ls, rs) = (xrest partition(lt(x,_))) 
     if (ls.isEmpty) { 
      if (rs.isEmpty) qsort(rest, x :: done) 
      else qsort(rs :: rest, x :: done) 
     } 
     else qsort(ls :: List(x) :: rs :: rest, done) 
    } 
    } 
    qsort(List(xs),Nil) 
}

這是當然的，因爲通過返璞詞鏈接到蹦牀的一種特殊情況下（你不需要直傳功能）。幸運的是，這種情況很容易手動完成。

來源

2012-02-12 18:15:42

您的解決方案接縫不正確 – 2012-09-28 16:06:29

我寫這篇文章包含分步說明如何將經典的實現快速排序的轉換爲尾遞歸形式：

Quicksort rewritten in tail-recursive form - An example in Scala

我希望你覺得它很有趣！

來源

2012-09-28 07:35:09 0xReinventor

您必須披露與外部博客帖子的聯繫。還請在答案本身發佈相關內容 - 如果有一天它不可用，鏈接就不好。 – 2012-09-28 19:34:18

如何實現尾遞歸快速排序在斯卡拉

回答

相關問題