在没有快速排序的情况下对数字列表进行排序时出现递归错误

Question

order :: [Int] -> [Int]
order [] = []
order [x] = [x]
order (x:y:xs) = if x>y
then [y] ++ (order (x:xs))
else [x] ++ (order (y:xs))

我尝试使用此 Haskell 代码对数字列表进行排序，但是当我输入包含 4 个以上元素的列表时，它无法正确排序。我想保留编译的代码，但我不知道如何使递归正常工作。

Answer 1

代码很好，完全按照你实现的方式执行，但你实现的内容实际上并没有对列表进行排序。 让我们用[4,3,2]试试：

order [4,3,2]
order [] = []               -- Nope not an empty list
order [x] = [x]             -- nope not a singleton
order (x:y:xs) = if x>y     -- x=4, y=3, xs =[2]; x >y  is true
then [y] ++ (order (x:xs))  -- this branch [3] ++ (order [4,2])
else [x] ++ (order (y:xs))  -- not this branch

所以我们到了[3] ++ (order [4,2]). 问你：2如何移动到3的另一边？