方案 - 使用積累

Question

我想寫的是得到一個未排序列表中的程序（可能包括重複的值），並使用「積累」又名foldr相似排序呢排序，減少等

我成功地過濾雙重價值但無法排序。 Generaly我看不到我怎麼可以使用地圖，過濾，排序積累吧....

我必須完成它，而無需使用插入排序，冒泡排序....

這是我的代碼現在（lambda（x no-duplicate））（cons x（filter（lambda（z）（not（= xz）））no-duplicate）））'（）（list 1 2 0 66 3 4） ）

Answer 1

您可以簡單地實現插入排序。

累計值是到目前爲止所有值的排序列表。 當看到一個新值時，它將被插入排序列表 的正確位置。爲此，請使用相同的insert，因爲您的 會在插入排序的普通實現中使用。

那你必須寫的是給定一個元素x和排序列表ys返回包含x和在ys所有元素排序列表的功能insert。使用此函數累計，一次構建一個元素的最終結果。

Answer 2

另一種方法是tree sort，它與插入排序（@ soegaard的解決方案）類似，但具有更好的時間複雜性。在這裏，你從一棵空樹開始作爲初始值，並在每次迭代迭代時建立樹。

Answer 3

從@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和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)