期望复杂度：0(n)
最坏复杂度：0(n*n)
方法：通过调用快速排序的子程序:random_paration()，根据返回的中枢元素单方向的处理集合中数据。
代码中实现递归和迭代的random_select()。
view plaincopy to clipboardprint?
1 #include <iostream>
2 #include <cstdlib>
3 #include <ctime>
4 using namespace std;
5
6 int random_paration(int *a,int s,int e)
7 {
8 srand(time(NULL));
9 //cout <<"s="<<s<<endl;
10 //cout << "e="<<e<<endl;
11 int r = s+rand()%(e-s+1);//注意：此时的随机数应该是s+rand()%(e-s+1)
12 //cout << "rand = " << r << endl;
13 int tmp = a[r];
14 a[r] = a[e];
15 a[e] = tmp;
16
17 int p = a[e];
18 int l=s,h=e;
19 while(l<h)
20 {
21 while(l<h && a[l]<=p)
22 l++;
23 tmp = a[l];
24 a[l] = a[h];
25 a[h] = tmp;
26
27 while(l<h && a[h]>= p)
28 h--;
29 tmp = a[l];
30 a[l] = a[h];
31 a[h] = tmp;
32 }
33 return l;
34
35
36 }
37 //寻找数组a中第i小的元素
38 //s:数组a的起始位置
39 //e:数组a的结束位置
40 /*递归方法
41 int random_select(int *a,int s,int e,int i)
42 {
43 if(s==e)
44 return a[s];
45 int q = random_paration(a,s,e);//选择中枢元素
46 int k= q-s+1;//a[s,q]的长度
47 if(k==i)//k 正是需要找的元素位置
48 return a[s+k-1];//注意：此时输出元素位置因该是：s+k－1;
49 //return a[q];
50 if(k<i)
51 return random_select(a,q+1,e,i-k);
52 else
53 return random_select(a,s,q-1,i);
54 }
55 */
56 //迭代方法
57 int random_select(int *a,int s,int e,int i)
58 {
59 while(s<=e)
60 {
61 if(s==e)
62 return a[s];
63 if(i> e-s+1)
64 {
65 cout << "error" << endl;
66 return -1;
67 }
68 int q = random_paration(a,s,e);
69 int k = q-s+1;
70 if(k==i)
71 return a[q];
72 if(k<i)
73 {
74 s = q+1;
75 i = i-k;
76 }
77 else
78 {
79 e = q-1;
80 }
81 }
82 }
83 int main()
84 {
85 //int a[10] = {2,4,1,5,4,6,7,4,10,8};
86 //int a[10] = {2,2,2,2,2,2,2,2,2,2};
87 int a[2] = {1,2};
88 int min = random_select(a,0,0,1);
89 cout<<min<<endl;
90 }