主页 / 问题 / 936163
Accepted
rjhdby
Asked:2020-01-24 20:28:29 +0000 UTC2020-01-24 20:28:29 +0000 UTC

在haskell中实现快速排序。冗余与否？

  • 772

在培训材料中，我发现了这样一个快速排序的经典实现

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

我有一个问题。在这篇文章中

smallerSorted ++ [x] ++ biggerSorted

执行smallerSorted和biggerSorted。也就是说，事实上，我们为了分成更小和更大的值的列表，运行xs两次，而一次通过就足够了。

我是对的，还是以某种方式进一步优化？

haskell

1 个回答

  1. Best Answer

    是的，这个列表出现了两次。

    可以优化

    import Data.List(partition)

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let (small, big) = partition ( <= x ) xs
        smallerSorted = quicksort small  
        biggerSorted = quicksort big  
    in  smallerSorted ++ [x] ++ biggerSorted
    • 2

相关问题