方案快速排序与过滤

Question

我需要写的函数（快速排序PRED LST） LST是号码列表进行排序 PRED是通过列表进行排序的谓词，签名这个断言的是：（拉姆达（XY）...）

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

现在我想用预解码做到这一点：

(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 ...)将覆盖<=而不是<的问题，反之亦然。所以它被卡住了，因为列表中的第一个元素总是与自身相等。

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

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