带滤波器的快速排序方案

Question

我需要编写函数(快速排序pred lst) lst是要排序的数字列表pred是对列表进行排序的谓词，该谓词的签名是：(lambda (x )…)

- (quick-sort < lst) will sort ascending (small to large)
- (quick-sort > lst) will sort descending (large to small)
- (quick-sort (lambda (x y) (< (car x) (car y))) lst) will sort a list
with inner lists according to the first element of the inner list, ascending.

我从常规的快速排序开始：

(define (quick-sort lst)
  (cond
    ((null? lst)        '())
    ((= (length lst) 1) lst)
    (else               (append (quick-sort (filter (lambda (n) (< n (car lst))) lst))
                                (list (car lst))
                                (quick-sort (filter (lambda (n) (> n (car lst))) lst))))))

现在我试着用pred做这个：

(define (quick-sort pred lst)
  (define (quick-sort-help lst)
    (cond   ((null? lst) ())
        ((= (length lst) 1) lst)
        (else 
            (append (quick-sort-help (filter (lambda (n) (pred n (car lst))) lst))
                (list (car lst))
                (quick-sort-help (filter (lambda (n) (not(pred n (car lst)))) lst)))))) (quick-sort-help lst))

我得到了无限递归什么的。

你能帮我解决这个问题吗？谢谢!

Answer 1

首先，您不需要助手函数quick-sort-help。

由于您将助手函数应用于lst而不是cdr lst，所以它会无限地递归。在常规的快速排序中，有(filter (lambda (n) (< n (car lst)))和(filter (lambda (n) (> n (car lst)))。但是，在带有谓词的例子中，如果谓词是(not (pred ...)，那么(not (pred ...)将涵盖<=的情况，而不是<的情况，反之亦然。所以它被卡住了，因为列表中的第一个元素总是与它本身相等。

这里有一个正确的快速排序：

(define (qsort f lst)
  (if (null? lst)
      null
      (let ([pivot (car lst)])
        (append (qsort f (filter (λ (n) (f n pivot)) (cdr lst)))
                (list pivot)
                (qsort f (filter (λ (n) (not (f n pivot))) (cdr lst)))))))