l算法考试程序代码.docxVIP

分治算法邮局选址问题问题描述：在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。要求：为建邮局选址，使得n个居民点到邮局之距离的总和最小。解题思路：因为街区中任意2 点(x 1,y 1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y 1-y2|度量所以我们可以将任意2点的距离可以看作为x坐标上的距离|x1-x2|和y坐标的距离|y 1-y2|之和。这样我们容易想到输油管道问题那个题目(我博客的第一篇文章)，所以我们可以将这个2维的题目拆分为2个一维然后将它们合并就行了。? ?一 ?找出x坐标(此时可忽略y坐标)的最优点参考输油管道问题可知最优点是中点，可以用 1.线性时间找中位数，2.先排序在找中位数 (因为输油管道问题是用的线性时间做的所以这个我贴的代码是用的排序)? ?二 ?找出y坐标(此时可忽略x坐标)的最优点 ?参考输油管道问题?可知最优点是中点，可以用 1.线性时间找中位数，2.先排序在找中位数?(因为输油管道问题是用的线性时间做的所以这个我贴的代码是用的排序)? 三 ? 合并将x ,y坐标所求的距离和相加即是最有值。算法分析快速排序选择中位数快排时间复杂度：O（nlogn），求距离和：O（n）总复杂度：O(nlogn)。（2）随机选择法求中位数最坏情况下，randomizedSelect的时间复杂度是：O（n2），平均时间为O（n）故时间复杂度为：O（n2）。线性时间选择求中位数最坏情况下，select算法时间复杂度为O（n），求距离和：O（n）总复杂度：O(n)。以上三种算法的空间复杂度均为O（n）。数据结构类“排序”Sortclass Sort属性:方法:public static void QuickSort(int[] arr,intlow,int height)//快速排序算法类“保存文本中的数据类”StringDataclass StringData属性:private intresultX, resultY; //定义结果集X,Y private int distance; //最小的距离和private String dataString; //原始数据信息private int[] x = null, y = null;//保存用户输入的整形数据,可以操作 private int[] resX = null, resY = null;//保存用户输入的原始数据方法: public void StringToInt()//该方法用于将字符串转变成相应的整型数组 public void getResult()//该方法用来计算最优的结果集合（3）类“处理字符串类”StringUtilclass StringUtil属性:方法: public String IntToString(int[] arr) //该方法用于将整形数据转换成字符数组（4）类“界面操作类”Form1,Sheetclass Form1,Sheet属性:方法:class Sort { //对数据进行快速排序 //从小到大进行排序public static int Partition(int[] arr, int low, int height) { //获取首元素,并将其作为阈值进行快速排序int index=arr[low];inti = low , j = height;if (low = height) return low;while (i j) { //从右边开始找到第一个比自己小的元素while (arr[j] index i j) {j--; }if (i j) {arr[i++] = arr[j]; }else break; //从左开始找到第一个比自己大的元素while (arr[i] index i j) {i++; }if (i j) {arr[j--] = arr[i]; }else break; }arr[i] = index;returni; }public static void QuickSort(int[] arr,intlo