《Learn You Haskell》中的quicksort实现是否高效？

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

你提到的两个因素确实会削弱这个版本快排的效率，这个实现来自《Learn You Haskell》的入门教学章节，优先保证代码简洁易读，没有做性能优化：

• 关于++操作的开销：Haskell的列表是单链表结构，++拼接操作必须完整遍历左侧列表才能完成，每次执行smallerSorted ++ [x] ++ biggerSorted都要遍历一遍已排序的小数子列表。如果遇到原列表本身有序的最坏情况，整个排序的时间复杂度会退化到O(n²)，这是该实现性能偏低的核心原因之一。工业级的Haskell快排实现通常会采用差分列表、可变数组等结构规避高频++带来的额外开销。
• 关于列表推导构造子列表的开销：这里用了两次独立的列表推导分别筛选小于等于基准值和大于基准值的元素，相当于把未排序的xs列表完整遍历了两次，而常规快排的分区操作仅需要一次遍历就能完成大小元素的拆分，多出来的一次遍历也会带来不必要的性能损耗。优化版本的实现一般会通过单次尾递归遍历直接生成两个子列表，减少遍历次数。

这个版本仅作为函数式编程思路的演示使用，不会直接应用在对性能要求高的生产场景中。

内容的提问来源于stack exchange，提问作者Don Quixote