【求助】算法导论9.3线性时间查找算法
最近在看算法导论；但是写出来的程序，提示出错 并且运行结果也是错的
请大牛指点
代码如下（只能开100分帖子见谅，如果嫌少，我再看贴补上几百分都可以）
#include<iostream>#include<ctime>#include<iterator>using namespace std;int random(int p,int q){ time_t t; srand((unsigned)time(&t)); return rand()%(q-p)+p;}int mid(int L,int R){ return L+(R-L)/2;}void swap(int &a,int&b){ int temp=a; a=b; b=temp;}void randomshuffle(int A[],int L,int R){ for(int i=L;i<R;i++) { int j=random(i,R); swap(A[i],A[j]); }}void insertsort(int A[],int L,int R){ for(int i=L+1;i<=R;i++) { int value=A[i]; int j=i-1; while(j>=L&&A[j]>value) { A[j+1]=A[j]; j--; } A[j+1]=value; }}int partition(int A[],int L,int R,int val){ int i; for(i=L;i<=R;i++) { if(A[i]==val) { break; } } swap(A[i],A[R]); int j=L-1; for(i=L;i<R;i++) { if(A[i]<val) { j++; swap(A[j],A[i]); } } swap(A[j+1],A[R]); return j+1;}int selete(int A[],int L,int R,int i){ if(R-L<5) { insertsort(A,L,R); //cout<<A[L+i-1]<<"***"; return A[L+i]; } int size=(R-L+6)/5,left,right; for(int k=0;k<size;k++) { left=L+k*5; right=(L+k*5+4>R?R:L+k*5+4); insertsort(A,left,right); swap(A[L+k],A[mid(left,right)]); } int x=selete(A,L,L+size-1,(size-1)/2); int M=partition(A,L,R,x); int K=M-L+1; if(K==i)return A[K]; else if(K>i) { return selete(A,L,K-1,i); } else { return selete(A,K+1,R,i-K); }}int main(){ int A[100]; int i; for(i=0;i<100;++i) A[i] = i+1; randomshuffle(A,0,99);//随机排列，打乱顺序 cout<<"Init A:\n"; copy(A,A+99,ostream_iterator<int>(cout," ")); cout<<endl; for(int i=0;i<100;++i) { cout<<i<<" th element: "; cout<<selete(A,0,99,i)<<endl; } cout<<endl;}#include<iostream>#include<ctime>#include<iterator>using namespace std;int random(int p,int q){ time_t t; srand((unsigned)time(&t)); return rand()%(q-p)+p;}int mid(int L,int R){ return L+(R-L)/2;}void swap(int &a,int&b){ int temp=a; a=b; b=temp;}void randomshuffle(int A[],int L,int R){ for(int i=L;i<R;i++) { int j=random(i,R); swap(A[i],A[j]); }}void insertsort(int A[],int L,int R){ for(int i=L+1;i<=R;i++) { int value=A[i]; int j=i-1; while(j>=L&&A[j]>value) { A[j+1]=A[j]; j--; } A[j+1]=value; }}int partition(int A[],int L,int R,int key){ //轴值的首尾标志 int leftIndex = L; int rightIndex = R; //快速排序的一轮 while (leftIndex < rightIndex) { //从右侧开始扫描若右侧数大于轴值则右侧标志位-1 while (leftIndex < rightIndex && A[rightIndex] > key) { rightIndex--; } //若右侧数小于轴值则交换右侧的数和左侧leftindex所指的数 并从左边开始比较 while (leftIndex < rightIndex && A[rightIndex] < key) { swap(A[leftIndex], A[rightIndex]); leftIndex++; } //从左边开始比较若该数小于或等于轴值 则左侧标志位+1 注意一定要注意等于的情况 while (leftIndex < rightIndex && (A[leftIndex] < key || A[leftIndex] == key)) { leftIndex++; } //从左边开始比较若该数比轴值大 则将该数和右侧标志位rightIndex对应的值交换并从右侧开始计算 while (leftIndex < rightIndex && A[leftIndex] > key) { swap(A[leftIndex], A[rightIndex]); rightIndex--; } if (leftIndex >= rightIndex) { break; } } //求key值对应的索引 return leftIndex;}int selete(int A[],int L,int R,int i){ if(R-L<5) { insertsort(A,L,R); //cout<<A[L+i-1]<<"***"; return A[L+i-1]; } int length=R-L+1; int size=length/5,left,right; for(int k=0;k<size;k++) { //计算每一组的起始索引 left=L+k*5; //计算每一组的终止索引 right=left+4; insertsort(A,left,right); swap(A[L+k],A[left+2]); } //求中位数的中位数x int x=selete(A,L,L+size-1,(size+1)/2); //将数组分割成两组 返回该pivot的索引值 int M=partition(A,L,R,x); int K=M-L+1; //在前半部分 递归前部分 if(i<=K) { return selete(A,L,M,i); } else//在后半部分递归 { return selete(A,M+1,R,i-K); }}int main(){ int A[100]; int i; for(i=0;i<100;++i) A[i] = i+1; randomshuffle(A,0,99);//随机排列，打乱顺序 cout<<"Init A:\n"; copy(A,A+100,ostream_iterator<int>(cout," ")); cout<<endl; for(i=0;i<100;++i) { cout<<i<<" th element: "; cout<<selete(A,1,100,i)<<endl; } cout<<endl;}