haskell快速排序,为什么第一个让使用<=而不是<？

Question

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerOrEqual = [a | a <- xs, a <= x]
        larger = [a | a <- xs, a > x]
    in quicksort smallerOrEqual ++ [x] ++ larger

main = do
    let a = [ 5, 1, 9, 4, 6, 7, 3]
    print  $ quicksort a

在Haskell中快速排序,为什么第一次let使用<=而不是<？我想<=会x多次复制.为什么不？

Answer 1

我认为<=会多次复制那个x

不,它不会.让我们了解这里到底发生了什么.您基本上将列表分为三个部分.

1. 小于或等于pivot元素的数字列表(不包括第一个元素,因为它是pivot元素)

2. pivot元素本身(列表中的第一个元素)

3. 大于pivot元素的数字列表

因此,在您的情况下,分区列表就像这样

[1, 4, 3] ++ [5] ++ [9, 6, 7]

考虑这样的情况,quicksort [5, 1, 5, 9, 8, 5, 3, 6, 4].然后,您的程序将其分区为这样的东西

smallerOrEqual ++ [x] ++ larger

由于smallerOrEqual与larger工作有xs,它不具备x,没有重复这样.现在,过滤后的分区列表变为

[1, 5, 5, 3, 4] ++ [5] ++ [9, 8, 6]

看到？没有重复,只是分区.

注意:您的程序存在严重错误.检查这一行

quicksort smallerOrEqual ++ [x] ++ larger

它基本上是这样的

(quicksort smallerOrEqual) ++ [x] ++ larger

因此,larger列表永远不会排序.您递归地必须对较小的列表和较大的列表进行排序,最后将它们合并为一个.应该是这样的

(quicksort smallerOrEqual) ++ [x] ++ (quicksort larger)

这可以写成没有这样的括号

quicksort smallerOrEqual ++ [x] ++ quicksort larger