求第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);
}
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);
}