1

我已经设法在几行中实现了插入排序和快速排序，但是选择排序和合并排序仍然让我头疼；）

selectionsort [] = []

selectionsort (x:xs) =
    let (minimum, greater) = extractMinimum x [] xs
    in  minimum : selectionsort greater

extractMinimum minimumSoFar greater [] = (minimumSoFar, greater)

extractMinimum minimumSoFar greater (x:xs)
    | x < minimumSoFar = extractMinimum x (minimumSoFar:greater) xs
    | otherwise        = extractMinimum minimumSoFar (x:greater) xs

是否有类似extractMinimum标准库中可用的功能？我试着兜售(a -> a -> Bool/Ordering) -> [a] -> (a, [a])没有任何运气。

mergesort [ ] = [ ]

mergesort [x] = [x]

mergesort xs =
    let (left, right) = splitAt (length xs `div` 2) xs
    in  merge (mergesort left) (mergesort right)

merge xs [] = xs

merge [] ys = ys

merge xxs@(x:xs) yys@(y:ys)
    | x < y     = x : merge  xs yys
    | otherwise = y : merge xxs  ys

同样，我必须自己编写merge，还是可以重用现有组件？Hoogle 没有给我任何有用的结果(a -> a -> Bool/Ordering) -> [a] -> [a] -> [a]。

4

2 回答 2

2

标准库中没有任何内容，但至少merge由hackage上的包提供，尽管我不确定是否值得为这样一个简单的函数引入依赖项。

然而，

merge xxs@(x:xs) yys@(y:ys)
    | x < y     = x : merge  xs yys
    | otherwise = y : merge xxs  ys

产生一个不稳定的排序，要获得一个稳定的排序，放置的条件x应该是x <= y.

对于extractMinimum，我也没有找到任何东西，但我可以提供一个替代定义，

extractMinimum :: Ord a => a -> [a] -> (a,[a])
extractMinimum x = foldl' select (x, [])
  where
    select (mini, greater) y
      | y < mini  = (y, mini:greater)
      | otherwise = (mini, y:greater)

一个很好的定义selectionSort是

import Data.List -- for unfoldr

selectionSort :: Ord a => [a] -> [a]
selectionSort = unfoldr getMin
  where
    getMin [] = Nothing
    getMin (x:xs) = Just $ extractMinimum x xs
于 2012-10-06T15:44:37.283 回答
0

我对选择排序的建议：

import Data.List

selectionsort xs = unfoldr f xs where
    f [] = Nothing
    f xs = Just $ extractMinimum xs

extractMinimum (x:xs) = foldl' f (x,[]) xs where
  f (minimum, greater) x | x < minimum = (x, minimum : greater)
                         | otherwise = (minimum, x : greater)
于 2012-10-06T16:28:47.273 回答