【求助】算法导论9.3线性时间查找算法

haofang666777

抱歉只有6分，请见谅
就是算法导论中关于线性时间内查找元素的算法

代码如下，昨天一直盖到现在，是在不会了 ，拜托了

1. #include<iostream>
   
2. #include<ctime>
   
3. #include<iterator>
   
4. using namespace std;
   
5. int random(int p,int q)
   
6. {
   
7.         time_t t;
   
8.         srand((unsigned)time(&t));
   
9.         return rand()%(q-p)+p;
   
10. }
    
11. int mid(int L,int R)
    
12. {
    
13.         return L+(R-L)/2;
    
14. }
    
15. void swap(int &a,int&b)
    
16. {
    
17.         int temp=a;
    
18.         a=b;
    
19.         b=temp;
    
20. }
    
21. void randomshuffle(int A[],int L,int R)
    
22. {
    
23.         for(int i=L;i<R;i++)
    
24.         {
    
25.                 int j=random(i,R);
    
26.                 swap(A[i],A[j]);
    
27.         }
    
28. }
    
29. void insertsort(int A[],int L,int R)
    
30. {
    
31.         for(int i=L+1;i<=R;i++)
    
32.         {
    
33.                 int value=A[i];
    
34.                 int j=i-1;
    
35.                 while(j>=L&&A[j]>value)
    
36.                 {
    
37.                         A[j+1]=A[j];
    
38.                         j--;
    
39.                 }
    
40.                 A[j+1]=value;
    
41.         }
    
42. }
    
43. int partition(int A[],int L,int R,int val)
    
44. {
    
45.         int i;
    
46.         for(i=L;i<=R;i++)
    
47.         {
    
48.                 if(A[i]==val)
    
49.                 {
    
50.                         break;
    
51.                 }
    
52.         }
    
53.         swap(A[i],A[R]);
    
54.         int j=L-1;
    
55.         for(i=L;i<R;i++)
    
56.         {
    
57.                 if(A[i]<val)
    
58.                 {
    
59.                         j++;
    
60.                         swap(A[j],A[i]);
    
61.                 }
    
62.         }
    
63.         swap(A[j+1],A[R]);
    
64.         return j+1;
    
65. }
    
66. int selete(int A[],int L,int R,int i)
    
67. {
    
68.         if(R-L<5)
    
69.         {
    
70.                 insertsort(A,L,R);
    
71.                 //cout<<A[L+i-1]<<"***";
    
72.                 return A[L+i];
    
73.         }
    
74.         int size=(R-L+6)/5,left,right;
    
75.         for(int k=0;k<size;k++)
    
76.         {
    
77.                 left=L+k*5;
    
78.                 right=(L+k*5+4>R?R:L+k*5+4);
    
79.                 insertsort(A,left,right);
    
80.                 swap(A[L+k],A[mid(left,right)]);
    
81.         }
    
82.         int x=selete(A,L,L+size-1,(size-1)/2);
    
83.         int M=partition(A,L,R,x);
    
84.         int K=M-L+1;
    
85.         if(K==i)return A[K];
    
86.         else if(K>i)
    
87.         {
    
88.                 return selete(A,L,K-1,i);
    
89.         }
    
90.         else
    
91.         {
    
92.                 return selete(A,K+1,R,i-K);
    
93.         }
    
94. }
    
95. int main()
    
96. {
    
97.         int A[100];
    
98.         int i;
    
99.         for(i=0;i<100;++i) A[i] = i+1;
    
100.         randomshuffle(A,0,99);//随机排列，打乱顺序
     
101. 
     
102.         cout<<"Init A:\n";
     
103.         copy(A,A+99,ostream_iterator<int>(cout," "));
     
104.         cout<<endl;
     
105. 
     
106.         for(int i=0;i<100;++i)
     
107.         {
     
108.                 cout<<i<<" th element: ";
     
109.                 cout<<selete(A,0,99,i)<<endl;
     
110.         }
     
111.         cout<<endl;
     
112. }

复制代码

walleeee

什么问题？

haofang666777

walleeee 发表于 2012-02-21 18:28
什么问题？

代码有错误，运行结果不对，程序最后也崩溃，改了两天了，实在不会改了，谢谢了

walleeee

我运行最后没有崩溃啊。。正常结束

haofang666777

walleeee 发表于 2012-02-21 22:00
我运行最后没有崩溃啊。。正常结束

但是运行结果不对啊
正确的运行结果是
第1个元素 1
  2            2
3        3
4            4
5          5
。。。。。。
15         15
  。。。。。。。。。。。


25              25
。。。。。。。。。。
第44个元素   44

walleeee

只看算法，我的理解是按5个元素分组，最多只有1组不足5个。如果只有1组，有如下情况：
1个元素   中位数是1，查找只能是1，所以查找的就是中位数
2个元素   中位数是2（这里有一个约定，中位数计算取偶数），查找只能是1和2，所以很容易根据中位数分辨出查找的是第几个（5个分组是有序的，预排序，至于用什么排序算法，随意，我看你用的是冒泡，不过至于你写的对不对我不知道）
3个元素   以此内推
4个元素   ...
5个元素   ...

上面的是递归的核心，所以递归只需要每次检查是不是还剩5个（满足上面的核心），不满足就选出所有组的中位数（中卫数有个性质就是小于他的有2个在左边，大于他的有2个在右边，他在中间），形成一个新组，然后作为参数递归。

比如举一个例子有如下数列：
4 2 8 9 1 3
查找第3大，f(0, 5, 3)

分组1  4 2 8 9 1      1 2 4 8 9
分组2  3                  3
当前不满足5边界（当前被查找集合大于5个元素）
重组中位数
4 3
再选中位数
3

ps.
主要用了中位数是中间一个元素的这个性质。

walleeee

step1：将n个元素每5个一组，分成n/5(上界)组。
step2：取出每一组的中位数，任意排序方法，比如插入排序。
step3：递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
step4：用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
step5：若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。

这样描述应该没问题了

walleeee

总之，一句话，中位数的性质

walleeee

还有，我看你的程序似乎编得不好啊

haofang666777

我看你用的是冒泡
PS:我就是按程序要求用的插入排序


PPS：那个程序编的不好请指教。
谢谢