haskell - 快速排序的比较次数

Question

这是一个被认为“不是真正快速”的快速排序的实现:

qSort :: Ord a => [a] -> [a]
qSort [] = []
qSort (p:xs) = (qSort $ filter (< p) xs) ++ (qSort $ filter (== p) xs) ++ [p] ++ (qSort $ filter (> p) xs)

main = print $ qSort [15, 11, 9, 25, -3]

但是，是否有可能计算完成它所需的比较次数？我试着计算 filter (< p) xs 的大小和 filter (> p) xs但事实证明我不是我需要的。

更新:

问题不在于时间复杂度，而在于计算比较次数。

Answer 1

正如其他人所说，直接翻译是修改您的算法以使用 monad，它将对比较进行计数。我宁愿使用 Writer 而不是 State，因为它更自然地描述了正在发生的事情:每个结果都增加了它所需的(附加)比较次数:

import Control.Applicative
import Control.Monad
import Control.Monad.Writer.Strict
import Data.Monoid

type CountM a = Writer (Sum Int) a

然后让我们定义一个函数，将一个纯值包装成一个递增计数器的单值函数:

count :: Int -> a -> CountM a
count c = (<$ tell (Sum c))

现在我们可以定义

qSortM :: Ord a => [a] -> CountM [a]
qSortM [] = return []
qSortM (p:xs) =
   concatM [ qSortM =<< filtM (<  p)
           , filtM (== p)
           , return [p]
           , qSortM =<< filtM (>  p)
           ]
  where
    filtM p = filterM (count 1 . p) xs
    concatM :: (Monad m) => [m [a]] -> m [a]
    concatM = liftM concat . sequence

它不如原始版本好，但仍然可用。

---

请注意，您将列表中的每个元素进行三次比较，而一次就足够了。这有另一个不幸的后果，即原始列表必须保存在内存中，直到所有三个过滤器都完成。所以让我们改为定义

-- We don't care we reverse the order of elements in the buckets,
-- we'll sort them later anyway.
split :: (Ord a) => a -> [a] -> ([a], [a], [a], Int)
split p = foldl f ([], [], [], 0)
  where
    f (ls, es, gs, c) x = case compare x p of
        LT  -> (x : ls, es, gs, c')
        EQ  -> (ls, x : es, gs, c')
        GT  -> (ls, es, x : gs, c')
      where
        c' = c `seq` c + 1

这会同时执行拆分到三个桶中并计算列表的长度，因此我们可以立即更新计数器。该列表会立即被消耗掉，并且可以被垃圾收集器丢弃。

现在我们的快速排序会变得更精简

qSortM :: Ord a => [a] -> CountM [a]
qSortM [] = return []
qSortM (p:xs) = count c =<<
    concatM [ qSortM ls
            , return (p : es)
            , qSortM gs
            ]
  where
    (ls, es, gs, c) = split p xs
    concatM = liftM concat . sequence

我们可以在不使用 Writer 的情况下达到相同的结果，只需让 qSortM 显式返回 (Int, [a])。但是这样我们就不得不手动处理递归qSortM的结果，这样会比较麻烦。此外，单子(monad)方式允许我们在以后添加更多信息，例如最大深度，而不会以任何方式破坏核心部分。