寻找数组中最大值和最小值—分治算法

题目：给定一个数组，求其最大值和最小值

解法：复杂度最低的算法应该是采用分治算法求得的。

分治算法，其基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可得到原问题的解。

如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

改题目的代码：

import java.util.*;
	class Group
	{
		private int max;
		private int min;
		public void setMax(int max)
		{
			this.max = max;
		}
		public void setMin(int min)
		{
			this.min = min;
		}
		public int getMax()
		{
			return max;
		}
		public int getMin()
		{
			return min;
		}
	}
public class FindArrayMax
{
	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		System.out.println("Enter an array(10):");
		int[] arr = new int[10];
		for(int i=0;i<10;i++)
			arr[i] = s.nextInt();
		Group a = new Group();
		a = Search(arr,0,9);
		System.out.println("the max of the array is:"+a.getMax());
		System.out.println("the min of the array is:"+a.getMin());
	}
	public static Group Search(int[] arr,int begin,int end)
	{
		Group p = new Group();
		if(end-begin<=1)
		{
			if(arr[begin]<arr[end])
			{
				p.setMax(arr[end]);
				p.setMin(arr[begin]);
			}
			else
			{
				p.setMax(arr[begin]);
				p.setMin(arr[end]);
			}
		}
		else
		{
			Group p1 = Search(arr,begin,begin+(end-begin)/2);
			Group p2 = Search(arr,begin+(end-begin)/2+1,end);
			if(p1.getMax()>p2.getMax())
				p.setMax(p1.getMax());
			else
				p.setMax(p2.getMax());
			if(p1.getMin()>p2.getMin())
				p.setMax(p2.getMin());
			else
				p.setMax(p1.getMin());
		}
		return p;
	}
}

扩展问题：

找出N个数组中的第二大数，用分治算法：

Search(int[] arr,int left,int right,int max,int smax)
{
	if(right-left<=1)
	{
		if(arr[left]>arr[right])
		{
			max = a[right];
			smax = a[left];
		}
		else
		{
			max = a[left];
			smax = a[right];
		}
	}
	else
	{
		Search(arr,left,left+(right-left)/2,lmax,lsmax);
		Search(arr,left+(right-left)/2+1,right,rmax,rsmax);
		if(lmax>rmax)
		{
			max = lmax;
			if(lsmax>rmax)
				smax = lsmax;
			else
				smax = rmax;
		}
		else
		{
			max = rmax;
			if(rsmax>lmax)
				smax = rsmax;
			else
				smax = lmax; 
		}
	}
}

分治算法同样也可以很好的解决排序问题，即分治（归并）排序

代码如下：

MergeSort(int[] arr,int left,int right)
{
	if(left<right)
	{
		int mid = (right+left)/2;
		MergeSort(arr,left,mid);
		MergeSort(arr,mid+1,right);
		Merge(arr,left,mid,right);
	}
}
Merge(int[] arr,int left,int mid,int right)
{
	int[] number = new int[arr.length];
	int i=left;
	int j=mid+1;
	int p=0;
	while(i<=mid&&j<=right)
		number[p++] = (arr[i]<=arr[j])?arr[i++]:arr[j++];
	while(i<=mid)
		number[p++] = arr[i++];
	while(j<=right)
		number[p++] = arr[j++];
	for(int i=0;i<arr.length;i++)
		arr[i] = number[i];
}