ML中的快速排序

Question

没有使用大小写表达式（在类的下一节出现），我看不出为什么以下不做快速排序。它在某个地方进入循环，永远不会结束。

splitAt和append已经过测试，但这里是他们的代码。

fun append(xs, ys) = 
if null xs 
then ys 
else (hd xs) :: append(tl xs, ys) 

fun splitAt(xs : int list, x : int) = 
let 
    fun sp(ys : int list, more : int list, less : int list) = 
     if null ys 
     then (more, less) 
     else 
      if hd ys < x 
      then sp(tl ys, more, append(less, [hd ys])) 
      else sp(tl ys, append(more, [hd ys]), less) 
in 
    sp(xs, [], []) 
end 

fun qsort(xs : int list) = 
    if length xs <= 1 
    then xs 
    else 
    let 
     val s = splitAt(xs, hd xs) 
    in 
     qsort(append(#2 s, #1 s)) 
    end 

我也得到使用追加（快速排序（＃2秒），快速排序（＃1秒））同样的问题，但我虽然前者是更好的风格，因为它仅需要每一轮单一的递归。 我想我应该说'splitAt'将列表分成大于或等于第二个参数，小于，并创建一个元组）。附加连接2个列表。 PS：这只是一个实践问题，而不是测试或家庭作业。

Answer 1

它进入一个循环的某个地方，永远不会结束。

您的问题很可能是qsort在递归调用时不会减小大小的列表上调用。也许去append(qsort (#2 s), qsort (#1 s))。但即使如此，你能确定每个#1 s和#2 s的尺寸总是会减小吗？

理想情况下，您应该提供splitAt和append，因为它们不是库函数。您可以考虑使用名为@的内置追加程序和内置的List.partition来形成splitAt。

比较反对这一个地方发现了interwebs：

fun quicksort [] = [] 
    | quicksort (x::xs) = 
    let 
     val (left, right) = List.partition (fn y => y < x) xs 
    in 
     quicksort left @ [x] @ quicksort right 
    end 

Answer 2

因为这不是功课...

注意，如果xs = [1,2]然后splitAt(xs hd xs)回报([1,2],[])所以试图通过这种[1,2]版本的qsort简化为...再排序[1,2]。那永远不会终止。

取而代之的是，我会主张将splitAt应用于xs的尾部。一个最小的调整你的代码是离开append和splitAt独自但重写qsort为：

fun qsort(xs : int list) = 
    if length xs <= 1 
    then xs 
    else 
    let 
     val s = splitAt(tl xs, hd xs) 
    in 
     append(qsort(#2 s), (hd xs) :: qsort(#1 s)) 
    end; 

然后，例如，

- qsort [4,2,1,2,3,6,4,7]; 
val it = [1,2,2,3,4,4,6,7] : int list 

至关重要的是，你申请qsort两次，然后追加结果。 Tryng将qsort应用一次到附加分割将试图减少qsort到应用qsort到与原始列表大小相同的列表。

当你进行模式匹配时，SML真的变得很有趣。你应该享受下一章。