我在《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²)
)。因此,它是高效的,因为它能够根据输入进行扩展。但它不会像高度调整的实现那么快(例如,参见 this question )。
作为一个小调整,我记得替换了 [x] ++ biggerSorted
通过(x:biggerSorted)
稍微提高性能是一个容易实现的目标。那是很多年前的事了,所以也许今天的优化编译器可以自动进行低级优化。
关于algorithm - 以下快速排序的 Haskell 实现是否高效?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68517871/