6

在Haskell 网站上，有这个示例快速排序实现：

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 ]' 物品？
4

4 回答 4

33
  1. 没有交换，因为这不是（几乎）就地版本的 QS。取而代之的是，构建新列表然后将其连接起来——比较是在创建lesser和greater创建时完成的，其中<,是一个限制为可排序的类型类>=——如果不使用它，你将无法使用or 。Orda<>=
  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]
于 2012-04-16T02:18:25.083 回答
17

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

是什么Ord意思？

Ord只是意味着a应该与自身或更严格的操作（如>, , ）具有可比性<，并且==应该为a. 您可以将其视为对方法的约束。

那么，在哪里下单呢？

答案是最后一个模式：

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

在运行时，程序将获取一个数组，并且该数组必须满足以下两种模式之一：

模式 1#：它是空的，在这种情况下，函数返回相同的空数组并停止。

模式 2#：它不为空，或者换句话说，有一个 head 元素p附加到一个 tailing array xs。在这种情况下，函数被告知将其放在p中间，将所有xs小于的元素p放在 的左侧（由 定义lesser），将所有大于或等于的p元素放在 的右侧。此外，函数最终被告知将自身（即相同的函数）应用于（如我们上面定义的，是 的左侧的数组）和（如我们上面定义的，是右侧的数组侧xsppquicksortlesserpgreaterp）。如您所见，这将一直持续到您留下一个大小为零的数组并且模式 1# 终止该函数。

最后，每当这些递归调用终止时，函数将返回数组：

sortedlesser ++ p ++ sortedgreater

其中sortedlesser是应用quicksorton产生的数组lesser，是应用onsortedgreater产生的数组。quicksortgreater

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

'greater' 谓词定义了项目 '>= p' （枢轴），所以这是否意味着我们最终会在函数的结果列表中得到一个额外的枢轴 [p]，因为 '++ [p ]' 物品？

不，这不是模式匹配的工作方式。这是说其中的所有元素xs都大于或等于p。顾名思义p，它本身就是 out of xs。如果 in 有重复项p，xs则它们将落在右侧。请注意，此选择将​​保留原始数组的自然顺序。

于 2012-04-16T02:35:11.833 回答
8

请注意，您可以使用以下方法编写更短且性能更高的代码（因为partition只扫描原始列表一次）

quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where (lesser, greater) = partition (< p) xs
于 2012-04-16T06:48:00.303 回答
2

如果你只想要一行：

qsortOneLine s = case s of{[]->[];(x:xs)->qsortOneLine [y | y<-xs, y<x] ++ x : qsortOneLine [y | y<-xs, y>=x]}

如果您想要更高性能的代码：

qsort3 :: Ord a => [a] -> [a]
qsort3 x = qsort3' x []
qsort3' [] y     = y
qsort3' [x] y    = x:y
qsort3' (x:xs) y = part xs [] [x] []  
      where
         part [] l e g = qsort3' l (e ++ (qsort3' g y))
         part (z:zs) l e g 
             | z > x     = part zs l e (z:g) 
             | z < x     = part zs (z:l) e g 
             | otherwise = part zs l (z:e) g

http://en.literateprograms.org/Quicksort_(Haskell )

于 2012-07-16T09:34:19.247 回答