/*設(shè)某次排序后，分界點x右邊有p個元素，（此時x左邊元素皆小于等于x,右邊元素皆大于等于x）若p == k-1，則 x 為恰第 k 大；若p < k-1，則在區(qū)間[left, i) 之間求第 k-p-1 大若p > k-1，則在區(qū)間[i+1, right) 之間求第k大*/#include <cstdio>int qsort(int* A, int left, int right, int k){//在左閉右開區(qū)間[left, right)求第k大 int i = left, j = right - 1; int tmp = A[left]; while(i < j){ while(A[j] >= tmp && i < j) j--;//從右往左第一個比tmp小的數(shù) if(i < j) A[i++] = A[j]; while(A[i] <= tmp && i < j) i++;//從左往右第一個比tmp大的數(shù) if(i < j) A[i] = A[j--]; } A[i] = tmp; int p = right - i - 1;//A[i]右邊有p個元素 if(p == k-1) return tmp; if(p < k-1) return qsort(A, left, i - 1, k - p - 1); if(p > k-1) return qsort(A, i + 1, right, k);}int main(){ int n, k; while(scanf("%d%d", &n, &k)==2){ int* A = new int[n+1]; for(int i = 0; i < n; i++) scanf("%d", &A[i]); //int A[10] = {13,16,2,1,-1,6,54,123,32,-90}; int ans = qsort(A, 0, n, k);//求第k大
