我知道quicksort有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]
好的，所以我知道这件事有问题。最大的问题是它没有排序，这通常是quicksort的一大优势。即使这没关系，它仍然需要比典型的快速排序更长的时间，因为它在分区时必须进行两次列表传递，然后它会进行昂贵的附加操作以将其拼接回来。此外，选择第一个元素作为枢轴不是最佳选择。
但即便考虑所有这些，这个快速排序的平均时间复杂度与标准快速排序不同吗？即，O(n log n)？因为追加和分区仍然具有线性时间复杂度，即使它们效率低下。
这个“快速排序”实际上是砍伐森林的树种：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)
我同意你的假设，即平均时间复杂度仍然是O(n log n)。我不是专家，100％肯定，但这些是我的想法：
这是就地快速排序的伪代码:(调用快速排序，其中l = 1且r =数组的长度）
Quicksort(l,r)
--------------
IF r-l>=1 THEN
choose pivot element x of {x_l,x_l+1,...,x_r-1,x_r}
order the array-segment x_l,...x_r in such a way that
all elements < x are on the left side of x // line 6
all elements > x are on the right side of x // line 7
let m be the position of x in the 'sorted' array (as said in the two lines above)
Quicksort(l,m-1);
Quicksort(m+1,r)
FI
平均时间复杂度分析然后通过选择第6行和第7行中的“< - ”比较作为该算法中的主导操作，并最终得出平均时间复杂度为O（n log n）的结论。由于线路的成本“以这样的方式对数组段x_l，... x_r进行排序”不被考虑（如果你想找到界限，只有主导操作在时间复杂度分析中很重要），我认为“因为它在分区时必须对列表进行两次传递”不是问题，因为在这一步中你的Haskell版本只需要大约两倍的时间。对于附录操作也是如此，我同意这一点，这对渐近成本没有任何影响：
因为追加和分区仍然具有线性时间复杂度，即使它们效率低下。
为方便起见，我们假设这会将“n”加到我们的时间复杂度成本上，因此我们得到“O（n log n + n）”。由于存在n log n> n的自然数o，对于大于o的所有自然数都为真，你可以估计n log n + n到顶部2 n log n和底部n log n，因此n log n + n = O（n log n）。
此外，选择第一个元素作为枢轴不是最佳选择。
我认为枢轴元素的选择在这里是无关紧要的，因为在平均情况分析中，您假设元素在数组中的均匀分布。您无法知道阵列中的哪个位置应该选择它，因此您必须考虑所有这些情况，其中您的pivot元素（独立于列表的哪个位置）是i-st最小元素你的清单，对于i = 1 ... r。
我可以为你提供Ideone.com的运行时测试，它似乎显示基于（++）版本的或多或少的线性运行时间，以及使用Landei's answer的累加器技术，以及使用one-pass three-way partitioning的另一个。在有序数据上，这对于所有这些都变为二次或更差。
-- random: 100k 200k 400k 800k
-- _O 0.35s-11MB 0.85s-29MB 1.80s-53MB 3.71s-87MB n^1.3 1.1 1.0
-- _P 0.36s-12MB 0.80s-20MB 1.66s-45MB 3.76s-67MB n^1.2 1.1 1.2
-- _A 0.31s-14MB 0.62s-20MB 1.58s-54MB 3.22s-95MB n^1.0 1.3 1.0
-- _3 0.20s- 9MB 0.41s-14MB 0.88s-24MB 1.92s-49MB n^1.0 1.1 1.1
-- ordered: 230 460 900 1800
-- _P 0.09s 0.33s 1.43s 6.89s n^1.9 2.1 2.3
-- _A 0.09s 0.33s 1.44s 6.90s n^1.9 2.1 2.3
-- _3 0.05s 0.15s 0.63s 3.14s n^1.6 2.1 2.3
quicksortO xs = go xs where
go [] = []
go (x:xs) = go [y | y<-xs, y<x] ++ [x] ++ go [y | y<-xs, y>=x]
quicksortP xs = go xs where
go [] = []
go (x:xs) = go [y | y<-xs, y<x] ++ (x : go [y | y<-xs, y>=x])
quicksortA xs = go xs [] where
go [] acc = acc
go (x:xs) acc = go [y | y<-xs, y<x] (x : go [y | y<-xs, y>=x] acc)
quicksort3 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)
empirical run-time complexities在这里被估计为O(n^a)，其中a = log( t2/t1 ) / log( n2/n1 )。时间非常近似，因为意外不是非常可靠，偶尔会有很多人，但是为了检查时间复杂性就足够了。
因此，这些数据似乎表明单通道分区比双通道方案快1.5倍-2倍，使用(++)绝不会减慢速度 - 完全没有。即“追加行动”根本不是“代价高昂”。
二次行为或（++）/ append似乎是一个都市神话 - 当然在Haskell语境中
（编辑：...即在受保护的递归/ tail recursion modulo cons的背景下;参见this answer）（更新：作为user:AndrewC explains，它实际上是左折叠的二次方;当(++)与右折叠使用时线性;更多关于此here和here）。
后来补充：为了保持稳定，三向分区快速排序版本也应该以自上而下的方式构建其部件：
q3s xs = go xs [] where
go (x:xs) z = part x xs go (x:) (`go` z)
go [] z = z
part x [] a b c = a [] (b (c []))
part x (y:ys) a b c =
case compare y x of
LT -> part x ys (a . (y:)) b c
EQ -> part x ys a (b . (y:)) c
GT -> part x ys a b (c . (y:))
（性能未经测试）。
我不知道这有多少改善了运行时的复杂性，但通过使用累加器，你可以避免昂贵的(++)：
quicksort xs = go xs [] where
go [] acc = acc
go (x:xs) acc = go [y | y<-xs, y<x] (x : go [y | y<-xs, y>=x] acc)
在这里查看一个真正的O（n log n）快速排序，它可以在数组和列表上运行：http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.23.4398&rep=rep1&type=pdf在Common Lisp中很容易实现，并且它优于许多商业lisps的排序实现。
是的，这个版本具有与经典版本相同的渐近复杂度 - 你将线性时间partition替换为：两个传递（<和>=），并且你有额外的线性时间++（包括线性重新分配/复制） ）。所以这是一个比原地分区更糟糕的常数因素，但它仍然是线性的。算法的所有其他方面都是相同的，因此给出“真实”（即就地）快速排序的O（n log n）平均情况的相同分析仍然存在。