scheme 快速排序

示例

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

           

以上是 scheme 快速排序 的全部内容, 来源链接: utcz.com/z/330663.html

回到顶部