Quickselect（快速选择）

Quickselect 的思想与 quicksort 基本一致。每次 partition() 结束后可得知 pivot 的位置，自然也就知道 pivot 前后各有多少小于、大于 pivot 的元素。选择时，第 k 大的元素必然只存在于 pivot 的左边或者右边。如果 pivot 前的元素数量多于 k，则说明左边有多于 k 个元素小于 pivot，所以第 k 大的元素必然在左边，可在左边选择第 k 大元素；如果 pivot 前的元素数量少于 k，则说明左边只有不到 k 个小于 pivot 的元素，那么第 k 大的元素必然在右边，可在右边选择第 (k – (pivot 左边元素数量)) 大的元素。如此递归进行，如果 pivot 刚好是第 k 个元素，那选择过程就结束了。

Quickselect 与 quicksort 类似，拥有平摊后可观的时间复杂度，但极差的最坏情况下的复杂度。Quickselect 的平摊复杂度是 Ɵ(n)，而最坏情况下复杂度是 Ɵ(n²)，n = 元素数量。最坏情况的高阶可通过随机化算法避免，此同 quicksort。另外，由于 quickselect 递归时每一步都只需深入 pivot 左或右其中一边，其算法可以轻易地被优化为循环形式的尾调用。

一个非随机化的 C 实现如下：

int
partition(int arr[], int i, int j)
{
    int pivot = arr[i];

    for(;;) {
        for (;;) {
            if (i >= j) {
                goto done;
            } else if (arr[j] < pivot) {
                arr[i++] = arr[j];
                break;
            }
            --j;
        }
        for (;;) {
            if (i >= j) {
                goto done;
            } else if (arr[i] > pivot) {
                arr[j--] = arr[i];
                break;
            }
            ++i;
        }
    }
done:
    arr[i] = pivot;

    return i;
}

int
qselect(int arr[], int i, int j, int k)
{
    for (;;) {
        int pivot = partition(arr, i, j);
        int pivot_pos = pivot - i + 1;
        if (pivot_pos == k)
            return arr[pivot];
        if (pivot_pos > k) {
            j = pivot - 1;
        } else {
            i = pivot + 1;
            k -= pivot_pos;
        }
    }
}

测试：

    int arr[] = {3, 2, -32, 1442, 203, 37, 874, 2, 193, 34};
    int right_bound = sizeof (arr) / sizeof (int) - 1;

    printf("%d\n", qselect(arr, 0, right_bound, 1)); // => -32
    printf("%d\n", qselect(arr, 0, right_bound, 2)); // => 2
    printf("%d\n", qselect(arr, 0, right_bound, 5)); // => 34
    printf("%d\n", qselect(arr, 0, right_bound, 4)); // => 3

目前这个实现中的 partition() 是原地破坏性算法。如果需要 qselect() 具有不变性（非破坏性），那可以操纵输入数组的复件。