Racket递归实现mergesort函数作业问题求助

你需要用递归实现Racket的mergesort函数，要求接收列表后拆分为更小的子列表，升序排序且不能使用内置排序命令，最终返回排序后的列表。你当前的代码如下：

(define (mergesort lst)
  (cond
    [(empty? lst) '()]
    [(= (length lst) 1) lst]
    [(let* ([index 0][end_index (- (length lst) 1)])
       (if (< (list-ref lst index) (list-ref lst (add1 index)))
           (cons...)
           (cons...) 
           ))]
    )
  )

(mergesort '(3 1 2 7 9)) ;should return (1 2 3 7 9)

你现在的困惑是：满足if条件时如何将元素移动到正确的升序位置，想确认当前思路是否正确。

你的当前思路不正确，因为这是在尝试逐个比较相邻元素，更接近冒泡排序的逻辑，而非归并排序的核心思想。归并排序的核心是拆分+合并，具体步骤是：

• 拆分：将原列表不断拆分为左右两个大致相等的子列表，直到每个子列表只剩单个元素（单个元素本身就是有序的）
• 合并：编写一个辅助函数，将两个已经排好序的子列表合并成一个新的有序列表

正确实现代码 #

首先实现合并两个有序列表的辅助函数merge：

; 合并两个已排序的列表，返回升序排列的新列表
(define (merge left right)
  (cond
    [(empty? left) right]
    [(empty? right) left]
    [(< (car left) (car right))
     (cons (car left) (merge (cdr left) right))]
    [else
     (cons (car right) (merge left (cdr right)))]))

然后实现主函数mergesort，负责拆分列表并递归排序后合并：

(define (mergesort lst)
  (cond
    [(empty? lst) '()]
    [(= (length lst) 1) lst]
    [else
     (let* ([mid (quotient (length lst) 2)]  ; 计算拆分的中间位置
            [left (take lst mid)]           ; 取前mid个元素作为左子列表
            [right (drop lst mid)])         ; 取剩余元素作为右子列表
       (merge (mergesort left) (mergesort right)))]))  ; 递归排序左右子列表后合并

测试验证：

(mergesort '(3 1 2 7 9)) ; 返回 (1 2 3 7 9)

细节说明 #

• merge函数通过递归比较两个有序列表的首元素，每次选择较小的元素加入结果，直到其中一个列表为空，直接拼接剩余列表
• mergesort函数中，用quotient计算中间位置（避免奇数长度列表出现小数），用take和drop拆分列表，递归对左右子列表排序后，调用merge合并结果

如果不允许使用take和drop，可以自己实现拆分函数：

; 自定义拆分函数，将列表拆分为左右两个大致相等的子列表
(define (split lst left right)
  (cond
    [(empty? lst) (list left right)]
    [(<= (length left) (length right))
     (split (cdr lst) (append left (list (car lst))) right)]
    [else
     (split (cdr lst) left (append right (list (car lst))))]))

; 修改后的mergesort
(define (mergesort lst)
  (cond
    [(empty? lst) '()]
    [(= (length lst) 1) lst]
    [else
     (let* ([split-result (split lst '() '())]
            [left (car split-result)]
            [right (cadr split-result)])
       (merge (mergesort left) (mergesort right)))]))

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