如何在Racket中生成升序列表？合并两列表后升序实现咨询

你的merge-tail目前是交替取两个列表的元素，并没有按大小比较排序。要实现合并后升序排列，分两种场景处理：

场景1：先排序输入列表，再用尾递归合并有序列表 #

原merge-tail并非真正的尾递归（递归调用后还有cons操作），如果可以先将两个输入列表各自排序，再用尾递归的merge函数合并已排序列表，步骤如下：

1. 实现尾递归的有序列表合并函数：

(define (merge-sorted-tail l1 l2)
  (let loop ([l1 l1] [l2 l2] [acc '()])
    (cond
      [(empty? l1) (append (reverse acc) l2)]
      [(empty? l2) (append (reverse acc) l1)]
      [(<= (car l1) (car l2))
       (loop (cdr l1) l2 (cons (car l1) acc))]
      [else
       (loop l1 (cdr l2) (cons (car l2) acc))])))

这里用累加器acc实现尾递归，最后反转累加器得到正确的升序顺序。

2. 调用时先对输入列表排序，再传入合并函数：

(merge-sorted-tail (sort '(15 8 42) <) (sort '(24 54 7) <))
; 输出: '(7 8 15 24 42 54)

场景2：直接合并后排序（简单实现） #

如果不需要严格遵循归并思路，直接合并两个列表后用尾递归排序也可以，比如实现尾递归的插入排序：

(define (insert-sorted-tail lst)
  (let loop ([lst lst] [acc '()])
    (if (empty? lst)
        acc
        (let ([elem (car lst)])
          (loop (cdr lst)
                (let insert ([acc acc])
                  (cond
                    [(empty? acc) (list elem)]
                    [(<= elem (car acc)) (cons elem acc)]
                    [else (cons (car acc) (insert (cdr acc)))])))))))

; 合并后排序
(insert-sorted-tail (append '(15 8 42) '(24 54 7)))
; 输出: '(7 8 15 24 42 54)

关键说明 #

• 原merge-tail不符合尾递归定义：因为cons操作在递归调用之后执行，递归结果还需进一步处理，不是最后一步操作。
• 场景1效率更高：归并排序时间复杂度为O(n log n)，场景2的插入排序为O(n²)，数据量大时优先选场景1。

内容的提问来源于stack exchange，提问作者ktt779