分治法~线性时间选择要点.doc

《计算机算法设计与分析》实 验 报 告 实验名称：线性时间选择问题 实验地点： 所使用的开发工具及环境： 实验目的： 熟悉掌握分治算法设计技术 二、实验内容： 1、按教材所授内容要求，完成“线性时间选择问题”算法。得到一个完整正确的程序。 2、问题规模：不少于2000 3、输出最终结果。 基本思想、原理和算法描述： 基本思想：将n个输入元素划分成┌ n/5┐个组，每组有5个元素，除最后一组可能不是5个元素之外用任意一种算法，将每组的元素排好序，并取出每组的中位数，共┌ n/5┐个。调用Select找出这┌ n/5┐个元素的中位数，如果┌ n/5┐是偶数就找两个中位数中较大的一个。在这里我用的排序的方法是快速排序。 算法描述： template class Type Type Select(Type a[],int p,int r,int k) { int i; if(r-p75) { Qsort(a,p,r); return a[p+k-1]; } //(r-p-4)/5相当于n-5 for(i=0; i=(r-p-4)/5; i++) { //将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置 //使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数 Qsort(a,p+5*i,p+5*i+4); Swap(a[p+5*i+2],a[p+i]); } //找中位数的中位数 Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10); i = Partition(a,p,r,x); int j = i-p+1; if(k=j) { return Select(a,p,i,k); } else { return Select(a,i+1,r,k-j); } } 源程序清单： #includestdio.h #includestdlib.h #includetime.h #includewindows.h #includeiostream.h template class Type void Swap(Type x,Type y); inline int Random(int x, int y); template class Type void Qsort(Type a[] ,int p,int r); template class Type int Partition(Type a[],int p,int r,Type x); template class Type Type Select(Type a[],int p,int r,int k); void main() { int a[2000]; srand((unsigned)time(NULL)); for(int i=0; i2000; i++) { a[i] = Random(0,2000); couta[i]:a[i] ; } coutendl; cout第800小元素是Select(a,0,1999,800)endl; //重新排序，对比结果 Qsort(a,0,1999); for( i=0; i2000; i++) { couta[i]:a[i] ; } coutendl; } template class Type void Swap(Type x,Type y) { Type temp = x; x = y; y = temp; } inline int Random(int x, int y) { int ran_num = rand() % (y - x) + x; return ran_num; } template class Type void Qsort(Type a[] ,int p,int r) { if(pr) { Type x; int q=Partition(a,p,r,x); Qsort(a,p,q-1); Qsort(a,q+1,r); } } template class Type int Partition(Type a[],int p,int r,Type x) { int i = p; int j = r + 1; x=a[p]; while(true) { while(a[++i]xir); while(a[--j]x); if(i=j) break; Swap(a[i],a[j]); } a[p]=a[j]; a[j]=x; return