Racket 中作为参数的比较函数

Question

我在 Racket 中实现了如下选择排序：

#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))

但是我被要求在我的函数中加入一个比较函数和我的列表，并且选择排序应该 return 根据比较函数以升序排列的列表。

我无法理解比较函数的这一点，我需要对代码进行哪些更改？

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)

Racket 中作为参数的比较函数

Comparison Function as Parameter in Racket

sorting

programming-languages

function

racket