问题：寻找数组中的最小值和最大值。
一道很简单的题目，一般有下面4种解法：
1 遍历两次，每次分别找出最小值和最大值。
2 只遍历一次，每次取出的元素先与已找到的最小值比较，再与已找到的最大值比较。
3 每次取两个元素，将较小者与已找到的最小值比较，将较大者与已找到的最大值比较。
4 分治：将数组划分成两半，分别找出两边的最小值、最大值，则最小值、最大值分别是两边最小值的较小者、两边最大值的较大者。
这4种算法，哪种效率最高，哪种最低？
后两种算法只要进行1.5*N次比较，因而网上有不少解答都将它们列为最佳答案。但是，算法4用到了递归，而递归法函数调用的开销是很大的，这就注定了该算法的效率肯定不高。那么，算法3就是最高效的吗？还是用代码来验证吧。
后面的代码，对每种算法都实现了两个函数（假设数组长度为N）：
算法1：solve_1a与solve_1b，后者加入两个临时变量，编译器可以将变量储存在寄存器中，不用每次循环都要写内存。比较次数为2*N次。
算法2：solve_2a与solve_2b，前者每次循环必比较2次，后者最好情况下(递减数组)只要比较1次，但最差情况下（递增数组）则要比较2次，比较次数为：N到2 * N次。
算法3：solve_3a与solve_3b，前者每次循环取头尾两元素（从两头往中间取），后者取相邻两元素。比较次数为1.5 * N次。
算法4：solve_4a与solve_4b，后者返回一个结构（只有两个元素），编译器优化可以通过两个寄存器返回该结构，减少写内存次数。（检查gcc产生的汇编，确认有进行该优化）。比较次数为1.5 * N次。
下面是测试结果：（数组长度为6e7，每种测4次取平均值）
|
|
所用时间（毫秒，GCC 4.5） |
所用时间（毫秒，VC 2010） |
||||||||
| 函数名 |
递增 |
递减 |
乱序1 |
乱序2 |
乱序3 |
递增 |
递减 |
乱序1 |
乱序2 |
<script type="text/java script" id="bdshare_js" data="type=tools&uid=12732">
<script type="text/java script" id="bdshell_js">
<script type="text/java script">
var bds_config = {'snsKey':{'tsina':'2386826374','tqq':'5e544a8fdea646c5a5f3967871346eb8'}};
document.getElementById("bdshell_js").src = "http://bdimg.share.baidu.com/static/js/shell_v2.js cdnversion=" + Math.ceil(new Date()/3600000)
<iframe src="http://www.2cto.com/uapi.php tid=89897&catid=339&title=0ru1wEMrK8PmytTM4rXEzvPH A==&forward=http://www.2cto.com/kf/201105/89897.html" width="100%" height="100%" id="comment_iframe" name="comment_iframe" frameborder="0" scrolling="no">
<script type="text/java script">BAIDU_CLB_fillSlot("406189");
<script type="text/java script">BAIDU_CLB_fillSlot("703749");
<script type="text/java script">BAIDU_CLB_fillSlot("182692");
<script type="text/java script">
<script type="text/java script">BAIDU_CLB_fillSlot("771043");
<script type="text/java script">BAIDU_CLB_fillSlot("333829");
关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 |
