QuickSort方案

Question

我需要实现以下快速排序：(quick-sort pred lst) lst是要排序的数字列表pred是该列表的排序依据，此谓词的签名为：(lambda (x，y)…)

这里的代码是有效的，但这里的问题是，当我进入相同的数字时，当我进入无限循环时，经过几个小时的调试，我找不到问题或如何解决它。

(define (quick-sort pred lst)

;Pivot is 1st element of the list
 (define (pivot lst)
  (if (or (null? lst) (= 1 (length lst)))
    'done
     (car lst)))

 partition get the pivot the list and the predicate and splitting it to two lists
  (define (partition piv lst pred)

    ;predPos is the pred it slef and predNeg is the negative of the pred
     (let* ((predPos (lambda (x) (pred x piv) )) 
            (predNeg (lambda (x) (if (pred x piv) #f #t)))

            ;Filtering the big list in to two lists
            (p1 (filter predPos lst))
            (p2 (filter predNeg lst)))

          ;Recursivly doing the qucicksort on each list. and joining them together.
           (cond ((and (null? p1) (null? p2)) (cons piv ()))
                 ((null? p1) (quick-sort pred p2))
                 ((null? p2) (quick-sort pred p1))
                 (else (joiner (quick-sort pred p1) (quick-sort pred p2))))))


      ;Joining 2 lists together
      (define (joiner p1 p2)
      (cond ((null? p1) p2)
            ((null? p2) p1)
            (else (cons  (car p1) (joiner (cdr p1) p2)))))

 ;The main quicksort method () and list size one are sorted!
 (let ((piv (pivot lst)))
   (if (or (null? lst) (= 1 (length lst)))
      lst
      (partition piv lst pred))))

Answer 1

如果您在分区之前删除了pivot，则可以保证在每个递归步骤中都会取得进展。如果没有这一措施，轴心将停留在其分区的前面，您将无法到达任何位置。