我可以使用Scheme有效地实现快速排序吗？

Question

这就是我所做的:

(define qsort
  (lambda (l)
    (let ((lesser '()))
      (let ((greater '()))
        (cond
          ((null? l) '())
          (else (map (lambda (ele)
                       (if (> (car l) ele)
                           (set! lesser (cons ele lesser))
                           (set! greater (cons ele greater)))) (cdr l))
                (append (qsort lesser) (cons (car l) (qsort greater))))
        )))))

我注意到,当提供已经排序的列表时,它变得极其缓慢.经过一番搜索后,我发现如果以随机方式选择"枢轴",可以提高性能.然而,我知道实现这一目标的唯一方法是list-ref,它似乎是O(n).更糟糕的是,我必须实现一个类似cdr的函数来删除列表中的第n个元素,这可能也是非常低效的.

也许我的方向错了.你能给我一些建议吗？

Answer 1

true quicksort在随机访问数组上运行,具有就地分区.例如看到这个.

你可以先将你的列表转换为vector list->vector,然后用C方式通过变换交换分割矢量来实现快速排序.

随机化它很简单:只需随机选择一个位置,并在每个分区步骤之前将其内容与要排序的范围中的第一个元素交换.当你完成后,将其转换回来vector->list.

快速排序的有效实现可以在没有递归的情况下运行,在循环中,保持一堆较大的部分边界,总是在较小的部分上下降(然后,当在底部时,切换到堆栈中的第一部分).三向分区总是更可取的,一次性处理等于.

基于列表的算法实际上是一个解开的树.

也可以看看:

• http://www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell
• 伪快速排序时间复杂度