求最大最小值算法优化

2017-10-26

From : blog.mwxu16.cn

一、问题描述

给定一个int数组，求出其中的最大值和最小值。
很简单的一个问题，循环加比较就出来结果了。
这里对比较的次数进行优化，尽量使得比较次数少一些。

二、常规算法

思路：
遍历数组，找出其中的最大值。
再次遍历数组，找出其中的最小值。
对于一个长度为N的数组，需要比较2N-2次（第一个元素不需要比较啊，当然强迫症患者也可以为了强行写成2N次，比较一下第一个元素）

@Test
    public void test1(){
        int count = 0;
//        int [] arr = {1,2,3,4,5,6,7,8,9,10,11,12};
        int [] arr = {12,11,10,9,8,7,6,5,4,3,2,1};
        int max = arr[0];
        int min = arr[0];
        for(int i = 1; i<arr.length; i++){
            count++;
            if(arr[i] > max){
                max = arr[i];
            }
        }
        for(int i = 1; i<arr.length; i++){
            count++;
            if(arr[i] < min){
                min = arr[i];
            }
        }
        System.out.println("方法一：");
        System.out.println("最大值： " + max + "最小值： " + min);
        System.out.println("共比较： " + count + "次");

    }

三、优化算法

思路：
与常规算法很相似，唯一不同点是，同时进行最大最小值的获取。
若当前最大值小于下一个元素，此时当前最小值肯定小于下一个元素，因此可以少比较一次。
通常情况下：
该算法的比较次数是N-1次到2N-2次之间。
极端情况下：
1、当数组是从小到大排序的有序数组时，只需要比较N-1次。
2、当数组是从大到小排序的有序数组时，与常规算法一样，需要比较2N-2次。

@Test
    public void test2(){
        int count = 0;
        int [] arr = {1,2,3,4,5,6,7,8,9,10,11,12};
//        int [] arr = {12,11,10,9,8,7,6,5,4,3,2,1};
        int max = arr[0];
        int min = arr[0];
        for(int i = 1 ; i<arr.length; i++){
            count++;
            if(arr[i] >max){
                max = arr[i];
                continue;
            }
            count++;
            if(arr[i] < min){
                min = arr[i];
            }
        }
        System.out.println("方法二：");
        System.out.println("最大值： " + max + "最小值： " + min);
        System.out.println("共比较： " + count + "次");
    }

四、总结

只能算略微优化一点吧，同时该算法不稳定，具体优化程度要视情况而定，不过最差的情况也只是与常规算法相同而已。
如果有更好的算法，欢迎在下面评论区提出来一起学习哈~