haskell - 伪快速排序时间复杂度

Question

我知道快速排序有 O(n log n)平均时间复杂度。一个伪快速排序(当你从足够远的地方看它时，它只是一种快速排序，具有适当高的抽象级别)，它通常用于证明函数式语言的简洁性，如下所示(在 Haskell 中给出):

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]

好的，所以我知道这件事有问题。这样做的最大问题是它没有就地排序，这通常是快速排序的一大优势。即使这无关紧要，它仍然会比典型的快速排序花费更长的时间，因为它在对列表进行分区时必须执行两次遍历，并且它会执行昂贵的附加操作以在之后将其拼接在一起。此外，选择第一个元素作为枢轴不是最佳选择。

但即使考虑到所有这些，这种快速排序的平均时间复杂度是否与标准快速排序相同？即， O(n log n) ?因为追加和分区仍然具有线性时间复杂度，即使它们效率低下。

Answer 1

这种“快速排序”实际上是砍伐森林的树排序:
http://www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell

data Tree a = Leaf | Node a (Tree a) (Tree a)

mkTree [] = Leaf
mkTree (x:xs) = Node x (mkTree (filter (<= x) xs)) (mkTree (filter (x <) xs))

二叉树是不平衡的，因此构建搜索树的最坏情况复杂度为 O(N^2)，平均情况复杂度为 O(N*Log N)。

foldTree f g Leaf = g
foldTree f g (Node x l r) = f x (foldTree f g l) (foldTree f g r)

treeSort l = foldTree (\x lft rht -> lft++[x]++rht) [] (mkTree l)

检索算法具有 O(N^2) 最坏情况和 O(N*Log N) 平均情况复杂度。

均衡:

Prelude> let rnds = iterate step where step x = (75*x) `mod` 65537
Prelude> length . quicksort . take 4000 . rnds $ 1
4000
(0.08 secs, 10859016 bytes)
Prelude> length . quicksort . take 8000 . rnds $ 1
8000
(0.12 secs, 21183208 bytes)
Prelude> length . quicksort . take 16000 . rnds $ 1
16000
(0.25 secs, 42322744 bytes)

不太平衡:

Prelude> length . quicksort . map (`mod` 10) $ [1..4000]
4000
(0.62 secs, 65024528 bytes)
Prelude> length . quicksort . map (`mod` 10) $ [1..8000]
8000
(2.45 secs, 241906856 bytes)
Prelude> length . quicksort . map (`mod` 10) $ [1..16000]
16000
(9.52 secs, 941667704 bytes)