#include<iostream> #include<ctime> using namespace std; int Partition(int *A, int p, int r)// 划分 { int x = A[r]; int i = p - 1; for (int j = p; j < r; j++) { if (A[j] < x) { i++; swap(A[i],A[j]); } } swap(A[i+1],A[r]); return (i+1); } int Rand(int M, int N)//实现区间为[M,N]的随机数 { return (int)((double)rand() / (double)RAND_MAX*(N - M + 1) + M); } int Randmom_Partion(int *A, int p, int r)//划分的随机版本 { int x = Rand(p,r); swap(A[r],A[x]); return Partition(A, p, r); } int RANDOMIZED_SELECT(int A[], int p, int r, int i)//基于循环版的randomized_select { while (1) { if (p == r) { return A[p]; } int q = Randmom_Partion(A, p, r); int k = q - p + 1; if (i == k) { return A[q]; } else if (i<k) { r = q - 1;//这行代码可以处理有重复的待查找数。 //q--;//网上给的答案是用这行,这行代码不能处理重复元素,例如int A[n]={63,34,92,34,44,16,2,39};需要找的第3小数刚好有重复数。 } else { p = q + 1; i = i - k; } } } int Random_Select(int *A, int p, int r, int i)//随机选择 { if (p == r) return A[p]; int q = Randmom_Partion(A,p,r); int k = q - p + 1; if (k == i) return A[q]; else if (i < k) return Random_Select(A, p, q - 1, i); else return Random_Select(A, q + 1,r, i - k);//当在右侧时,注意修改下一次i值 } int main() { int A[] = { 63, 34, 92, 34, 44, 16, 2, 39}; int N = sizeof A / sizeof A[0]; srand((int)time(0));//必须放在调用前,不可放到产生随机数的函数中 cout << RANDOMIZED_SELECT(A, 0, N - 1, 5) << endl; }