改进简单的 qsort 实现

Question

我开始学习 Haskell 并且我一直在阅读 Haskell 维基上的 this 页面，其中报告了这个 qsort 实现：

 qsort :: (Ord a) => [a] -> [a]
 qsort []     = []
 qsort (x:xs) = qsort less ++ [x] ++ qsort more
     where less = filter (<x)  xs
           more = filter (>=x) xs

之后是一个警告，表明这不是最有效的方法，并链接了一个 article，它显示了同一算法的极其冗长的版本。只是看着它，我认为那不是我学习 Haskell 的目的，我想在不牺牲其优雅的情况下制作一个更好的初始 qsort 版本。我主要专注于消除每次调用两次运行 filter 的需要，这就是我想出的：

filter' :: (a -> Bool) -> [a] -> ([a], [a])
filter' _ [] = ([], [])
filter' f a = filterInternal a ([], [])
  where
    filterInternal [] p = p
    filterInternal (x:xs) (l, t)
      | f x       = filterInternal xs (x:l, t)
      | otherwise = filterInternal xs (l, x:t)

qsort' :: (Ord a) => [a] -> [a]
qsort' [] = []
qsort' (x:xs) = qsort' less ++ [x] ++ qsort' more
  where
    (more, less) = filter' (>x) xs

但我不确定这是否真的更好。我的意思是，它有效，但它与初始版本相比如何？

Answer 1

这是我在思考大致相同的问题时想出的解决方案（请指出任何注意事项！）。我没有想太多关于 space 的复杂性（不过不应该太可怕），只是时间。真正杀死幼稚qsort的是O(n)操作(++)。因此，让我们使用一种新的数据结构（可折叠）来快速连接。

{-# LANGUAGE DeriveFoldable #-}

import Data.Foldable
import Data.List

data Seq a = (Seq a) :++: (Seq a) | Leaf a | Empty deriving (Foldable)

然后，修改后的 qsort' returns 和 Seq a 将是

qsort' :: Ord a => [a] -> Seq a
qsort' []     = Empty
qsort' (x:xs) = qsort less :++: Leaf x :++: qsort more
    where (less, more) = partition (<x)  xs

而 qsort 本身就是 qsort = toList . qsort'.

注意：涉及 partition 的修复让您获得更好的常数因子，但是 ++ 与 :++: 意味着 qsort 现在可以比 [=23 更好=].此外，大多数排序实现都比这更好。这样做的目的只是试图尽可能接近地反映 "naive" 实现。

改进简单的 qsort 实现

Improving naive qsort implementation

haskell

quicksort