sorting - 在 SML 中使用 Foldl 或 Foldr 编写冒泡排序

Question

有没有办法使用 SML 中提供的 Foldl 或 Foldr 方法来实现冒泡排序？任何指导都会有所帮助。

Answer 1

我刚刚用 OCaml 编写了一个实现，以让我自己满意地演示该技术。

我将排序过程分为两部分。一种是通过fold_left (foldl) 调用的比较和交换函数。该函数的类型( bool 值表示本次扫描中是否发生交换):

bool * 'a list -> 'a -> bool * 'a list

每次运行时，它都会在适当的情况下进行交换，在其结果中构建一个新列表，该列表以与输入相反的顺序组成。 (这是必要的，因为 Foldl 的从左到右、尾递归行为。)它还跟踪在列表扫描中是否进行了任何交换(这是必要的，以便我们知道何时停止排序)。

另一个函数是递归的，只是不断调用扫描，直到没有发生任何更改。该函数还有一个 bool 值，它在每次调用时切换以跟踪列表当前是否已反转。当它发现最近一次扫描中没有进行交换时，它会返回结果列表。如果列表当前已反转，那么它会在返回之前最后一次反转它。

这是第二个函数的类型(这里的bool是列表当前是否反转):

bool -> 'a list -> 'a list

应该同样可以编写使用foldr 的冒泡排序。它不会是尾递归的(因为foldr不是)，并且由于它从右到左扫描列表，因此您不必处理foldl所遇到的反转问题。