6

我正在学习haskell，我看到的函数定义是： 

quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
                 where less = filter (< x) xs
                       equal = filter (== x) xs
                       more = filter (> x) xs

是否可以只遍历列表一次而不是 3 次来编写它？

4

3 回答 3

13

你的意思是这样的？

quicksort [] = []
quicksort (x:xs) = quicksort less ++ (x : equal) ++ quicksort more
  where (less, equal, more) = partition3 x xs

partition3 _ [] = ([], [], [])
partition3 x (y:ys) =
  case compare y x of
    LT -> (y:less, equal, more)
    EQ -> (less, y:equal, more)
    GT -> (less, equal, y:more)
  where (less, equal, more) = partition3 x ys

请注意，这并不是真正的快速排序，因为真正的快速排序是就地的。

于 2011-10-04T00:17:36.933 回答
9

它似乎没有任何改善，但：

qs (x:xs) = let (a,b) = partition (< x) xs in (qs a) ++ [x] ++ (qs b)
于 2011-10-04T00:11:04.927 回答
8

虽然晚了，但这里的版本应该不会泄漏太多空间（并且似乎比这里的其他 3 路版本快两倍）：

qsort3 xs = go xs [] 
  where
    go     (x:xs) zs       = part x xs zs [] [] []
    go     []     zs       = zs
    part x []     zs a b c = go a ((x : b) ++ go c zs)
    part x (y:ys) zs a b c =
        case compare y x of
                  LT -> part x ys zs (y:a) b c
                  EQ -> part x ys zs a (y:b) c
                  GT -> part x ys zs a b (y:c)

这解决了使用元组可能出现的问题，其中let (a,b) = ...实际翻译成let t= ...; a=fst t; b=snd t哪个导致即使在a被消耗和处理之后，它仍然保持活动状态，作为 tuple 的一部分t，b以便从中读取 - 尽管当然完全没有必要。这被称为“Wadler 对空间泄漏”问题。或者也许 GHC (with -O2) 比这更聪明。:)

此外，这显然使用了差异列表方法（谢谢，hammar），这也使它更有效率（大约比使用元组的版本快两倍）。我认为part使用累加器参数，因为它以相反的顺序构建它们。

于 2012-03-03T22:27:30.970 回答