如何从一个无序数组中找到第 K K K大的数?
方案一：对数组排序，然后取出第 K K K大的数。需要 O ( n l o g n ) O(nlogn) O(nlogn)的时间复杂度。
方案二：随机选择算法，对任何输入都可以达到 O ( n ) O(n) O(n)的时间复杂度。
原理类似于随机快速排序

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int randPartion(int *arr, int left, int right)
{
    int p = 1.0*rand()/RAND_MAX*(right-left)+left;
    swap(&arr[p], &arr[left]);

    int temp = arr[left];
    while(left < right)
    {
        while(left<right && arr[right]>temp)
        {
            right--;
        }
        arr[left] = arr[right];
        while(left<right && arr[left]<=temp)
        {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = temp;
    return left;

}

//随机选择算法,递归实现
int randSelect(int *arr, int left, int right, int K)
{
    if(left == right)//递归边界
    {
        return arr[left];
    }
    int p = randPartion(arr, left, right);
    int M = p - left +1;//arr[p]是[left,right]中第M大

    if(K == M)
    {
        return arr[p];
    }
    if(K < M)
    {
        return randSelect(arr,left, p-1, K);//左侧找第K大
    }
    else
    {
        return randSelect(arr, p+1, right, K-M);//右侧找K-M大
    }
}