快速排序
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