Sorting a list in scheme

问题:

How do write a sorting algorithm that returns a list into increasing order.

ex: '(1 3 5 2 9) returns '(1 2 3 5 9)

回答1:

Most Scheme implementations come with a procedure to sort lists. If your implementation does not provide one, it is not difficult to roll one on your on. Here is an implementation of the quick-sort algorithm:

> (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)

回答2:

SRFI 95 provides a sorting library. Many Scheme implementation also have sorting libraries built in, though not all of them conform to the SRFI 95 interface.

---

If you need to write your own implementation (for homework, say), then you should use one of the standard sorting algorithms like mergesort or quicksort. However, both of those algorithms are vector-based algorithms, so you will need to copy the list to a vector, sort that, then copy it back to a list. (You may find SRFI 43 useful for vector manipulation operations, especially vector-swap! for swapping two elements of a vector.)

There may be algorithms that are suited for sorting a linked list directly. I'm not au fait with them, so I won't comment on them further.