Haskell中的quicksort如何工作？

Question

在Haskell网站上,这个示例是quicksort实现:

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

该网站有一个解释,但我有几个问题,我没有看到解决...

• 对于重新订购,两个元素的实际比较/交换在哪里？这是由'Ord'(有序)类型定义本身处理的.那么类型强制执行这个被命令的条件？
• '更大'的过滤器定义了项目'> = p'(枢轴),所以这并不意味着我们最终会在函数的结果列表中有一个额外的pivot [p],因为'++ [p ]'项目？

Answer 1

1. 没有交换,因为这不是QS的(几乎)就地版本.相反,新的名单是建立,然后再连接-比较时完成lesser和greater创建,用<,>=- Ord是一个类型类限制a要订购-如果没有使用它,你将无法使用<或>=.
2. 不,因为枢轴不是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]

Answer 2

对于重新订购,两个元素的实际比较/交换在哪里？这是由Ord(有序)类型定义本身处理的.那么类型强制执行这个被命令的条件？

什么Ord意思？

Ord只是意味着a应与本身相当或在更严格的条件的操作,例如>,<和==应进行定义a.您可以将其视为该方法的约束.

那么,订购在哪里完成？

答案是最后一种模式:

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

在运行时,程序将获得一个数组,并且数组必须满足以下两种模式之一:

模式1#:它是空的,在这种情况下,该函数返回相同的空数组并停止.

模式2#:它不是空的,换句话说,有一个头元素p附加到拖尾数组xs.在这种情况下,函数被告知置于p中间,放置的所有元素xs都小于p左边(由定义lesser)p并且所有元素xs都大于或等于p右边的p.此外,函数最终被告知应用它自己(即,相同的函数quicksort)lesser(如上所述,是左侧的数组p)和greater(如上所述,是右侧的数组)的一面p).正如您所看到的,这将持续到您留下零大小的数组并且模式1#终止该函数.

最后,每当这些递归调用终止时,函数都将返回数组:

sortedlesser ++ p ++ sortedgreater 

其中sortedlesser是起因于应用的阵列quicksort上lesser和sortedgreater是起因于应用的阵列quicksort上greater.

等等......我们不是一次又一次地复制p吗？

'更大'的谓词定义了项'> = p'(枢轴),所以这并不意味着我们最终会在函数的结果列表中得到一个额外的数据透视[p],因为'++ [p ]'项目？

不,这不是模式匹配的工作原理.它说的是所有元素xs都大于或等于p.根据定义p本身就是出于xs.如果有重复的p在xs那么他们将落在右手边.请注意,此选择将​​保留原始数组的自然顺序.

Answer 3

请注意,您可以使用更短更高效的内容(partition仅扫描原始列表一次)

quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where (lesser, greater) = partition (< p) xs