Haskell中的递归插入排序函数

Question

我有递归插入排序函数的工作代码。我只需要澄清它是如何工作的。现在，我对第三行 insert(isort xs) 上发生的事情感到困惑。如果可以的话，请逐步解释其余代码。谢谢！

isort :: [Int] -> [Int]
isort [] = []
isort [x] = [x]
isort (x:xs) = insert (isort xs)
  where insert [] = [x]
        insert (y:ys)
          | x < y = x : y : ys
          | otherwise = y : insert ys

Answer 1

好，我们来看看。你说你已经了解了其中的大部分内容，但为了完整起见，我还是会完成其余部分。

isort :: [Int] -> [Int]

整数排序采用 returns 列表 Int。

isort [] = []

尾递归函数的基本情况：空列表已排序。在实践中，对一个空列表进行排序是微不足道的，我们从不关心它，并且非空列表上的递归总是会在此之前遇到下一个基本情况，所以这一行主要在这里，以便模式守卫将涵盖每个可能的列表.

isort [x] = [x]

单例列表按重言式排序。这是我们将在实践中达到的基本情况。

isort (x:xs) = insert (isort xs)

现在我们到了您询问的线路。这是递归的情况。它在列表的尾部调用下面定义的 insert 函数。您可以将列表的头部 x 视为 insert.

的隐藏参数

这个函数基本上对列表的尾部进行排序，然后将头部插入到排序后的列表中：

  where
        insert [] = [x]

将 x 插入空列表会生成单例列表。

        insert (y:ys)
          | x < y = x : y : ys
          | otherwise = y : insert ys

这对案例使用第二个递归函数处理非平凡的插入。它假定 xs 已排序，并保持不变。因此，它遍历输入列表，并在第一次遇到大于 x 的元素时，将 x 拼接在列表的头部。（一个简单的优化是如果 y 等于 等于 x，而不是读取大量重复项——想象一下，如果你正在对一个包含相同元素数百万次的列表！）

虽然输入列表的元素小于（或者，如写的，等于）x，它会创建一个新的前缀列表，该前缀列表将拼接在x之前。

所以，如果你用 x:xs 作为 [3,2,1] 调用它，它会首先将其拆分为 3:[2,1] 并在 [2,1] 上递归调用自己。然后，它会再次递归并生成2:[1]，看到[1]是一个单例，并停止递归并开始展开堆栈。在返回的路上，它会看到 2>1 并再次递归，将 2 插入 [] 并在前面添加 1 以获得 1:[2]。然后，它返回到原始调用的范围，并尝试将 3 插入 [1,2]。它现在递归两次，生成前缀 1:2 并将 3 插入 [] 以获得 1:2:[3] 或 [1,2,3]，即 returns。

该实现是一个好的开始，但有经验的 Haskell 程序员可能会编写一个 尾递归模 cons 的版本。你更可能看到这样的东西表示为严格的左折叠，其中累加参数是到目前为止列表的排序前缀，每一步都将剩余列表的头部插入其中以获得新的排序前缀列表。（好吧，在现实世界中，他们会使用不同的排序算法，这种算法不需要二次时间，如果你不把它作为练习，你也会这样做，但是严格左折叠和尾递归模-cons 模式非常有用。）这样效率更高，因为编译器可以使用单个堆栈框架和单个严格累加器来实现它，这相当于命令式语言中的 while 循环。从空列表开始并以相反顺序插入每个元素的右折叠也可以，尽管它在这里没有任何优势。

一些示例代码，如您所见，它们非常相似：

import Data.List (foldl') insertSort :: Ord a => [a] -> [a] insertSort = foldl' insert [] where insert [] x = [x] insert (y:ys) x | x <= y = x:y:ys | otherwise = y:(insert ys x)

如果您再次遍历 [3,2,1] 示例，不同之处在于它从左到右，首先生成 [3]，然后插入 2 以获得 [2,3] ，然后插入 1 得到 [1,2,3]。 accumulating 参数是严格的，它进行的所有调用都是尾调用，因此它应该更快并且一次需要更少的内存。 insert 辅助函数本身是尾递归模缺点。

Answer 2

处理递归不要想得太深，让递归自己做。我们先搞清楚isort、insert是干什么的。

isort xs 对列表 xs 进行升序排序
insert (isort xs) 尝试将单个元素 x 插入到 sorted 列表中：isort xs
insert (y:ys) 试图为 x
列表y:ys按升序排列！
如果x<y，我们找到x属于哪里！
否则，x>=y、x应该比x晚出现，所以我们再来看一个子问题：insert ys

Haskell中的递归插入排序函数

Recursive insertion sort function in Haskell

sorting

recursion

haskell

insertion