快速排序方案

Question

我需要實現以下快速排序： （快速排序預解碼LST） 地表溫度進行排序 預計值的號碼列表是由列表進行排序的謂詞，這個謂詞的簽名是： （lambda（xy）...）

這裏的代碼正在工作，但這裏的問題是，當我在lst獲得相同的數字，然後一旦im進入無限循環，經過數小時的調試後，我無法找到問題或如何解決它。

(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

如果您在分區之前刪除了數據透視表，則可以保證在每個遞歸步驟都取得進展。如果沒有這種措施，樞軸將會粘在其分區的前部，您將無法獲得任何位置。