正如他们所说，“真正的快速排序就地排序”。所以快速排序的标准短Haskell代码，
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
毕竟，它描述的是什么算法/计算过程？
这肯定不是Tony Hoare 设计的，因为它缺乏最明确的特征，即就地分区算法。
（答案可能是众所周知的，但还没有在这里）。
更正：这个问题实际上是重复的：答案毕竟是已知的：cf。伪快速排序时间复杂度。
是的，这是快速排序，只是不是就地。它匹配快速排序的高级算法，同时更改低级实现以匹配链表的数据结构。这就是为什么它是链表的快速排序。
我更愿意说“快速排序最初是为就地工作而开发的”，而不是“真正的快速排序是就地完成的”。快速排序有许多变体，包括随机选择枢轴以避免更坏的情况等。这是对链表快速排序的明智、清晰的定义。
这个定义完全符合我们在英国教 16 岁数学学生快速排序的方式。（我们教的是算法，而不是编程。）就地非常模糊了目的和设计，这就是为什么我们不教那些细节，尽管距离教函数式编程或链表有一百万英里。（这并没有改变当你有破坏性的更新数组时，对交换技巧就地算法是最好的事实。）
此定义存在时间损失，因为它为两个子列表遍历列表两次。当然可以将其重写为分区而不是过滤，但我断言这是优化而不是改变这里的基本算法，快速排序。
所有就地算法都需要在 Haskell 中进行一些“仪式”，其中可变状态隐藏在 monad 后面。上面的算法是快速排序，只是不是就地排序。
预期的答案（从这里）是这“真的是砍伐森林的树种”。事实证明， haskellwiki上也提到了它。