在球拍中作为参数的比较函数

Question

我已经在球拍中实现了如下选择排序：

#lang racket
(define (selection-sort lst)
  (cond [(empty? lst) '()]
        [else (define first (apply min lst))
              (cons first (selection-sort(remove first lst)))]))

(selection-sort (list 5 4 3))

然而，我被要求我的函数接受一个比较函数以及我的列表，选择排序应该根据比较函数以升序返回一个列表。

我在理解这个比较函数时遇到了问题，我需要对代码做哪些修改？

Answer 1

请记住，当前的实现效率很低，你在那里做了很多额外的循环:当找到最小值时，当删除它时。

话虽如此，我们可以通过编写自己的接收任意比较函数的min来调整代码以接收比较函数-因为隐含地，min使用的是<。如下所示：

(define (selection-sort lst cmp)
  (cond [(empty? lst) '()]
        [else (define amin (mymin cmp lst))
              (cons amin (selection-sort (remove amin lst) cmp))]))

(define (mymin cmp lst)
  ; assuming non-empty list
  (cond [(empty? (rest lst))
         (first lst)]
        ; call the recursion
        [else (define amin (mymin cmp (rest lst)))
              ; use the comparison function
              (cond [(cmp (first lst) amin) (first lst)]
                    [else amin])]))

它的工作方式与预期一致：

; ascending order, this was the default behavior
(selection-sort (list 5 4 3) <)
=> '(3 4 5)
; same as above
(selection-sort (list 5 4 3) (lambda (x y) (< x y)))
=> '(3 4 5)
; descending order
(selection-sort (list 5 4 3) >)
=> '(5 4 3)