Haskell整数列表递归排序实现求助：现有代码无法解决问题

首先，我们先看看你写的代码存在的问题：

1. 模式匹配不完整：你的函数只处理了空列表和至少两个元素的列表（x:y:xs），但当列表只剩一个元素时，没有对应的模式匹配，运行时会抛出非穷尽模式的错误。
2. 逻辑方向偏差：当前代码只是不断丢弃前两个元素中的较小者，并没有构建出排序后的列表——最终你只能得到原列表中的最大值，而不是完整的有序列表。

接下来，我会用两种容易理解的递归排序算法来帮你实现需求：选择排序和插入排序，这两种算法的递归逻辑非常直观，适合入门学习。

方法一：递归实现选择排序 #

选择排序的核心思路是：每次找到列表中的最小元素，把它放到结果的最前面，然后递归排序剩下的元素。我们需要两个辅助函数配合主函数：

1. 辅助函数：找到列表中的最小元素 #

minimo :: [Int] -> Int
minimo [x] = x  -- 单元素列表的最小值就是自己
minimo (x:xs) = min x (minimo xs)  -- 比较第一个元素和剩余列表的最小值，取更小的那个

2. 辅助函数：移除列表中第一个出现的最小元素 #

removerMinimo :: [Int] -> [Int]
removerMinimo [] = []
removerMinimo (x:xs)
    | x == minimo (x:xs) = xs  -- 如果当前元素是最小值，直接返回剩余列表
    | otherwise = x : removerMinimo xs  -- 否则把当前元素保留，递归处理剩余列表

3. 主排序函数 #

ordenarMemoria :: [Int] -> [Int]
ordenarMemoria [] = []  -- 空列表排序后还是空列表
ordenarMemoria xs = minimo xs : ordenarMemoria (removerMinimo xs)  -- 把最小值放在前面，递归排序剩下的部分

逻辑解释

比如输入[3,1,2]：

• 第一步找到最小值1，移除后得到[3,2]，所以结果开头是1 : ...
• 递归处理[3,2]，找到最小值2，移除后得到[3]，结果变成1 : 2 : ...
• 递归处理[3]，直接返回[3]，最终得到[1,2,3]

方法二：递归实现插入排序 #

插入排序的核心思路是：把列表的第一个元素插入到剩余元素排序后的正确位置，递归重复这个过程。这种方法只需要一个辅助函数：

1. 辅助函数：将元素插入到有序列表的正确位置 #

insertar :: Int -> [Int] -> [Int]
insertar x [] = [x]  -- 插入到空列表，直接返回包含x的列表
insertar x (y:ys)
    | x <= y = x : y : ys  -- 如果x比当前列表的第一个元素小，直接插在前面
    | otherwise = y : insertar x ys  -- 否则把当前元素保留，递归插入x到剩余的有序列表中

2. 主排序函数 #

ordenarMemoria :: [Int] -> [Int]
ordenarMemoria [] = []  -- 空列表边界条件
ordenarMemoria (x:xs) = insertar x (ordenarMemoria xs)  -- 先排序剩余列表，再把x插入到正确位置

逻辑解释

比如输入[3,1,2]：

• 先递归排序[1,2]，得到[1,2]
• 把3插入到[1,2]的正确位置，得到[1,2,3]
• 而排序[1,2]时，先递归排序[2]得到[2]，再把1插入到[2]前面，得到[1,2]

递归的核心思路小总结 #

递归的关键在于分解问题+边界条件：

• 边界条件：处理最简单的情况（比如空列表、单元素列表），直接给出结果
• 分解问题：把原问题拆解成更小的子问题，解决子问题后再组合出原问题的结果

这样一步步拆解，递归就不会那么难理解啦。

内容的提问来源于stack exchange，提问作者Felipe Otero