如何让Haskell实现的冒泡排序函数递归重复直至列表完全排序？

你的当前代码只完成了单次冒泡遍历——也就是把列表中最大的元素“冒”到末尾，但没有重复对剩余的未排序部分执行这个过程，因此只能处理短列表（比如长度4的列表可能刚好一次遍历就有序），但更长的列表只会把最大元素移到最后，前面的元素仍然无序。

下面提供两种可行的修复方案：

方法1：递归处理未排序的前n-1个元素 #

先实现单次遍历的函数bubblePass（复用你原来的遍历逻辑），然后主排序函数递归对单次遍历后的前n-1个元素排序，再拼接上已经排好的最大元素：

-- 单次冒泡遍历：将最大元素移到列表末尾
bubblePass :: Ord a => [a] -> [a]
bubblePass [] = []
bubblePass [x] = [x]
bubblePass (x:y:xs)
    | x <= y    = x : bubblePass (y:xs)
    | otherwise = y : bubblePass (x:xs)

-- 完整冒泡排序：递归处理前n-1个元素
bsort :: Ord a => [a] -> [a]
bsort [] = []
bsort xs = let passed = bubblePass xs
           in bsort (init passed) ++ [last passed]

方法2：循环直到列表完全有序 #

另一种更直观的方式是，不断调用单次遍历函数，直到遍历后的列表和原列表完全相同（说明已经有序）：

bubblePass :: Ord a => [a] -> [a]
bubblePass [] = []
bubblePass [x] = [x]
bubblePass (x:y:xs)
    | x <= y    = x : bubblePass (y:xs)
    | otherwise = y : bubblePass (x:xs)

bsort :: Ord a => [a] -> [a]
bsort xs = let passed = bubblePass xs
           in if passed == xs then xs else bsort passed

测试验证 #

对于输入bsort [9,6,1,5,2,4]，两种方法都会返回正确的有序列表[1,2,4,5,6,9]；输入bsort [1,5,2,4]也能正常得到[1,2,4,5]。

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