2019-11-14 · 数组中涉及到的常见算法（中）

接着上一章，继续学习数组中涉及到的常见算法

常见算法

如何实现数组的反转？

/*
 * 实现数组的反转
 */
public class Test {
    public static void main(String[] args) {
        
        String[] arr = new String[] {"JJ","GG","MM","DD","CC","LL"};
        
        //反转方法一：
//      for(int i=0; i<arr.length / 2; i++) {//到中间就不用再换了
//          //首元素和尾元素相互调换
//          String temp = arr[i];
//          arr[i] = arr[arr.length-1-i];
//          arr[arr.length-1-i] = temp;
//      }
        
        //反转方法二：
        for(int i=0,j=arr.length-1; i<j; i++,j--) {
            String temp = arr[i];
            arr[i] = arr[arr.length-1-i];
            arr[arr.length-1-i] = temp;
        }
        
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }   
    }
}

如何实现在数组中（线性）查找元素的下标？

/*
 * 实现数组元素的查找（线性查找）
 */
public class Test {
    public static void main(String[] args) {
        
        String[] arr = new String[] {"JJ","GG","MM","DD","CC","LL"};
        //设置一个标识
        boolean isFlag = true;
        //查找CC
        String dest = "CC";
        
        for(int i=0; i<arr.length; i++) {
            if(dest.equals(arr[i])) {//这是String类的对比语句
                System.out.println("恭喜！找到了！");
                System.out.println("元素下标为：" + i);
                isFlag = false;//标识改为false
                break;
            }
        }
        if(isFlag) {//如果是true，就输出没有找到
            System.out.println("很遗憾没有找到！");
        }
    }
}

如何实现在数组中（二分法）查找元素的下标？

二分法查找，就是先取到数组的一个中间值，然后把要对比的值和中间值做对比。中间值大了，就把中间值再减一半。中间值小了，就把中间值增大。

例如：图中要取5，中间值是10，中间值大了，所以把中间值后面的数组砍掉。然后再在新的数组中取中间值，继续比较直到找到为止。

二分法图解

/*
 * 实现数组的二分法查找
 * 前提：所要查找的数组必须有序！
 */
public class Test {
    public static void main(String[] args) {
                //定义一个数组
        //前提：所要查找的数组必须有序！
        int[] array = new int[]
                {-95,-56,-26,-17,-5,0,1,35,67,98,300,412};
        
        boolean isFlag = true;
        int num = 412;
        //定一个头尾
        int first = 0;
        int end = array.length-1;
            
        while(first <= end) {//头不能超过尾
            //二分法需要的中间值
            int middle = (end+first)/2;
            
            if(num == array[middle]) {
                System.out.println("恭喜你找到了！");
                System.out.println("下标为：" + middle);
                isFlag = false;
                break;
            }else if(num < array[middle]) {
                //要找的值比中间值还小，就把后面的值去掉
                end = middle - 1;
            }else {//num > array[middle]
                //要找的值比中间值还大，就把前面的值去掉
                first = middle + 1;
            }
        }
        
        if(isFlag) {
            System.out.println("很遗憾没找到！");
        }
    }
}