在球拍中插入排序，不知道为什么这不起作用

Question

我是球拍新手，我试图找出插入排序。这是我的，但我得到一个错误，并且我无法从调试中找出它。

;Definition of insert: inserts a number into an already sorted list based on 
;the cmp parameter 
;cmp: <or>, L1: a list, n: the number to be inserted 
(define (insert cmp L1 n) 
    (cond 
    ((null? n) (list L1)) 
    ((null? L1) (cons n L1)) 
    ((cmp n (car L1)) (cons n L1)) 
    (else (cons (car L1) (insert cmp (cdr L1) n))) 
    ) 
) 

;Definition of insertionSort: sorts a list based on a recursive insertion sort 
;L1: a list, cmp: <or> 
(define (insertionSort L1 cmp) 
    (cond 
    ((null? L1) L1) 
    (else (insert cmp (car L1) (insertionSort(cdr L1) cmp))) 
) 
) 

Answer 1

以下功能正常工作：

(define (insert n l cmp (ol '())) 
    (cond 
    [(empty? l) 
    (append ol (list n))] ; or: (reverse (cons n (reverse ol))) 
    [(not (cmp n (first l))) 
    (append ol (list n) l)] 
    [else (insert n 
        (rest l) 
        cmp 
        (append ol (list (first l))) ; or: (reverse (cons (first l) (reverse ol))) 
       )])) 

(define (isort l cmp (sl '())) 
    (cond 
    [(empty? l) sl] 
    [else (isort (rest l) 
       cmp 
       (insert (first l) 
         sl 
         cmp))])) 

这些功能似乎是尾递归。

测试：

(isort '(4 2 5 8 1 4 7 3 6 9) >) 
(isort '(4 2 5 8 1 4 7 3 6 9) <) 

输出：

'(1 2 3 4 4 5 6 7 8 9) 
'(9 8 7 6 5 4 4 3 2 1) 

Answer 2

您已经为insert当你insertionSort使用 “翻转” 的观点;它应该是

(define (insertionSort L1 cmp) 
    (cond 
    ((null? L1) L1) 
    (else (insert cmp (insertionSort (cdr L1) cmp) (car L1)))))