#include <iostream>#include <vector>using namespace std;#define EXCHANGE(a,b) \ ({typeof(a) _tmp; \ _tmp=a; \ a=b; \ b=_tmp;})template <typename T>int Partition(vector<T>& arr,int p,int r){ int x=arr[r]; int i=p-1; int j=0; for(j=p;j<=r-1;j++){ if(arr[j]<=x){ i=i+1; EXCHANGE(arr[i],arr[j]); } } EXCHANGE(arr[i+1],arr[r]); return i+1;}template <typename T>void FIND_K(vector<T>& arr,int first,int last,int K){ int index; index = Partition(arr,first,last-1); if(index == K) return; else if(K < index) FIND_K(arr,first,index,K); else FIND_K(arr,index+1,last,K); return;}int main(){ int arr[] = {250,300,350,400,400,\ 450,500,500,550,650,\ 655,700,725,735,750}; int K; int N = sizeof(arr)/sizeof(int); vector<int> Arry(arr,arr+N); K = N/2; FIND_K(Arry,0,N,K); cout<<Arry[K]<<endl; return 0;}
从一组未排序的数组里找到第K大元素 用快速排序的思想 可以减少一半的排序量
