分治法线性时间选择

1、计算机算法设计与分析实 验 报 告实验名称：线性时间选择问题实验地点：所使用的开发工具及环境：1、 实验目的：熟悉掌握分治算法设计技术二、实验内容：1、按教材所授内容要求，完成“线性时间选择问题”算法。得到一个完整正确的程序。2、问题规模：不少于20003、输出最终结果。3、 基本思想、原理和算法描述： 基本思想：将n个输入元素划分成 n/5个组，每组有5个元素，除最后一组可能不是5个元素之外用任意一种算法，将每组的元素排好序，并取出每组的中位数，共 n/5个。调用Select找出这 n/5个元素的中位数，如果 n/5是偶数就找两个中位数中较大的一个。在这里我用的排序的方法是快速排序。算法描述

2、：template <class Type>Type Select(Type a,int p,int r,int k)int i;if(r-p<75)Qsort(a,p,r);return ap+k-1;/(r-p-4)/5相当于n-5for(i=0; i<=(r-p-4)/5; i+)/将元素每5个分成一组，分别排序，并将该组中位数与ap+i交换位置/使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数Qsort(a,p+5*i,p+5*i+4);Swap(ap+5*i+2,ap+i);/找中位数的中位数Type x = Select(a,p,p+(r-p-4

3、)/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);elsereturn Select(a,i+1,r,k-j);4、 源程序清单：#include<stdio.h>#include<stdlib.h>#include<time.h>#include<windows.h>#include<iostream.h>template <class Type>void Swap(Type &x,Typ

4、e &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 a2000;srand(unsigned)time(NULL);for(int i=0; i<2

5、000; i+)ai = Random(0,2000);cout<<"a"<<i<<":"<<ai<<" "cout<<endl;cout<<"第800小元素是"<<Select(a,0,1999,800)<<endl;/重新排序，对比结果Qsort(a,0,1999);for( i=0; i<2000; i+)cout<<"a"<<i<<&quo

6、t;:"<<ai<<" "cout<<endl;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(p<r)Ty

7、pe 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=ap;while(true)while(a+i<x&&i<r);while(a-j>x);if(i>=j) break;Swap(ai,aj);ap=aj;aj=x;return j;template <class Type>Type Se

8、lect(Type a,int p,int r,int k)int i;if(r-p<75)Qsort(a,p,r);return ap+k-1;/(r-p-4)/5相当于n-5for(i=0; i<=(r-p-4)/5; i+)/将元素每5个分成一组，分别排序，并将该组中位数与ap+i交换位置/使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数Qsort(a,p+5*i,p+5*i+4);Swap(ap+5*i+2,ap+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);elsereturn Select(a,i+1,r,k-j);5、 程序运行结果（包括上机调试的情况、调试所遇到的问题是如何解决的，并对调试过程中的问题进行分析，对执行结果进行分析。）： 在本次实验中遇到了一些问题。在写select方法调用的时候调用不了，然后产