haskell - Haskell 中的快速排序如何工作？

Question

在 Haskell website ，有这个例子quicksort implementation :

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

网站上有一个解释，但我有几个我没有看到的问题得到解决......

对两个元素进行重新排序的实际比较/交换在哪里？这是否由“Ord”(有序)类型定义本身处理。那么类型强制执行这种被订购的条件？

'greater' 过滤器定义了项目 '>= p' (枢轴)，所以这是否意味着我们最终会在函数的结果列表中得到一个额外的枢轴 [p]，因为 '++ [p ]' 元素？

Answer 1

没有交换，因为这不是(几乎)就地版本的 QS。取而代之的是，新列表被构建然后连接起来——比较在 lesser 时完成。和 greater被创建，带有 < , >= — Ord是限制 a 的类型类可订购——如果不使用，您将无法使用 <或 >= .

不，因为枢轴不是 xs 的一部分— 模式匹配将输入列表拆分为 p和 xs .

这是糟糕的 ASCII 可视化:

                                qs [5, 5, 6, 3, 1]
                                          |
                         qs [3, 1]   ++  [5] ++ qs [5, 6]
                             |            |       |
                  qs [1] ++ [3] ++ qs []  |    qs [] ++ [5] ++ qs [6]
                             |            |       |
                           [1, 3]    ++  [5]  ++ [5, 6]
                             \            |        /
                              \-------------------/
                                        |
                                  [1, 3, 5, 5, 6]