使用循环进行插入排序方案

Question

最近，我第一次学会了略读。我尝试使用一个方案来实现插入对齐。但是，在这个时候，我尝试只使用map、for-each和let循环等迭代来实现它，而不使用递归。但它没有成功，也没有付诸实施。当我尝试实现以下代码时，短语“宏名用作变量”和"set!“出现，导致语法错误。

(define tlst '())
(define (insertion-sort lst)
  (for-each
   (lambda (x)
     (let loop ((temp-lst (cdr(member i (reverse lst)))))
       (cond
        ((> x (car temp-lst)) set! lst (append (reverse(cdr temp-lst))(append i ((member (car temp-lst) (lst))))) )
        (else (loop (cdr temp-lst)))
        )
       )
     )
   lst
   )
  )

我居住的地方不是一个讲英语的国家，所以我写了一篇文章，因为我不能仅仅用我的语言获得相关的知识。

Answer 1

递归插入排序示例来自普利采什·什里瓦斯塔瓦

; sorts a list l in increasing order
; List-of-numbers -> List-of-numbers
(define (insertion-sort l)
  (cond
    [(null? l) '() ]
    [else (insert (car l) (insertion-sort (cdr l))) ]))

; We now define the 'insert' function from our wish list, after which our problem is solved.
; Helper function that inserts a number n into a sorted list of numbers l at its correct position 
; Number List-of-numbers -> List-of-numbers
(define (insert n l)
  (cond
    [(null? l) (cons n '()) ]
    [else (if (<= n (first l))
              (cons n l)
              (cons (car l) (insert n (cdr l)))) ]))

; testing the insert sort function with an example
(insertion-sort '(72 45 43 29 34))

可以将insertion-sort中的递归调用替换为命名的let中的“累加器参数”：

(define (insertion-sort l) ;; List-of-numbers -> List-of-numbers
  ;; produce copy of l sorted in increasing order
  (let build-result ([l l] [result '()])
    (cond
      [(null? l) result ]
      [else (build-result (cdr l) (insert (car l) result)) ])))

( build-result调用处于尾部位置，因此这是一种迭代计算。)

类似地，在insert中(由cons构建的部分结果，因此需要reverse)：

(define (insert n l) ;; Number List-of-numbers -> List-of-numbers
  ;; produce result of inserting n into sorted l (may share tail of l)
  (let insert-n ([l l] [result '()])
    (cond
      [(null? l) (append (reverse result) (list n)) ]
      [else (if (<= n (first l))
                (append (reverse result) (list n) l)
                (insert-n (cdr l) (cons (first l) result))) ])))