假设我有一个数字数组：[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()andMath.max()可以接受任意数量的参数。此外，了解对象apply()可用的方法也很重要Function。它允许您使用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 循环搜索最小值或最大值要快。
没有任何可靠的方法可以在不测试每个值的情况下获得最小值/最大值。您不想尝试排序或类似的事情，遍历数组是 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)。
如果您想快速访问数据结构中的最大元素，请查看堆，以找到一种将对象保持在某种顺序中的有效方法。
您必须遍历数组，没有其他方法可以检查所有元素。只需对代码进行一次更正 - 如果所有元素均为负数，则 maxValue 最后将为 0。您应该使用整数的最小可能值对其进行初始化。
如果您要多次搜索数组，最好先对其进行排序，而不是搜索更快（二分搜索），并且最小和最大元素只是第一个和最后一个。
取决于你所说的“最佳”。从理论的角度来看，解决问题的时间比O(n)确定性图灵机少。
天真的算法太循环和更新最小值，最大值。但是，如果您想同时获得 min，max，递归解决方案将需要比朴素算法更少的比较（由于函数调用开销，它不一定更快）。
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() 实际上是编译为 AVM2 操作码的 as3 代码，因此并不比任何其他 as3 代码更“原生”。因此，它不一定是最快的实现。
实际上，鉴于它适用于 Array 类型，它比精心编写的代码 usign Vector 慢：
我使用 gskinner 的 PerformanceTest（向量和数组填充了相同的随机数）对 Math.max 的几个简单的向量和数组实现进行了快速基准比较。使用最新的 AIR SDK/发布播放器（闪存播放器 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;
}
结论是，如果你关心性能，你应该首先在任何地方使用 Vector over Array，而不是总是依赖默认实现，尤其是当它们强制使用 Array 时
PS：使用 for each() 循环的相同实现要慢 12 倍......！
如果您只构建一次数组并且只想找到最大值一次，那么迭代是您能做的最好的事情。
当您想修改数组并且偶尔想知道最大元素时，您应该使用Priority Queue。最好的数据结构之一是Fibonacci Heap，如果这太复杂，请使用较慢但仍然不错的Binary Heap 。
要找到最小值和最大值，只需构建两个堆并更改其中一个中的数字的符号。
这取决于现实世界的应用需求。
如果您的问题只是假设性的，那么基础知识已经解释过了。这是一个典型的搜索与排序问题。已经提到，在这种情况下，在算法上你不会比 O(n) 更好。
但是，如果您正在研究实际用途，事情会变得更加有趣。然后，您需要考虑数组有多大，以及从数据集中添加和删除所涉及的过程。在这些情况下，最好通过动态排序在插入/删除时进行计算“命中”。插入预先排序的数组并不昂贵。
对 Min Max 请求的最快查询响应将始终来自排序数组，因为正如其他人所提到的，您只需获取第一个或最后一个元素 - 给您 O(1) 成本。
有关所涉及的计算成本和大 O 表示法的更多技术解释，请在此处查看 Wikipedia 文章。
缺口。
请考虑到对数组进行排序只会比循环到特定大小的数组更快。如果您的阵列很小（并且任何时候都会如此），那么您的解决方案非常好。但是如果它可能变得太大，您应该在数组较小时使用条件使用排序方法，而在数组太大时使用正常迭代
如果你想同时找到最小值和最大值，循环可以修改如下：
int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}
这应该可以实现 O(n) 时间。
最短的方式：
Math.min.apply(null,array); //这将从数组中返回最小值
Math.max.apply(null,array); //这将从数组中返回最大值
从数组中获取最小值和最大值的其他方式
function maxVal(givenArray):Number
{
var max = givenArray[0];
for (var ma:int = 0; ma<givenArray.length; ma++)
{
if (givenArray[ma] > max)
{
max = givenArray[ma];
}
}
return max;
}
function minVal(givenArray):Number
{
var min = givenArray[0];
for (var mi:int = 0; mi<givenArray.length; mi++)
{
if (givenArray[mi] < min)
{
min = givenArray[mi];
}
}
return min;
}
如您所见，这两个函数中的代码非常相似。该函数设置一个变量 - 最大值（或最小值），然后使用循环遍历数组，检查每个下一个元素。如果下一个元素高于当前元素，则将其设置为最大值（或最小值）。最后，返回数字。
有多种方法可以做到这一点。
如果您真的对速度、运行时间和比较次数感到偏执，请参阅 http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/
以下是 o(n) 的解决方案：-
public static void findMaxAndMinValue(int A[]){
int min =0, max = 0;
if(A[0] > A[1] ){
min = A[1];
max = A[0];
}else{
max = A[1];
min = A[0];
}
for(int i = 2;i<A.length ;i++){
if(A[i] > max){
max = A[i];
}
if(min > A[i]){
min = A[i];
}
}
System.out.println("Maxinum Value is "+min+" & Minimum Value is "+max);
}
很惊讶没有人在这里提到并行性。
如果你真的有一个巨大的数组，你可以在子范围上使用 parallel-for。最后比较所有子范围。但是并行性也会带来一些损失，因此这不会在小型阵列上进行优化。但是，如果您拥有庞大的数据集，它就开始变得有意义了，并且您会获得接近执行测试的线程数量的时间划分减少。
从数组中查找最大值 让我们看看如何使用单个函数获取最小值、最大值
public void findMaxValue(){
int[] my_array = {1,2,,6,5,8,3,9,0,23};
int max = my_array[0];
for(int i=1; i<my_array.length; i++)
{
if(my_array[i] > max)
max = my_array[i];
}
return max;
}
查找最小值也可以做同样的事情
看了大家的评论（感谢大家的关注），我发现“最好”的方式（代码量最少，性能最好）就是简单地对Array进行排序，然后抓取Array中的第一个值：
var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
myArray.sort(Array.NUMERIC);
var minValue:int = myArray[0];
这也适用于对象数组 - 您只需使用 Array.sortOn() 函数并指定一个属性：
// Sample data
var myArray:Array /* of XML */ =
[
<item level="2" name="a" />
<item level="3" name="b" />
<item level="3" name="c" />
<item level="2" name="d" />
<item level="5" name="e" />
]
// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);
var lowestLevel:int = myArray[0].@level;
我希望有一天这对其他人有所帮助！