5.1.1 数组的反转

• 所谓的数组的反转：就是一开始是 [1,2,3,4,5] ，经过数组的反转之后变成了 [5,4,3,2,1] 。
• 其实，数组的反转就是对称位置的元素交换。
  注意：数组的反转不是数组的倒叙遍历。
• 方法一：
  • 借助一个新的数组。
  • 首尾对应位置交换。
  • 将新数组的地址赋值给旧数组。

示例：

package com.github.array.demo1;
import java.util.Arrays;
/**
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        // 原来的数组
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        // 新的数组
        int[] newArr = new int[arr.length];
        // 给新的数组中插入值
        for (int i = 0; i < newArr.length; i++) {
            newArr[i] = arr[arr.length - 1 - i];
        }
        // 将原来的数组指向新的数组
        arr = newArr;
        // 打印输出
        System.out.println(Arrays.toString(arr));
    }
}

方法二：数组对称位置的元素互换。

示例：

package com.github.array.demo2;
import java.util.Arrays;
/**
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        // 原来的数组
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        // 数组反转
        for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        // 打印输出
        System.out.println(Arrays.toString(arr));
    }
}

5.1.2 数组的二分查找法

• 数组的查找：判断一个元素是否存在于数组中。
• 数组的基本查找法：遍历数组，判断即可。

• 数组的二分查找法（折半查找法）：要求数组元素必须支持比较大小，并且数组中的元素已经按大小排好序，然后对半查找。

• 二分查找法的步骤：

  • ① 定义两个遍历，表示要查找的范围。默认min = 0，max = 最大索引。
  • ② 循环查找，但是min <= max。
  • ③ 计算出 mid 的值。
  • ④ 判断 mid 位置的元素是否为要查找的元素，如果是，直接返回的索引。
  • ⑤ 如果要查找的值在 mid 的左半边，那么 min 值不变，max = mid -1，继续下次循环查找。
  • ⑥ 如果要查找的值在 mid 的右半边，那么 max 值不变，min = mid +1，继续下次循环查找。
  • ⑦ 当 min > max 的时候，表示要查找的元素在数组中不存在，返回 -1 。

示例：

package com.github.array.demo3;
/**
 * 基本查找法
 * 
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int result = basicSearch(arr, 6);
        System.out.println("result = " + result);
    }
    /**
     * 
     * 数组的基本查找法
     * 
     * @param arr 数组
     * @param key 元素
     * @return 如果元素在数组中，则返回元素在数组中的索引位置；否则，返回-1
     */
    public static int basicSearch(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                return i;
            }
        }
        return -1;
    }
}

示例：

package com.github.array.demo4;
/**
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = {1, 5, 8, 12, 15};
        int result = binarySearch(arr, 9);
        System.out.println(result);
    }
    /**
     *
     * 数组的二分查找法
     *
     * @param arr 数组
     * @param key 元素
     * @return 如果元素在数组中，则返回元素在数组中的索引位置；否则，返回-1
     */
    public static int binarySearch(int[] arr, int key) {
        // 起始元素索引
        int min = 0;
        // 最后元素索引
        int max = arr.length - 1;
        while (min <= max) {
            // 计算中间元素的索引
            int mid = (min + max) / 2;
            // 如果中间元素就是需要查找的元素，直接返回索引
            if (key == arr[mid]) {
                return mid;
            }
            // 如果需要查找的元素比中间的元素大，那么min就是此时的mid+1，然后再计算mid
            if (key > arr[mid]) {
                min = mid + 1;
            }
            // 如果需要查找的元素比中间的元素小，那么max就是此时的mid-1，然后再计算mid
            if (key < arr[mid]) {
                max = mid - 1;
            }
        }
        return -1;
    }
}

5.1.3 冒泡排序

• 排序：将一组数据按照固定的规则进行排列。
• 冒泡排序：相邻的数据两两比较，小的放在前面，大的放在后面。

注意：

• 如果有 n 个数据进行排序，总共需要比较 n-1 次。
• 每一次比较完毕，下一次的比较就会少一个数据参与。

示例：

package com.github.array.demo5;
import java.util.Arrays;
/**
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 1, 4};
        System.out.println("排序之前：" + Arrays.toString(arr));
        sort(arr);
        System.out.println("排序之后：" + Arrays.toString(arr));
    }
    /**
     * 冒泡排序
     * 
     * @param arr 需要排序的数据
     */
    public static void sort(int[] arr) {
        // 外层循环控制的是次数，比数组的长度少1次
        for (int i = 0; i < arr.length - 1; i++) {
            // 内层循环就是实际循环比较的
            // -1 为了让数组不越界
            // -i 每一轮结束之后，就会少比一个数字
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

5.1.4 递归
递归：以编程的角度来看，递归指的是方法定义中调用方法本身的现象。
递归解决问题的思路：
① 将一个复杂的问题层层转换为一个 和原问题类似的规模较小 的问题来求解。
② 递归策略只需要 少量的程序 就可以描述出解题过程所需要的多次的重复计算。
递归解决问题要遵循以下的规则：
① 递归出口：否则会内存溢出。
② 递归规则：和原问题相似的规模较小的问题。
示例：

package com.github.array.demo7;
/**
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        int sum = sum(100);
        System.out.println("sum = " + sum);
    }
    /**
     * 使用递归求和
     * 
     * @param n 整数
     * @return 和
     */
    public static int sum(int n) {
        if (n == 1) {
            return 1;
        }
        return n + sum(n - 1);
    }
}

示例：

package com.github.array.demo8;
/**
 * 需求：用递归求5的阶乘，并将结果输出在控制台上。 
 * 分析： 
 * ① 阶乘：一个正整数的阶乘是所有小于以及等于该数的正整数的乘积，自然数n的阶乘写作n! 
 * ② 递归出口：1!=1 
 * ③ 递归规则：n!=n*(n-1)!
 * 
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        int factorial = factorial(5);
        System.out.println("factorial = " + factorial);
    }
    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

5.1.5 数组的扩容
当原来的数组长度不够的时候需要扩容，那么新建一个数组，并指定长度，其长度为原来的 1.5 倍或 2 倍等，然后将元素复制到新数组中，并将新添加的元素放到新数组的后面。

注意：
新数组的长度定义多少合适，看实际情况，如果新增的元素个数确定，那么可以直接指定长度；如果新增的元素个数不确定，那么可以扩容为原来的 1.5 倍或 2 倍等。
数组扩容太多会造成资源浪费，太少会导致频繁扩容，效率低下。

示例：

package com.github.array.demo9;
import java.util.Arrays;
/**
 * 数组扩容
 * 
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        // 原数组
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        // 扩容的数组
        int[] newArr = new int[arr.length * 2];
        // 将数组的数据拷贝到新数组中
        System.arraycopy(arr, 0, newArr, 0, arr.length);
        // 如果还需要使用arr，可以让arr指向新数组
        arr = newArr;
        // 添加新数据到arr的最后
        arr[8] = 10;
        // 遍历显示
        System.out.println(Arrays.toString(arr));
    }
}

5.1.6 数组元素的插入

• 在原数组的某个 index 插入一个元素。
• ① 如果原数组未满，那么直接将 index 后面的元素（包括 index 上的元素）移动到后面，然后将元素插入到 index 上。

• ② 如果原数组已经满了，那么先扩容，然后重复 ① 。

• 示例：原数组未满

package com.github.array.demo10;
import java.util.Arrays;
/**
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        // 原数组
        String[] str = new String[5];
        str[0] = "张三";
        str[1] = "李四";
        str[2] = "王五";
        // 现在想在index为1的位置上插入一个元素赵六
        // 将index为1的位置以及后面的元素依次移动1位
        System.arraycopy(str, 1, str, 2, 2);
        // 在index为1的位置插入元素
        str[1] = "赵六";
        // 打印输出
        System.out.println(Arrays.toString(str));
    }
}

示例：原数组已满

package com.github.array.demo11;
import java.util.Arrays;
/**
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        // 原数组
        String[] str = new String[3];
        str[0] = "张三";
        str[1] = "李四";
        str[2] = "王五";
        // 现在想在index为1的位置上插入一个元素赵六
        String[] dest = new String[4];
        // 扩容
        System.arraycopy(str, 0, dest, 0, str.length);
        // str指向新数组
        str = dest;
        // 将index为1的位置以及后面的元素依次移动1位
        System.arraycopy(str, 1, str, 2, 2);
        // 在index为1的位置插入元素
        str[1] = "赵六";
        // 打印输出
        System.out.println(Arrays.toString(str));
    }
}

5.1.7 数组元素的删除

• 希望删除某个 index 上的元素，但是不希望数组中间空的元素，那么就将 index 后面的元素依次向前移动一位，最后一个元素置空即可。

• 示例：

package com.github.array.demo12;
import java.util.Arrays;
/**
 * @author maxiaoke.com
 * @version 1.0
 * 
 */
public class Test {
    public static void main(String[] args) {
        String[] arr = {"张三", "李四", "王五"};
        // 希望删除index为1的元素，但是不希望index为1上为空
        System.arraycopy(arr, 2, arr, 1, 1);
        // 最后一个元素置空
        arr[2] = null;
        // 打印输出
        System.out.println(Arrays.toString(arr));
    }
}