Re: [請益] 快速排序的問題
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
→
04/17 21:20, , 1F
04/17 21:20, 1F
忘了寫boundary condition orz
→
04/17 21:21, , 2F
04/17 21:21, 2F
這個嚴格來說不是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)
推
04/17 21:45, , 3F
04/17 21:45, 3F
→
04/17 21:48, , 4F
04/17 21:48, 4F
→
04/17 21:49, , 5F
04/17 21:49, 5F
→
04/18 08:48, , 6F
04/18 08:48, 6F
討論串 (同標題文章)
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
-1
10