算法思想:利用快速排序的方法将a[p:r]被划分成两个子数组a[p:i]和a[i+1:r],使a[p:i]中的每个元素都不大于a[i+1:r]中每个元素。接着算法计算子数组a[p:i]中元素个数j。如果k≤j，则第k小的数落在左区间，否则落在右区间，直到k=j时，找到第k小的数。
对于有重复数字的无法解决。其实维护小顶堆感觉更好，无论时间复杂度还是代码复杂程度。
int Partiotion(int a[], int p, int r) { int i = p; int j = r + 1; int x = a[p];//划分的基准 while (true) { while (a[++i] < x && i < r);//找到第一个比基准大的元素 while (a[--j] > x);//找到比基准大的元素 if (i >= j) { break; } swap(a[i], a[j]);//交换两个位置不正确的元素 } a[p] = a[j]; a[j] = x; return j; } int RandomizedPartition(int a[], int p, int r) {//随机选择基准优化快速排序，区间对称性 int i = rand() % (p - r + 1) + p; swap(a[i], a[p]); return Partiotion(a, p, r); } int RandomizedSelect(int a[], int low, int high, int k) { if (low == high) { return a[low]; } int i = Partiotion(a, low, high); int j = i - low + 1; if (k <= j) { return RandomizedSelect(a, low, i, k); } else { return RandomizedSelect(a, low+1, high, k-j); } }
