quickSelect C++

int partition(vector<int> &a,int l, int r){ swap(a[l],a[l+rand()%(r-l+1)]); int j=l,pivot=a[l]; for(int i=l+1;i<=r;i++){ if(a[i]<pivot){ swap(a[i],a[++j]); } } swap(a[l],a[j]); return j; } int quickSelect(vector<int>& arr, int k){ int left=0,right=arr.size()-1; int m=k-1; while(left<=right){ int index=partition(arr,left,right); if(index==m) return arr[m]; else if(index<m) left=index+1; else if(index>m) right=index-1; } return 0; }

库函数快速实现：

void nth_element( RandomIt first, RandomIt nth, RandomIt last ); void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );

nth_element 是部分排序算法，它重排 [first, last) 中元素，使得nth前面元素都小于等于nth元素，nth后面元素都大于等于nth元素。 时间复杂度O(n)。 源代码使用内省选择 （Introselect） 内省选择算法首先调用快速选择算法，但如果其运算次数超过O(n)时，默认使用BFPRT算法，确保最坏运行时间为Theta(n)。

int nthOfArr(vector<int> &arr, int k){ nth_element(arr.begin(), arr.begin() + k - 1, arr.end()); return arr[k - 1]; }