快速排序

Quicksort 是一種常見的排序演算法，平均案例複雜度為 O(n log n)，最壞情況下複雜度為 O(n^2)。它優於其他 O(n log n) 方法的優勢在於它可以就地執行。

Quicksort 將輸入拆分為選定的透視值，將列表分成小於的值和大於（或等於）透視的值。使用 filter 可以輕鬆完成拆分列表。

使用它，Quicksort 的 Scheme 實現可能如下所示：

(define (quicksort lst)
  (cond
    ((or (null? lst) ; empty list is sorted
         (null? (cdr lst))) ; single-element list is sorted
     lst)
    (else
      (let ((pivot (car lst)) ; Select the first element as the pivot
            (rest (cdr lst)))
        (append
          (quicksort ; Recursively sort the list of smaller values
            (filter (lambda (x) (< x pivot)) rest)) ; Select the smaller values
          (list pivot) ; Add the pivot in the middle
          (quicksort ; Recursively sort the list of larger values
            (filter (lambda (x) (>= x pivot)) rest))))))) ; Select the larger and equal values