找出包含n个元素的数组中的最小值和最大值 最简单的方法就是独立的使用n 次循环 然后分别得到最小值和最大值 如是这样的 共用了 n 次比较
但是我们可以使用比较次数更低的方法来找出最小值和最大值 方法如下
先将一对元素互相进行比较 然后把最小值跟当前最小值进行比较 把最大值跟当前最大值进行比较 因此每两个元素需要 次比较
如果n 为奇数 那么比较的次数是<! [if supportFields] > <! [endif] >次比较 如果n 为偶数 那么比较的次数是 n/ 次比较 因此 不管是n是奇数还是偶数 比较的次数至多是 具体的c# 代码如下
public void LookMinMaxElement(Int [] a ref Int min ref Int max)
{
for (int i = ; i <= a Length ; i+= )
{
if (!(i + >= a Length))
{
if (a[i] < a[i + ])
{
if (a[i] < min)
{
min = a[i];
}
if (a[i + ] > max)
{
max = a[i + ];
}
}
else
{
if (a[i + ] < min)
{
min = a[i + ];
}
if (a[i] > max)
{
max = a[i];
}
}
}
}
}
测试代码如下
[TestMethod()]
public void LookMinMaxElementTest()
{
MinMaxElement target = new MinMaxElement(); // TODO: Initialize to an appropriate value
int[] a = new Int [ ] { };
Int min = Int MaxValue;
Int max = Int MinValue;
target LookMinMaxElement(a ref min ref max);
Assert AreEqual( min);
Assert AreEqual( max);
a = new Int [ ] { };
min = Int MaxValue;
max = Int MinValue;
target LookMinMaxElement(a ref min ref max);
Assert AreEqual( min);
Assert AreEqual( max);
lishixinzhi/Article/program/net/201311/13069