快速排序 (Quicksort)

问题

从小到大排序序列 [l, r]

思路

取序列中一值 [p], 称为主元 (pivot element)
将序列分为 [l, p-1], [p+1, r], 且 [l, p-1] 序列中所有的值都小于或等于 [p+1, r]
递归处理这两个子序列

比较复杂的部分是按规则将主序列分成两个子序列，称为 Partition 过程
对于 [l, r-1] 序列，将 [r] 作为主元，i, j 用于标记
i 用于在 [l, r-1] 中划分小于和大于 [r] 的分界， 精确点说就是，[l, i-1] 中的所有值小于等于 [r], [i, r-1] 中的所有值大于等于 [r]
j 用于每次比较
概括一下思想就是：j 从 l 增加到 r-1, 每次将 [j] 与 [r] 比较，如果 [j] 小于 [r], 那么 i++ (小于 [r] 的值又多了一个）, 交换 [j] 和 [i]（使 [l, i-1] 中的所有值都小于等于 [r]）
代码如下：

(define (partition vec l r)
  (let ([pivot-value (vector-ref vec r)])
    (define (iter i j)
      (if (< j r)
          (if (< (vector-ref vec j) pivot-value)
              (begin
                (vector-swap! vec i j)
                (iter (+ i 1) (+ j 1)))
              (iter i (+ j 1)))
          (begin
            (vector-swap! vec i r)
            i)))
    (iter l l)))

C 语言版：

int partition(int arr[], int l, int r)
{
    int i, j;
    int pivot_value = arr[r];

    for (i = l, j = l; j < r; j++) {
        if (arr[j] < pivot_value) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, j);

    return i;
}

代码

(define (quick-sort vec l r)
  (if (< l r)
      (let ([p (partition vec l r)])
        (quick-sort vec l (- p 1))
        (quick-sort vec (+ p 1) r))
      '()))