记录一下 算法分析实验七
利用Sherwood型随机化思路求解线性时间选择算法，并计算出程序运行所需要的时间。
① 参考课件、教材、其它资料，将伪代码改成正式程序代码。
② 用一组小数据，手工验证程序正确性，发现可能的错误并修复。
③ 自己设计代码，生成小、中、大规模数据，分别存到三个.txt文件。
④ 对三种规模的数据，检测程序运行时间，观察并记录结果和发现。
先贴一下用来生成随机数文本的代码：
/* #include <iostream> #include <fstream> #include <stdlib.h> using namespace std; int main() { fstream fso("50000.txt", ios::out); int i; for(i = 0; i < 50000; ++i) fso << rand() << ' '; fso.close(); fstream fsi("50000.txt", ios::in); int x[50000]; for(i = 0; i < 50000; ++i) fsi >> x[i]; for(i = 0; i < 50000; ++i) cout << x[i] << '\t'; return 0; } */ //万级以下用这个缩小范围(四舍五入生成整数) #include<iostream> #include<stdlib.h> #include <fstream> #include<time.h> #include<iomanip> #include<stdio.h> #include<math.h> using namespace std; double round(double r) { return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5); } double randomRange(double a, double b) { double x = (double)rand() / RAND_MAX; double result = x*(b - a) + a; return round(result); } int main() { srand((int)time(0)); fstream fso("10.txt", ios::out); int i; for(i = 0; i <10; ++i) fso <<randomRange(0, 100)<< ' '; // fso.close(); fstream fsi("10.txt", ios::in); int x[10]; for(i = 0; i <10; i++) fsi >> x[i]; for ( i = 0; i <10; i++) { cout << randomRange(0, 100) << " "; } cout << endl; system("pause"); }主体代码：
#include<time.h> #include<stdio.h> #include<math.h> #include <iomanip> #include <iostream> #include <fstream> #include <stdlib.h> using namespace std; template<class Type> Type select(Type a[],int l,int r,int k); template<class Type> //是否越界 Type select(Type a[],int n,int k); template<class Type> void Shuffle(Type a[],int n); template <class Type> inline void Swap(Type &a,Type &b); int main() { int n,k,i; cout<<"输入三种数据选择元素规模：1.10；2.500；3.50000"<<endl; cin>>n; int *a=new int[n+1]; cout<<"求第k小个元素，请输入k："<<endl; cin>>k; if(n==10) { fstream fsi("10.txt", ios::in); for(i = 0; i < 10; ++i) fsi >> a[i]; for(i = 0; i <10; ++i) cout << a[i] << '\t'; } else if(n==500) { fstream fsi("500.txt", ios::in); for(i = 0; i < 500; ++i) fsi >> a[i]; for(i = 0; i <500; ++i) cout << a[i] << '\t'; } else if(n==50000) { fstream fsi("50000.txt", ios::in); for(i = 0; i < 50000; ++i) fsi >> a[i]; for(i = 0; i <50000; ++i) cout << a[i] << '\t'; } cout<<endl; Shuffle(a,n); cout<<"数组洗牌后："<<endl; for(i=0;i<n;i++) cout<<a[i]<< '\t'; cout<<endl; clock_t start,end,over; start=clock(); end=clock(); over=end-start; start=clock(); cout<<"数组第k小元素为："<<select(a,n,k)<<endl; end=clock(); printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); cout<<endl; system("pause"); return 0; } //计算a[0:n-1]中第k小元素 //假设a[n]是一个键值无穷大的元素 template<class Type> Type select(Type a[],int n,int k) { if(k<1 || k>n) { cout<<"请输入正确的k!"<<endl; return 0; } return select(a,0,n-1,k); //合法 } //计算a[l:r]中第k小元素 template<class Type> Type select(Type a[],int l,int r,int k) { while(true) { if(l>=r) //数组仅1元素 { return a[l]; } int i = l; int j = r+1; Type pivot = a[l]; //轴值=最左边元素 //以划分基准为轴做元素交换 //小于轴值的换到左边，大于轴值的换到右边 while(true) { while(a[++i]<pivot); while(a[--j]>pivot); if(i>=j) { break; } Swap(a[i],a[j]); } if(j-l+1 == k)//第k小找到，是轴值 { return pivot; } //如果没找到（轴值不是第k小） //a[j]必然小于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大 a[l] = a[j]; a[j] = pivot; //对子数组重复划分过程 if(j-l+1<k) //第k小在轴值右边 { k = k-j+l-1;//右侧：k-(j-l+1)=k-j+l-1 l = j + 1; } else //第k小在轴值左边 { r = j - 1; } } } template <class Type> inline void Swap(Type &a,Type &b) { Type temp = a; a = b; b = temp; } /* //随机洗牌算法 template<class Type> void Shuffle(Type a[],int n) { static Randomnumber rnd; //随机数类 for(int i=0; i<n; i++) { int j = rnd.Random(n-i)+i; //随机生成i~n之间的整数 Swap(a[i],a[j]); //随机选取的数作为基准值 } } */ //随机洗牌算法 template<class Type> void Shuffle(Type a[],int n) { srand((int)time(0)); double x,r; for(int i=0; i<n; i++) { x = (double)rand() / RAND_MAX; r = x*(n - i) + i; (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5); int j = (int)r; //随机生成i~n之间的整数 Swap(a[i],a[j]); //随机选取的数作为基准值 } } 不想用随机数类所以直接生成i~n随机数，运行起来似乎没有问题的样子。