期望为线性时间的选择算法RANDOM_SELECT

浏览数：20 / 时间：2015年06月08日

 1 #include<iostream>
 2 #include<ctime>
 3 using namespace std;
 4 void swap(int *a, int *b)
 5 {
 6     int *c = a;
 7     a = b;
 8     b = c;
 9 }
10 int Partition(int *A, int p, int r)// 划分
11 {
12     int x = A[r];
13     int i = p - 1;
14     for (int j = p; j < r; j++)
15     {
16         if (A[j] < x)
17         {
18             i++;
19             swap(A[i],A[j]);
20         }
21     }
22     swap(A[i+1],A[r]);
23     return (i+1);
24 }
25 int Rand(int M, int N)//实现区间为[M,N]的随机数
26 {
27     return (int)((double)rand() / (double)RAND_MAX*(N - M + 1) + M);
28 }
29 int Randmom_Partion(int *A, int p, int r)//划分的随机版本
30 {
31     int x = Rand(p,r);
32     swap(A[r],A[x]);
33     return Partition(A, p, r);
34 }
35 int Random_Select(int *A, int p, int r, int i)//随机选择
36 {
37     if (p == r)
38         return A[p];
39     int q = Randmom_Partion(A,p,r);
40     int k = q - p + 1;
41     if (k == i)
42         return A[q];
43     else if (i < k)
44         return Random_Select(A, p, q - 1, i);
45     else
46         return Random_Select(A, q + 1,r, i - k);//当在右侧时，注意修改下一次i值
47 
48 }
49 int main()
50 {
51     int A[] = {2,4,1,3,5,100,6,6,2,102};
52     int N = sizeof A / sizeof A[0];
53     srand((int)time(0));//必须放在调用前，不可放到产生随机数的函数中
54     cout << Random_Select(A,0,N-1,8)<<endl;
55 
56 }