利用快速排序思想，每次把一个数找到他应该在的位置，然后如果当前位置满足条件，直接返回，如果这个数（包括这个数）
前面的数的个数小于k，那么第k大在后面的区间，否则在前面的区间，同时还要修改参数。
复杂度O（n）
#include <stdio.h>int quick_select(int a[], int l, int r, int k)
{int p = rand() % (r - l + 1) + l;int x = a[p];{int t = a[p];a[p] = a[r];a[r] = t;}int i = l, j = r;while (i < j){while (i < j && a[i] < x)i++;if (i < j){a[j] = a[i];j--;}while (i < j && a[j] > x)j--;if (i < j){a[i] = a[j];i++;}}a[i] = x;p = i;if (i - l + 1 == k)return a[i];if (i - l + 1 < k)return quick_select(a, i + 1, r, k - (i - l + 1)); //???elsereturn quick_select(a, l, i - 1, k);
}int main()
{int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};printf("%d\n", quick_select(a, 0, 14, 5));return 0;
}