假设我有一个数字数组：[2,3,3,4,2,2,5,6,7,2]
那么最好的方式是如何查找该数组中的最小值或最大值？
目前，为了获取最大值，我正在遍历数组，并在新值大于现有值时将变量重置为该值：
var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = 0;
for each (var num:Number in myArray)
{
if (num > maxValue)
maxValue = num;
}
这种方式似乎并不是最高效的做法（我尽可能避免使用循环）。
其他人的理论答案都很好，但让我们实际一点。ActionScript提供了你需要的工具，以便在这种情况下，你甚至不需要编写循环！
首先，注意到Math.min()和Math.max()可以接受任意数量的参数。此外，重要的是理解Function对象可用的apply()方法。它允许你使用一个Array传递参数给函数。让我们利用这两个工具：
var myArray:Array = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = Math.max.apply(null, myArray);
var minValue:Number = Math.min.apply(null, myArray);
最好的部分是：“循环”实际上是使用本地代码（在Flash Player内部）运行的，因此它比使用纯ActionScript循环搜索最小值或最大值更快。
apply 调用函数已知性能较差，与普通函数调用相比。 - Vitaly没有可靠的方法可以获得最小/最大值，除非测试每个值。你不想尝试排序或类似的操作，遍历数组的时间复杂度是O(n)，这比任何排序算法在一般情况下都要更好。
如果：
那么有一个算法可以在3n/2次比较中找到最小值和最大值。需要做的是成对处理数组元素。应将一对中较大的与当前最大值进行比较，将一对中较小的与当前最小值进行比较。此外，如果数组包含奇数个元素，则需要特别注意。
以下是C++代码（借用了Mehrdad的一些代码）。
struct MinMax{
int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
MinMax min_max;
int index;
int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
if ( n%2 != 0 ){// if n is odd
min_max.Min = array[start];
min_max.Max = array[start];
index = start + 1;
}
else{// n is even
if ( array[start] < array[start+1] ){
min_max.Min = array[start];
min_max.Max = array[start+1];
}
else{
min_max.Min = array[start+1];
min_max.Max = array[start];
}
index = start + 2;
}
int big, small;
for ( int i = index; i < n-1; i = i+2 ){
if ( array[i] < array[i+1] ){ //one comparison
small = array[i];
big = array[i+1];
}
else{
small = array[i+1];
big = array[i];
}
if ( min_max.Min > small ){ //one comparison
min_max.Min = small;
}
if ( min_max.Max < big ){ //one comparison
min_max.Max = big;
}
}
return min_max;
}
很容易看出，需要比较的次数为3n/2。循环运行n/2次，在每次迭代中执行3次比较。这可能是我们能够实现的最优解。目前，我无法确定确切的来源。（但是，我认为我在某个地方看到过证明。）
Mehrdad提供的递归解决方案，可能也实现了这个最小比较次数（最后一行需要更改）。但是，使用相同数量的比较，由于函数调用的开销，迭代解决方案总是会击败递归解决方案，正如他所提到的。然而，如果只关心找到几个数字的最小值和最大值（如Eric Belair所做），在今天的计算机上，任何上述方法都不会有任何区别。对于大型数组，差异可能很大。
尽管此解决方案和Matthew Brubaker提供的解决方案具有O(n)复杂度，但在实践中，应仔细评估涉及的隐藏常数。他的解决方案中比较的次数为2n。与2n比较相比，使用3n/2比较的解决方案获得的加速效果将是显着的。
如果数组未排序，则这是您可以获得的最佳结果。如果已排序，则只需取第一个和最后一个元素。
当然，如果它没有排序，那么先进行排序并获取第一个和最后一个元素的效率肯定比仅循环一次要低。即使是最好的排序算法也必须多次查看每个元素（每个元素平均需要 O(log N) 次）。这是总共 O(N*Log N)。而简单扫描一次仅为 O(N)。
如果您想快速访问数据结构中的最大元素，请查看堆以了解一种有效的方式来保持某种顺序的对象。
你必须循环遍历数组，没有其他方法可以检查所有元素。对于代码的一个纠正 - 如果所有元素都是负数，则最大值将在结尾处为0。您应该将其初始化为整数的最小可能值。
如果您要多次搜索数组，则最好先对其进行排序，然后搜索更快（二进制搜索），最小和最大元素仅为第一个和最后一个。
取决于你所谓的“最好”。从理论角度来看，在确定性图灵机上，你不能在少于O(n)（n为问题规模）的时间内解决这个问题。
朴素算法是太过循环和更新最小值、最大值了。然而，如果你想同时获得最小值和最大值，使用递归解决方案将需要比朴素算法更少的比较（由于函数调用开销，它不一定更快）。
struct MinMax{
public int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
if (start == end)
return new MinMax { Min = array[start], Max = array[start] };
if (start == end - 1)
return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;
MinMax res1 = FindMinMax(array, start, (start + end)/2);
MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}
最简单的解决方案是排序并获取第一个和最后一个项目，尽管显然不是最快的 ;)
在性能方面，找到最小值或最大值的最佳解决方案是您编写的朴素算法（使用单个循环）。
Math.max()实际上是AS3代码编译成AVM2操作码，因此并不比任何其他AS3代码更“本地”。因此，它不一定是最快的实现。
实际上，考虑到它适用于Array类型，它比使用Vector仔细编写的代码要慢：
我使用gskinner的PerformanceTest对几个天真的Vector和Array实现进行了快速基准测试比较Math.max，（Vector和Array被填充相同的随机数字)。在最近的AIR SDK/发布播放器（flash player WIN 14.0.0.122 RELEASE，使用AIR SDK 14编译）中，最快的Vector实现似乎比Math.max快3倍以上:
平均1,000,000个值需要3.5毫秒，而Math.max()的平均时间为11毫秒。
function max(values:Vector.<Number>):Number
{
var max:Number = Number.MIN_VALUE;
var length:uint = values.length;
for (var i:uint = 0; i < length ; ++i)
if (values[i] > max)
max = values[i];
return max;
}