标准 ML：使用数组的冒泡排序

Question

我正在尝试使用数组实现冒泡排序，但我很难做到。这是我目前所拥有的：

fun swap(A, i, v) = 
    let 
        val temp = sub(A, i);
    in
        update(A, i, sub(A, v));
        update(A, v, temp)
    end;

这需要固定的时间，所以到目前为止一切都很好。

异常为空；

fun bubbleSort(nil, i) = raise Empty
    (* if has one element, already sorted)
    | bubbleSort(
    (* if at least two elements, compare *)
    | bubbleSort(A, i) = 
        if i < A.length then
            if sub(A, i) > sub(A, i+1) then
                swap(A, i, i+1)
            else bubbleSort(i+1);

1) 现在，这只会遍历 >= 2 个元素的数组一次。但是冒泡排序算法一直持续到您不再需要交换元素为止，我不确定如何递归地实现它。

2) 我们如何在长度为 1 的数组上进行模式匹配？对于列表，它只是 bubbleSort([x])...

任何帮助实施都会很棒，克莱曼

Answer 1

要回答您的第一个问题，一种方法是向您的 bubbleSort 函数添加一个额外的参数来确定您是否已达到固定点。您的函数将具有以下类型

bubbleSort : int Array -> int -> bool -> int Array

在每次迭代中，如果您实际执行交换，则将标志设置为真。一旦你遍历了整个数组，然后检查标志是否已设置，如果是，则将 i 重置为 0。不断重复此过程，直到你完全通过而不设置标志。

阵列上的模式匹配不是通常要做的事情，您可以为向量做（参见 this link，请注意这是 SML/NJ 特定的），但是，您最好只使用长度函数。这样，甚至不需要拆分前两个案例。您可以简单地检查长度是否小于 1，如果是，return 数组而不进行任何交换。

标准 ML：使用数组的冒泡排序

Standard ML: BubbleSort with Arrays

arrays

functional-programming

sml