scheme - 在方案中对列表进行排序

Question

如何编写一个排序算法，以递增顺序返回一个列表。

例如:'(1 3 5 2 9)返回 '(1 2 3 5 9)

Answer 1

大多数 Scheme 实现都带有一个对列表进行排序的过程。如果您的实现没有提供一个，那么在您身上滚动一个并不困难。下面是快速排序算法的实现:

> (define (qsort e)
  (if (or (null? e) (<= (length e) 1)) e
      (let loop ((left null) (right null)
                   (pivot (car e)) (rest (cdr e)))
            (if (null? rest)
                (append (append (qsort left) (list pivot)) (qsort right))
               (if (<= (car rest) pivot)
                    (loop (append left (list (car rest))) right pivot (cdr rest))
                    (loop left (append right (list (car rest))) pivot (cdr rest)))))))
> (qsort  '(1 3 5 2 9))
=> (1 2 3 5 9)