Int arr[]，int p，int r，int i Y P==r Return arr[p] 获取划分后随机基数的位置 int q = RANDOMIZED_PARTITION(arr,p,r);
int k = q-p+1;
Y 获取基数距第一个数的长度
i==k N Y i Return arr[q] 如果基数在中间则返回基数的值 Return RANDOMIZED_SELECT(arr,p,q-1,i); 如果基数在中间数的左边则重复进行以上操作 程序代码如下： int main() { //display available options int alignment; //输油管道方向的选择 label: cout<<\ <<\ <<\ <<\ cin>>alignment; if(alignment != 1 && alignment != 2) { cout<<\ goto label; } int number; //油井个数的选择 cout<<\ cin>>number; cout<<\ int array[number][2]; for(int i=0;i cout<<\ cin>>array[i][0]; cout<<\ cin>>array[i][1]; OilBearing(array[i][0],array[i][1]); } if(alignment==2) //当选择修建的是一个东西走向的输油管道 { int arrayew[number]; int j=0; for(j=0;j arrayew[j]=array[j][1]; } if(number%2==0) //当油井的个数为偶数的时候 { int num1=RANDOMIZED_SELECT(arrayew,0,number-1,number/2); int num2=RANDOMIZED_SELECT(arrayew,0,number-1,number/2+1); printf(\ printf(\ }else if(number%2==1) { printf(\ printf(\ } }else if(alignment==1) //当选择修建的是一个南北走向的输油管道 { int arrayns[number]; int k=0; oil tubing's position is total X=%f\\n\ is : %f\\n\ for(k=0;k arrayns[k]=array[k][0]; } if(number%2==0) //当油井的个数为偶数的时候 { int num1=RANDOMIZED_SELECT(arrayns,0,number-1,number/2); int num2=RANDOMIZED_SELECT(arrayns,0,number-1,number/2+1); printf(\ printf(\ }else if(number%2==1) { printf(\ printf(\ } } return 0; } oil tubing's position is total Y=%f\\n\ is : %f\\n\ PARTITION（划分）函数的作用：将一串数据由大到小进行排序，最后返回划分时所用基数的位置。 int PARTITION(int arr[LEN],int p,int r) { int x = arr[r]; int i = p-1; for(int j = p;j if(arr[j]<=x) { ++i; int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } int t = arr[i+1]; arr[i+1] = arr[r]; arr[r] = t; return i+1; } RANDOMIZED_PARTITION（随机划分优化算法）函数的作用：在所有坐标中随机选择一个，并以此作为基数进行划分，最后返回该基数的位置。 int RANDOMIZED_PARTITION(int arr[LEN],int p,int r) { int i = RANDOM(p,r); int t = arr[i]; arr[i] = arr[r]; arr[r] = t; return PARTITION(arr,p,r); } RANDOMIZED_SELECT（随机选择）函数的作用：找到排序后数据的中位数。 int RANDOMIZED_SELECT(int arr[LEN],int p,int r,int i) //找到arr中第i小的数，数组下标从1开始 { if(p==r) return arr[p]; int q = RANDOMIZED_PARTITION(arr,p,r); int k = q-p+1; if(i==k) return arr[q]; else if(i return RANDOMIZED_SELECT(arr,p,q-1,i); else return RANDOMIZED_SELECT(arr,q+1,r,i-k); } SUM函数的作用：根据以上求解的到的中位数，求出所有数据与该中位数差的绝对值之和。 float SUM(int arr[LEN],float k,int num) { int i=0; float total=0; for(i=0;i total=total+Myabs(k-arr[i]); } return total; } 程序结果如图所示： 5 优点介绍 1.时间需求 （1）如果使用快速排序算法QuickSort将n口油井的y坐标排序后，再计算出中位数median(y) ，则所需时间主要是排序算法用的时间，在平均情况下需要 O(nlog(n))计算时间。 （2）如果用最坏情况下的线性时间选择算法Select 计算出中位数median(y),然后计算n口油井到主管道的最小长度总和，则所需时间主要是选择算法Select用的时间，在最坏情况下需要O (n*n） 计算时间。 （3)如果用随机选择算法RandomizedSelect计算出中位数 median(y),然后计算n口油井到主管道的最小长度总和，则所需时间主要是随机选择算法RandomizedSelect用的时间，在平均情况下需要O(n)计算时间。 2.空间需求 算法所需的空间明显是O(n)。 所以根据比较，此算法是求解此类问题的合理算法。