在一个随机数组中同时求出最大值与最小值，要求 辅助空间 O(1)【线性复杂度】,最坏情况下比较次数 3n/2, n为数组元素数
| 提供一个方法：
假设待处理的数组为A[1...N]，该算法分为两步
1.
对A中的元素做如下的比较，A[1]与A[N]，A[2]与A[N-1]，...,
A[N/2]与A[N-N/2+1](如果N为奇数，则A[N/2+1]没有参与比较），对于每一个A[i]与A[N-i+1]，如果A[i]>A
[N-i+1]，则交换他们的值，否则，保持他们的值不变。
2. 第一步的结果是将数组A分成两半，可以证明，最小值一定在前一半中，而最大值一定在后一半中。分别对前一半求最小值，对后一半求最大值，即得到整个数组的最大值和最小值。
对于第一步，比较次数为n/2，第二步的比较次数为n，因此整个算法的比较次数为3n/2（该算法需要严格的3n/2次比较，可能还存在更优的算法，不过暂时没想到） |
|
|