线性时间选择问题

其实就是算法书上的一个问题实现，复杂度O(n)。

给定线性序集中n个元素和一个整数k，1<=k<=n，要求找出这n个元素中第k小的元素。
即如果将这n个元素依次线性排序时，排在第k个位置的元素即为要找的元素。
当k-1时，就是要找的最小元素；
当k=n时，就是要找的最大元素；
当k=(n+1)/2，称为中位数。

#include <iostream>
#define LENGTH 16
using namespace std;

void exswap(int& i, int& j)
{
    int n;
    n = i;
    i = j;
    j = n;
}

int Partition(int a[], int p, int r, int x)
{
    //将小于x的元素放到左边
    //反之放到右边
    int i = p - 1;
    for (int j = p; j <= r - 1; j++) {
        if (a[j] <= x) {
            i++;
            exswap(a[i], a[j]);
        }
    }
    exswap(a[i + 1], a[r]);
    return i + 1;
}

void QuickSort(int a[], int p, int r)
{
    if (p < r) {
        int q = Partition(a, p, r, a[r]);
        QuickSort(a, p, q - 1);
        QuickSort(a, q + 1, r);
    }
}

int Select(int a[], int p, int r, int k)
{
    if (r - p < 15) //小于阈值时直接使用快排
    {
        QuickSort(a, p, r);
        return a[p + k - 1];
    }
    for (int i = 0; i <= (r - p - 4) / 5; i++) {
        QuickSort(a, p + 5 * i, p + 5 * i + 4); //范围内数字进行O(1)快排
        exswap(a[p + i], a[p + 5 * i + 2]); //这里是第k小元素与a[p+i]交换位置
    }
    //查找中位数的中位数
    int x = Select(a, p, p + (r - p - 4) / 5, (r - p - 4) / 10);
    int i = Partition(a, p, r, x), j = i - p + 1;
    if (k <= j)
        return Select(a, p, i, k);
    else
        return Select(a, i + 1, r, k - j);
}

int main()
{
    int test[LENGTH] = { 1, 0, 11, 2, 14, 1523, 233, 123, 11, 5, 4, 12, 7, 6, 9, 8 };
    int k, x;
    cout << "Number of k？" << endl;
    cin >> k;
    x = Select(test, 0, LENGTH - 1, k);
    cout << "Is " << x << endl;
    return 0;
}