0

这是我实现快速排序的尝试：

(define (sublist ls start stop middle)
 (cond ( (null? ls) ls)
     ( (< middle start) (sublist (cdr ls) start stop (+ middle 1)))
     ( (> middle stop) '() )
     (else
        (cons (car ls) (sublist (cdr ls) start stop (+ middle 1))))))

(define (split5 ls)                                      
  (let ((len (length ls)))
   (cond ((= len 0) (list ls ls) )
         ((= len 1) (list ls '() ))
         (else 
          (list (sublist ls 1 (/ len 2) 1)
                (sublist ls (+(/ len 2)1) len 1))))))

;this divides the sorted list into two sublists 
(define (dividelist rel? ls)
 (split5 (order rel? ls)))


(define (quicksort rel? ls)
 (if (null? (cdr ls)) ls
  (let ((pivot (list-ref (sort rel? ls) (round (/ (length (sort rel? ls)) 2))))
        (left (car (dividelist rel? ls)))
        (right (cdr (dividelist rel? ls))))
        (join left pivot right))))

我知道这种实现效率很低，但我想不出办法。无论如何，它真的不起作用。

When I input this:
(quicksort < '(9 3 -5 8 -7 2 9))
It gives me this:
(-7 -5 2 8 (8 9 9))
It should give me this:
(-7 -5 2 3 8 9 9)

我怎样才能解决这个问题？

编辑

(define (join ls1 goo ls2)
  (if (null? ls1) (cons goo ls2)
      (if (null? ls2) (cons goo ls1)
          (cons (car ls1) (join (cdr ls1) goo ls2)))))
4

1 回答 1

1

假设该过程与代码中下面几行使用order的过程相同（等等，您正在使用排序过程来实现排序过程？！）并且这是某种，我可以得出结论，列表创建问题在于您的. 将其更改为此以修复它：sortjoinappendjoin

(define (join left pivot right)
  (append* left (list pivot) right))

现在该过程将返回一个list，因为它应该：

(quicksort < '(9 3 -5 8 -7 2 9))
=> '(-7 -5 2 8 8 9 9)

哎呀，号码3去哪儿了？您的代码中有一个错误，您必须找到它！提示：计算枢轴的代码非常错误。

编辑

这是快速排序的正确、无忧实施。请注意，在像这样的简单实现中，选择第一个元素作为枢轴就足够了：

(define (quicksort cmp lst)
  (if (null? lst)
      '()
      (let ((x  (car lst))
            (xs (cdr lst)))
        (append (quicksort cmp (filter (lambda (e) (cmp e x)) xs))
                (list x)
                (quicksort cmp (filter (lambda (e) (not (cmp e x))) xs))))))

或者稍微花哨和更短，使用 Racket 的高阶程序：

(define (quicksort cmp lst)
  (if (empty? lst)
      empty
      (let ((x  (first lst))
            (xs (rest  lst)))
        (append (quicksort cmp (filter-not (curry cmp x) xs))
                (cons x (quicksort cmp (filter (curry cmp x) xs)))))))

还有另一种可能性，partition用于在一个步骤中获取两个分区（枢轴之前的元素和枢轴之后的元素） - 它更有效：

(define (quicksort cmp lst)
  (if (empty? lst)
      empty
      (let-values (((greater-than less-equal)
                    (partition (curry cmp (first lst)) (rest lst))))
        (append (quicksort cmp less-equal)
                (cons (first lst) (quicksort cmp greater-than))))))

无论如何，它按预期工作：

(quicksort < '(9 3 -5 8 -7 2 9))
=> '(-7 -5 2 3 8 9 9)
于 2013-04-01T22:03:51.140 回答