用快速排序法寻找第k大元素

#include<iostream>#include<algorithm>#include<iterator>#include<cstdio>using namespace std;// 求首元素、中间元素和尾元素的中位数，将中位数与首元素交换位置inline void medianAsPivot(int arr[], const int& left, const int& right){const int middle = left+(right-left)>>1;const int l = arr[left];const int m = arr[middle];const int r = arr[right];if(l<=m&&m<=r || r<=m&&m<=l) swap(arr[left], arr[middle]);if(l<=r&&r<=m || m<=r&&r<=l) swap(arr[left], arr[right]); }// 求分区位置i，该位置左边的所有元素小于该元素，，右边的所有元素不小于该元素// 同时，求得的这个位置的元素值为第i+1大元素int partition(int arr[], const int& left, const int& right){if(left < right){medianAsPivot(arr, left, right);int i = left;int j = right;int key = arr[i]; // 首元素作为pivotwhile(i < j){while(i<j && arr[j]>=key) j–;if(i < j) arr[i++] = arr[j];while(i<j && arr[i]<key) i++;if(i < j) arr[j–] = arr[i];}arr[i] = key;return i;}return left;}// 利用快速排序寻找第k大元素int findKth(int arr[], int n, int k){int position = -1;int i = 0;int j = n-1;while(true){position = partition(arr, i, j);if(position < n-k){i = position+1;j = n-1;}else if(position > n-k){i = 0;j = position-1;}else return arr[position];}}int main(){int arr[] = {7, 8, 9, 1, 2, 3, 6, 5, 4};int size = sizeof(arr)/sizeof(int);int k = 8;int kNum = findKth(arr, size, k);copy(arr, arr+size, ostream_iterator<int>(cout, " "));printf("\n");printf("The %dth number is %d.\n", k, kNum);return 0;}

你的脸是为了呈现上帝赐给人类最贵重的礼物–微笑，一定要成为你工作最大的资产。