Haskell中列表排序合并功能实现课程作业技术问询

嘿，我来帮你搞定这个Haskell的问题！

你的需求很明确：接收两个数值列表，先分别给它们排序，再合并成一个有序的新列表。之前的代码失效，是因为它默认输入列表已经是有序的——这其实是归并排序里“合并两个有序列表”的步骤，但漏掉了先给输入列表排序的环节。

在Haskell里，我们不用for循环，而是用内置函数或者递归就能优雅解决这个问题，分两种方式给你讲：

1. 简单直观版（快速实现，不用纠结效率） #

Haskell的Data.List模块里自带了sort函数，能直接给任何可比较类型的列表排序。我们可以先分别给两个输入列表排序，再把它们拼接起来后整体排序（虽然有点冗余，但小数据量下完全够用）：

首先要导入sort函数：

import Data.List (sort)

然后实现功能函数：

mergeSortedLists :: Ord a => [a] -> [a] -> [a]
mergeSortedLists xs ys = sort (sort xs ++ sort ys)

比如你输入[9,3,5]和[2,7,1]，这个函数会先把两个列表分别排序成[3,5,9]和[1,2,7]，拼接后得到[3,5,9,1,2,7]，最后整体排序输出[1,2,3,5,7,9]，完全符合要求。

2. 高效优化版（利用归并逻辑） #

如果数据量比较大，上面的方法有点浪费——毕竟两个已经排序的列表，我们可以用归并的方式直接合并，不用再整体排序。我们自己实现一个合并两个有序列表的递归函数，再结合sort：

import Data.List (sort)

-- 合并两个已经有序的列表
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys  -- 如果第一个列表空，直接返回第二个
merge xs [] = xs  -- 如果第二个列表空，直接返回第一个
merge (x:xsRest) (y:ysRest)
  | x <= y    = x : merge xsRest (y:ysRest)  -- 取较小的元素，递归处理剩余部分
  | otherwise = y : merge (x:xsRest) ysRest

-- 主函数：先分别排序，再归并
mergeSortedLists :: Ord a => [a] -> [a] -> [a]
mergeSortedLists xs ys = merge (sort xs) (sort ys)

这个版本里，merge函数用递归替代了其他语言里的for循环逻辑：每次比较两个有序列表的首元素，把更小的那个放到结果里，然后继续处理剩下的元素，直到其中一个列表为空。这样的时间复杂度比“拼接后再排序”更低，适合处理大规模数据。

测试一下同样的输入：mergeSortedLists [9,3,5] [2,7,1] 会先排序得到[3,5,9]和[1,2,7]，然后通过merge一步步合并，最终输出有序列表。

总结一下，核心就是先给每个输入列表单独排序，再把两个有序列表合并——不管你用哪种方式，都能解决输入列表无序时失效的问题。

内容的提问来源于stack exchange，提问作者Mike Noel Higgs