作者dryman (dryman)
看板CSSE
标题Re: [请益] 快速排序的问题
时间Tue Apr 17 15:12:19 2012
yauhh大写的方法还蛮清楚的
提供一个有用accumulator来减少++的版本：
qsort [] acc = acc
qsort [x] acc = x:acc -- one element case
qsort (x:xs) acc = partition xs [] [x] []
where
partition [] less equal greater = qsort less (equal ++ (qsort greater acc))
partition (y:ys) less equal greater
| y > x = partition ys less equal (y:greater)
| y < x = partition ys (y:less) equal greater
| otherwise = partition ys less (y:equal) greater
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.109.22.88
1F：→ Favonia:忘了 [] 的 case... 然後用 partition 省 ++ 不一定有好处 04/17 21:20
忘了写boundary condition orz
2F：→ Favonia:看似 tail recursion 但 acc 还是有一堆 ++ 等着算 xDDDDD 04/17 21:21
这个严格来说不是tail recursion，因为还是得暂存less的值
只是随着执行时间它的stack会小於N（因为被推到ACC里面去了）
而用++的stack会一直差不多等於N
※ 编辑: dryman 来自: 220.136.176.35 (04/17 21:32)
※ 编辑: dryman 来自: 220.136.176.35 (04/17 21:39)
3F：推 Favonia:我觉得你不能用其他程式语言的执行顺序来理解 Haskell... 04/17 21:45
4F：→ Favonia:前者 stack 大小的期望值和後者 acc 大小的期望值只差常数 04/17 21:48
5F：→ Favonia:GHC 的预设实作中不会用到的部份根本不会算，这是重点。 04/17 21:49
6F：→ dryman:哈，我其实比较熟的FP语言是scrict而不是lazy 04/18 08:48