伪快速排序时间复杂度

我知道快速排序有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]

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

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

这种“快速排序”实际上是森林砍伐的树排序：http://www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell 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)