algorithm - 以下快速排序的 Haskell 实现是否高效？

Question

我在《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  

我的问题是，鉴于此，这是否会降低快速排序的效率

1. ++ 操作相当昂贵
2. 列表推导式用于构造两个子列表？

Answer 1

对于算法点来说，它不是就地算法。因此，它不会像您所知道的传统命令式实现那样高效。 (就地是类似快速排序的排序算法卓越性能的一个关键方面。)

它将以快速排序的典型复杂性运行(平均 O(N * log(N)) 最坏情况 O(N²) )。因此，它是高效的，因为它能够根据输入进行扩展。但它不会像高度调整的实现那么快(例如，参见 this question )。

作为一个小调整，我记得替换了 [x] ++ biggerSorted通过(x:biggerSorted)稍微提高性能是一个容易实现的目标。那是很多年前的事了，所以也许今天的优化编译器可以自动进行低级优化。