algorithm - 这是 Haskell 中正确实现的合并排序吗？

Question

我在网上的任何地方都找不到我的代码，所以你能告诉我为什么函数 myMergeSort 是归并排序吗？我知道我的函数 myMergeSort 排序，但我不确定它是否真的使用合并排序算法进行排序，或者它是否是一种不同的算法。我几天前才开始使用 Haskell。

merge xs [] = xs
merge [] ys = ys
merge (x : xs) (y : ys)
    | x <= y = x : merge xs (y : ys)
    | otherwise = y : merge (x : xs) ys

myMergeSort :: [Int] -> [Int]
myMergeSort [] = []
myMergeSort (x:[]) = [x]
myMergeSort (x:xs) = foldl merge [] (map (\x -> [x]) (x:xs))

我对合并功能没有任何疑问。

以下函数 mergeSortOfficial 是提供给我们的解决方案，我理解它但不确定我是否在我的函数 myMergeSort 中正确实现了合并排序算法。

官方解决方案-实现:

mergeSortOfficial [] = []
mergeSortOfficial (x : []) = [x]
mergeSortOfficial xs = merge
    (mergeSortOfficial (take ((length xs) ‘div‘ 2) xs))
    (mergeSortOfficial (drop ((length xs) ‘div‘ 2) xs))

Answer 1

不，那不是mergeSort。这就是 insertionSort，它与 bubbleSort 本质上是相同的算法，具体取决于您如何看待它。在每一步，一个单例列表都被合并到到目前为止累积的有序列表，因此，实际上，该单例的元素被插入。

正如其他评论者已经观察到的那样，要获得 mergeSort(尤其是它的效率)，有必要将问题重复划分为大致相等的部分(而不是“一个元素”和“休息”)。 “官方”解决方案提供了一种相当笨拙的方法来做到这一点。我很喜欢

foldr (\ x (ys, zs) -> (x : zs, ys)) ([], [])

作为一种将列表分成两部分的方法，不是在中间，而是分成偶数和奇数位置的元素。

如果像我一样，您喜欢在可以看到的地方预先设置结构，您可以将有序列表设为 Monoid。

import Data.Monoid
import Data.Foldable
import Control.Newtype

newtype Merge x = Merge {merged :: [x]}
instance Newtype (Merge x) [x] where
  pack = Merge
  unpack = merged

instance Ord x => Monoid (Merge x) where
  mempty = Merge []
  mappend (Merge xs) (Merge ys) = Merge (merge xs ys) where
    -- merge is as you defined it

现在你有了插入排序

ala' Merge foldMap (:[]) :: [x] -> [x]

获得mergeSort的分而治之结构的一种方法是使它成为一种数据结构:二叉树。

data Tree x = None | One x | Node (Tree x) (Tree x) deriving Foldable

我没有在这里强制执行平衡不变量，但我可以。重点是和之前一样的操作，多了一个类型

ala' Merge foldMap (:[]) :: Tree x -> [x]

合并从树状排列的元素中收集的列表。要获得上述安排，请思考“Tree 的缺点是什么？”并确保通过我在上述“划分”操作中使用的相同类型的曲折来保持平衡。

twistin :: x -> Tree x -> Tree x   -- a very cons-like type
twistin x None        = One x
twistin x (One y)     = Node (One x) (One y)
twistin x (Node l r)  = Node (twistin x r) l

现在您通过构建二叉树然后合并它来实现合并排序。

mergeSort :: Ord x => [x] -> [x]
mergeSort = ala' Merge foldMap (:[]) . foldr twistin None

当然，引入中间数据结构有好奇心的值(value)，但你可以很容易地把它剪下来，得到类似的东西

mergeSort :: Ord x => [x] -> [x]
mergeSort []   = []
mergeSort [x]  = [x]
mergeSort xs   = merge (mergeSort ys) (mergeSort zs) where
  (ys, zs) = foldr (\ x (ys, zs) -> (x : zs, ys)) ([], []) xs

这里的树已经成为程序的递归结构。