快排求第k大

2019-11-11 06:59:53

字体：大中小

来源：转载

供稿：网友

/*设某次排序后，分界点x右边有p个元素，（此时x左边元素皆小于等于x,右边元素皆大于等于x）若p == k-1，则 x 为恰第 k 大；若p < k-1，则在区间[left, i) 之间求第 k-p-1 大若p > k-1，则在区间[i+1, right) 之间求第k大*/#include <cstdio>int qsort(int* A, int left, int right, int k){//在左闭右开区间[left, right)求第k大 int i = left, j = right - 1; int tmp = A[left]; while(i < j){ while(A[j] >= tmp && i < j) j--;//从右往左第一个比tmp小的数 if(i < j) A[i++] = A[j]; while(A[i] <= tmp && i < j) i++;//从左往右第一个比tmp大的数 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大 PRintf("%d/n", ans); } return 0;}

上一篇：1058. 选择题(20)

下一篇：Thrift框架介绍