快速排序仅对小数列表生效？自定义辅助函数排序异常排查

首先看你的测试案例和代码片段，核心问题大概率出在splitBy函数的条件逻辑，以及它和quicksort递归逻辑的匹配上。咱们一步步拆解：

问题现象分析 #

你提到两个测试用例：

• 当列表最大元素是1237时，排序正常；
• 把第一个元素改成3687（此时它是列表最大值），排序直接返回原列表。

这种“只有当基准不是最大值时才生效”的现象，几乎可以确定是拆分列表的逻辑和递归合并的顺序不匹配导致的。

最可能的错误点 #

从你给出的splitBy代码片段splitBy n y = ([x|x <- y,x >...来看，你大概率把拆分条件写反了，或者递归合并时的顺序搞反了：

1. splitBy条件逻辑错误 #

标准快排的拆分逻辑是：将列表拆分为小于等于基准值和大于基准值的两个子列表，然后递归排序这两个子列表，最后合并为排序后的左列表 ++ [基准] ++ 排序后的右列表。

如果你的splitBy是把大于基准值的元素放到第一个元组，而递归时又错误地把这个元组当成“小于基准”的部分去合并，就会导致：

• 当基准是列表最大值时，第一个元组为空，第二个元组是所有其他元素；
• 合并时变成空列表 ++ [基准] ++ 排序后的全元素列表，但如果你的递归逻辑没有正确处理第二个元组，就会直接返回原列表。

2. 递归时未正确移除基准元素 #

如果你的quicksort函数没有把基准元素从待拆分列表中移除（比如直接把整个原列表传给splitBy），会导致基准元素被重复包含在子列表中，要么引发无限递归，要么打乱排序顺序。

修复示例 #

假设你要实现标准的非尾递归快排，正确的代码应该是这样：

正确的splitBy函数 #

splitBy :: Int -> [Int] -> ([Int], [Int])
splitBy pivot xs = (left, right)
  where
    -- 小于等于基准的元素放到左列表
    left = [x | x <- xs, x <= pivot]
    -- 大于基准的元素放到右列表
    right = [x | x <- xs, x > pivot]

正确的quicksort函数 #

quicksort :: [Int] -> [Int]
quicksort [] = []
-- 取出第一个元素作为基准，拆分剩下的元素
quicksort (pivot:rest) = quicksort left ++ [pivot] ++ quicksort right
  where (left, right) = splitBy pivot rest

验证修复后的效果 #

对于你的第二个测试用例，基准是3687（列表最大值），splitBy会返回：

• left：所有小于等于3687的元素（也就是rest里的全部元素）
• right：空列表

递归时quicksort right返回空，quicksort left会正常排序剩下的元素，最后合并为排序后的left ++ [3687] ++ []，得到正确的排序结果。

额外排查建议 #

如果修复后还是有问题，可以单独测试splitBy的功能，比如：

*Main> splitBy 3687 [324,675,238,1237,345,12,45,1,434,2,1,33,43]
-- 预期输出：([324,675,238,1237,345,12,45,1,434,2,1,33,43], [])

如果输出不符合预期，就说明splitBy的条件确实写错了，调整一下即可。

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