加载中…
分治法求数组中最大和最小的元素
(2010-10-22 16:45:06)
标签：
杂谈 |
分类： 数据结构 |
分治法
package fenzhi;
public class Min_Max {
public
static IntPair min_max(int[] a, int low, int high){ //
1. low和 high不能写死，要接收参数
IntPair pair
= new
IntPair(); //
2. 定义见算法 5-5
if
(low>high-2){
// 3.
//
if
(a[low]<a[high]){
// 4.
//
pair.x =
a[high];
//
pair.y =
a[low]; } // 5.
//
//
else{ //
6.
//
pair.y =
a[high];
//
pair.x =
a[low]; } // 7.
//
} // 8.
pair.x=a[low]>a[high]?a[low]:a[high];
pair.y=a[low]>a[high]?a[high]:a[low];
}
else{ //
9.
int mid =
(low +
high)/2; //
10.
IntPair p1 =
min_max(a,low,mid);
// 11.
IntPair p2 =
min_max(a,mid+1,high);
// 12.
pair.x =
p1.x>p2.x ? p1.x :
p2.x; //
13.
pair.y =
p1.y<p2.y ? p1.y :
p2.y; //
14.
} //
15.
return
pair; //
16.
}
// 17.
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，
否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地 解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法整数数组 a[0, n-1] 输出：a 中的最大与最小元素 代码：
public IntPair simpleMinMax (int[] a){ IntPair pair = new IntPair();
pair.x = a[0];
pair.y = a[0];
for (int i=1; i<a.length; i++){
if (pair.x<a[i]) pair.x = a[i];
if (pair.y>a[i]) pair.y = a[i];
}
return pair;
}
private class IntPair{
int x;
int y;
}
算法 5-5 中一共要进行 2n-2 次比较。 然而另外一种解决这个问题的方法是使用分治法：可以把数组 a 分成大小相等的两个数
组 a1 和 a2，在 a1 和 a2 中分别找出最大和最小元素，然后比较 a1 和 a2 中的最大和最小元 素，两个最大元素中大的就是原数组中的最大元素，两个最小元素中小的就是原数组中的最 小元素。为了要在 a1 和 a2 中找到最大与最小元素，可以重复上述过程，分别将 a1 分为 a11、 a12 以及将 a2 分为 a21、a22，该过程可以一直进行下去，直到在某次分割后的数组中元素 的个数少于三个的时候，此时最多只需要一次比较就可以找出该数组中的最大和最小元素。package fenzhi;
public class Min_Max {
//
//
//
//
//
//
//
//