求第k大数
int Partion(int a[], int s, int e)
{
　 if (s + 1 >= e) return s;
　int i = s;
　int j = e-1;
　int key = a[s];
　 while (i < j)
　 {
　　 while (i < j&&a[j] >= key) --j;
　　a[i] = a[j];
　　while (i < j&&a[i] <= key) ++i;
　　 a[j] = a[i];
　 }
　a[i] = key; return i;
}
int Select(int a[], int s,int e,int k)
{
　 int i = Partion(a, s, e);
　 if (i + 1 == k) return a[i];
　if (i + 1 > k) return Select(a, s, i, k);
　 else return Select(a, i + 1, e, k);
}

可以看出这和快排的代码很像，只是每划分一次都减少了一部分元素的排序。因为这是没有必要的，如果知道某数排名m之后，那排名前m的元素谁排第几和此数的排名没有关系。这种不断缩减元素范围的设计思想叫减治。
算法的时间复杂度为O(n)。如果要求排名前k的数，可以先求出第k大数，再遍历元素，找出比第k大数小的元素，算法时间复杂度依旧是线性的。
但此算法有两点不足。一，不适合密集查询，当查询次数多了，不如先排个序，平摊的时间复杂度还小些。二，用来找排名前k的数，必须先知道所有的数，也就是说算法是离线的。与此相关的在线算法，可以建k个元素的大顶堆，来一个元素，若其比堆顶元素小，则取代堆顶元素。

top k算法
void Down(int a[], int n, int pos)
{
　 if (pos >= n) return;
　 int l = 2 * pos + 1;
　 int r = 2 * pos + 2;
　int max = pos;
　 if (l<n&&a[l]>a[max]) max = l;
　 if (r<n&&a[r]>a[max]) max = r;
　if (max != pos)
　{
　　Swap(a + max, a + pos);
　　Down(a, n, max);
　}
}
void BuildHeap(int a[], int n)
{
　for (int i = n / 2; i >= 0; --i) Down(a, n, i);
}
void TopK(int a[], int n, int k)
{
　 if (k >= n) return;
　BuildHeap(a, k)
　 for (int i = k; i < n; ++i)
　 {
　　 if (a[i] < a[0])
　　 {
　　　Swap(a + i, a);
　　　 Down(a, k, 0);
　　}
　}
}

划分树待补。