比较功能作为球拍中的参数

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)