sorting - scheme - 使用 accumulate 排序

Question

我想编写一个程序来获取未排序的列表(可能包含重复值)并使用“累积”a.k.a foldr、reduce 等对其进行排序

我成功过滤了 double 值，但无法对其进行排序。一般来说，我看不出如何使用 map 、过滤器、累积...对其进行排序。

我必须在不使用插入排序、冒泡排序的情况下完成它....

这是我现在的代码

(accumulate (lambda (x no-duplicate) (cons x (filter (lambda (z) (not (= x z))) no-duplicate))) '() (list 1 2 0 66 3 4 ))

Answer 1

您可以简单地实现插入排序。

累积值是迄今为止看到的所有值的排序列表。当看到一个新值时，它被插入到排序列表中在正确的地方。为此，请使用与您相同的 insert将在插入排序的普通实现中。

您必须编写一个函数insert，它给定一个元素x 和一个排序列表ys，返回一个包含x 和ys 中的所有元素。将此函数与 accumulate 结合使用，一次构建一个元素的最终结果。