方法一：quicksort
根据快排思想，从后往前找比基准数小的，交换位置。
从前往后找比基准数大的，交换位置。
最后安放基准数。
保证 l到p 是大数，若 p-l+1==k 那么p就是第K大
若 p-l+1<k 那么从 p+1 到 r 中 找 k-（p-l+1）大的数
若 p-l+1>k 那么从 l 到 p-1中 找第k大的数。
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 int n, k; 9 int a[100010]; 10 int par(int l, int r) 11 { 12 int t = a[l]; 13 while (l < r) 14 { 15 while (l < r &&a[r] <= t) r--; 16 a[l] = a[r]; 17 while (l < r &&a[l] >= t) l++; 18 a[r] = a[l]; 19 } 20 a[l] = t; 21 return l; 22 } 23 int search(int l, int r,int k) 24 { 25 if (l <= r) 26 { 27 int p = par(l, r); 28 if (p - l + 1 == k) return p; 29 else if (p - l + 1 < k) return search(p+1,r,k-(p-l+1)); 30 else return search(l,p-1,k); 31 } 32 } 33 int main() 34 { 35 cin >> n >> k; 36 for (int i = 1; i <= n; i++) 37 cin >> a[i]; 38 cout << a[search(1, n, k)] << endl; 39 40 return 0; 41 }
方法二：最小堆
原本用swap函数的，后来好像swap并不能使两个数交换，以后我一定自己写。（鞠躬表示歉意）
搞了半天搞错了，还是挖坑吧。