本文共 1841 字，大约阅读时间需要 6 分钟。
#include #include #include #include #include #include #include #include #include using namespace std;inline int my_rand(int low, int high) { srand((unsigned)time(NULL)); int size = high - low + 1; return low + rand() % size; } int partition(int array[], int left, int right) { int pivot = array[right]; int pos = left-1; for(int index = left; index < right; index++) { if(array[index] <= pivot) swap(array[++pos], array[index]); } swap(array[++pos], array[right]); return pos;//返回pivot所在位置 } //最坏情况下是线性时间O（N）bool median_select(int array[], int left, int right, int k) { //第k小元素，实际上应该在数组中下标为k-1 if (k-1 > right || k-1 < left) return false; //真正的三数中值作为枢纽元方法，关键代码就是下述六行 int midIndex=(left+right)/2; if(array[left] k-1) return median_select(array, left, pos-1, k); else return median_select(array, pos+1, right, k); } //总的时间复杂度为线性期望时间：O（n+k）=O（n）（当k比较小时）bool rand_select(int array[], int left, int right, int k) { //第k小元素，实际上应该在数组中下标为k-1 if (k-1 > right || k-1 < left) return false; //随机从数组中选取枢纽元元素 int Index = my_rand(left, right); swap(array[Index], array[right]); int pos = partition(array, left, right); if (pos == k-1) return true; else if (pos > k-1) return rand_select(array, left, pos-1, k); else return rand_select(array, pos+1, right, k); } //平均为O(N)bool kth_select(int array[], int left, int right, int k) { //直接取最原始的划分操作 if (k-1 > right || k-1 < left) return false; int pos = partition(array, left, right); if(pos == k-1) return true; else if(pos > k-1) return kth_select(array, left, pos-1, k); else return kth_select(array, pos+1, right, k); } int main() { int array1[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33}; int array2[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33}; int array3[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33}; int numOfArray = sizeof(array1) / sizeof(int); for(int i=0; i
转载地址：http://ybvvi.baihongyu.com/