以下快速排序的Haskell实现是否有效？
我在名为 Learn You Haskell 的书中找到了快速排序的以下实现。
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort [a | a <- xs, a <= x]
biggerSorted = quicksort [a | a <- xs, a > x]
in smallerSorted ++ [x] ++ biggerSorted
我的问题是，这是否会破坏快速排序的效率，因为
- ++ 操作相当昂贵
- 列表推导用于构造两个子列表？
回答
对于算法点，它不是就地算法。因此，它不会像您所知道的传统命令式实现那样高效。（就地是类似快速排序的排序算法卓越性能的一个关键方面。）
它将以快速排序的典型复杂性运行（平均而言O(N * log(N))，最坏情况O(N²)）。因此，从能够随输入扩展的意义上说，它是有效的。但它不会像高度调整的实现那样快（例如，请参阅此问题）。
作为一个小调整，我记得更换[x] ++ biggerSorted由(x:biggerSorted)是唾手可得的小幅提高性能。那是多年前的事了，所以也许今天优化编译器可以自动进行低级优化。
- 快速排序是 O(n^2)，如果枢轴是有利的，它只是 O(n log n)。
- 不过，可以肯定地说，*预期的*运行时间是 O(n lg n); 当您使用新列表而不是交换来实现分区时，隐藏常量会增加。
- 如今，GHC 确实足够聪明，可以将 `[foo] ++ bar` 转换为 `foo:bar`。