2

我想编写一个程序来获取未排序的列表（可能包括重复值）并使用“累积”又名 foldr、reduce 等对其进行排序。

我成功过滤了双精度值，但无法对其进行排序。一般来说，我看不到如何使用地图、过滤器、累积...对其进行排序。

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

这是我现在的代码

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

4

3 回答 3

3

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

累积值是迄今为止看到的所有值的排序列表。当看到一个新值时，它会被插入到正确位置的排序列表中。对此使用相同insert的方法，就像在插入排序的普通实现中一样。

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

于 2012-05-11T16:02:35.323 回答
1

另一种方法是树排序，它类似于插入排序（@soegaard 的解决方案），但时间复杂度更高。在这里，您从一棵空树作为初始值开始，并在每次折叠迭代时构建树。

于 2012-05-11T16:33:10.350 回答
1

借用@soegaards 的答案：首先定义一个插入过程，给定一个元素、一个比较过程和一个列表，根据比较过程返回一个包含元素的新列表：

(define (insert-in-order e cmp lst)
  (cond ((null? lst)
         (list e))
        ((cmp e (car lst))
         (cons e lst))
        (else
         (cons (car lst) (insert-in-order e cmp (cdr lst))))))

foldr现在您可以根据and实现插入排序过程insert-in-order，它接收要排序的列表和比较过程作为参数：

(define (insertion-sort lst cmp)
  (foldr (lambda (e acc)
           (insert-in-order e cmp acc))
         '()
         lst))

像这样使用它：

(insertion-sort '(4 5 1 1 2 3) <) ; ascending order
> '(1 1 2 3 4 5)

(insertion-sort '(4 5 1 1 2 3) >) ; descending order
> '(5 4 3 2 1 1)
于 2012-05-12T17:51:45.093 回答