方案:实现快速排序

Question

我正在尝试使用一个快速的排序方案，这里的一些人已经帮我修复了我的split函数，现在我请求您帮助将所有的东西组合成一个工作的算法。

到目前为止，我的代码如下：

(define quick-sort (lambda (lst)

                 (define pivot (lambda (lst)
                                 (if (null? lst)
                                     null
                                     (car lst))))
                 (define split (lambda (lst pivot)
                                 (define lst1 null)
                                 (define lst2 null)
                                 (define split-helper (lambda (lst pivot lst1 lst2)
                                                        (if (null? lst)
                                                            (list lst1 lst2)
                                                            (if (<= (car lst) pivot)
                                                                (split-helper (cdr lst) pivot (cons (car lst) lst1) lst2)
                                                                (split-helper (cdr lst) pivot lst1 (cons (car lst) lst2))))))
                                 (split-helper lst pivot lst1 lst2)))

                 (if (null? lst)
                            null
                            (append (quick-sort (car (split lst (pivot lst)))) (quick-sort (cdr (split lst (pivot lst))))))))

正如你所看到的，我选择枢轴只是为了成为列表中的第一个元素，我面临的问题是当这个枢轴是列表中最小的元素时，程序会陷入一个无限循环，因为它让程序一次又一次地选择相同的枢轴。

而且，它目前的实现方式使得它实际上是无效的，因为split函数在每个quick-sort的惰性中都用相同的lst被调用两次，但是我对Scheme没有足够好的控制，无法用其他方式编写它。

我看到了一些关于快速排序的帖子，但是它们的实现有点不同，我宁愿尝试纠正我自己的实现，也不愿抄袭其他人的作品。

谢谢。

Answer 1

删除过多的lambdas、别名、绑定和重新格式化，但没有更改或注释语义(Sylwester已经指出了错误)：

(define (quick-sort lst)
   (define (pivot lst)
      (if (null? lst)
         '()
         (car lst) ))
   (define (split lst pivot)
      (let split-helper ((lst lst)         ; Named let instead of internal
                         (lst1 '())        ; definition
                         (lst2 '()) )
         (if (null? lst)
            (cons lst1 list2)
            (if (<= (car lst) pivot)
               (split-helper (cdr lst)
                             (cons (car lst) lst1)
                             lst2)
               (split-helper (cdr lst)
                             lst1
                             (cons (car lst) lst2) )))))
   (if (null? lst)
      '()
      (let ((spl (split lst (pivot lst)))) ; Memoization of the `split`
         (append (quick-sort (car spl))
                 (quick-sort (cdr spl)) ))))

我想你是在尝试实现一个partition

(define (partition pred xs)
   (let part ((ps '()) (ns '()) ; Initial "positives" `ps`, and "negatives" `ns`
              (xs' xs) )
      (if (null? xs')
         (cons ps ns)             ; Returning pair of lists
         (let ((x (car xs')))     ; Memoization of `(car lst)`
            (if (pred x)
               (part (cons x ps) ns (cdr xs'))
               (part ps (cons x ns) (cdr xs')) )))))

(define (quicksort xs)
   (if (null? xs) '()
      (let* ((x (car xs))
             (pn (partition               ; Memoization of `partition`
                    (lambda (x')
                       (< x' x) )
                    (cdr xs) )))
         (append (quicksort (car pn))      ; Extracting positives from pair
                 (list x)                  ; Pivot
                 (quicksort (cdr pn)) )))) ; Negatives


(display
   (quicksort (list 4 2 3 5 1)) )    ; (1 2 3 4 5)

在诸如Scheme这样的严格语言中，part效率低下；它在每一个递归步骤中都复制它的所有三个参数。通常，以基本折叠(如filter和map )为基础的直截了当的公式最有效。使用filter更有效的实现

(define (quicksort xs)
   (if (null? xs) '()
      (let ((x (car xs))
            (xs' (cdr xs)) )
         (append (quicksort
                    (filter (lambda (x')
                               (< x' x) )
                            xs'))
                 (list x)
                 (quicksort
                    (filter (lambda (x')
                               (>= x' x) )
                            xs'))))))

众所周知，这种策略在函数式语言中非常简单地表达。

在懒惰的Haskell中，单次遍历partition实际上比filter执行两次更有效。

select :: (a -> Bool) -> ([a], [a]) -> a -> ([a], [a])
select pred (ps, ns) x | pred x    = (x : ps, ns)
                       | otherwise = (ps, x : ns)

partition :: (a -> Bool) -> [a] -> ([a], [a])
partition pred  =  foldl (select pred) ([], [])

quicksort :: Ord a => [a] -> [a]
quicksort []       = []
quicksort (x : xs) = let (lt, gt) = partition (< x) xs
                     in  quicksort lt ++ [x] ++ quicksort gt

Answer 2

说到快速排序，这是一个经典的错误。您的枢轴不应该是分区的一部分。这样，一个元素列表就会生成两个空分区，一个在支点之前，一个在枢轴之后。

做两次同样的手术。使用let缓冲拆分结果并使用该变量两次。