5.1 数组的算法升华-Java语言基础9-常用API和常见算法

当前位置:　首页>> 技术小册>> Java语言基础9-常用API和常见算法

5.1.1 数组的反转

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

示例：
```bash
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));

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

![](/uploads/images/20230725/0595a373c5aed65aa7c536abb2705b97.png)

示例：
```bash
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 。
  
示例：

```bash
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;
    }
}
```

示例：

```bash
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 次。
- 每一次比较完毕，下一次的比较就会少一个数据参与。

示例：

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

```bash
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);
    }
}
```

示例：

```bash
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 倍等。
数组扩容太多会造成资源浪费，太少会导致频繁扩容，效率低下。

示例：
```bash
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 上。 
-  ② 如果原数组已经满了，那么先扩容，然后重复 ① 。

-  示例：原数组未满

```bash
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));
    }
}
```

示例：原数组已满

```bash
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 后面的元素依次向前移动一位，最后一个元素置空即可。

-  示例：

```bash
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));
    }
}
```

该分类下的相关小册推荐：

Mybatis合辑2-Mybatis映射文件

Java语言基础3-流程控制

Java语言基础12-网络编程

SpringBoot零基础到实战

Mybatis合辑3-Mybatis动态SQL

Java语言基础2-运算符

Java语言基础5-面向对象初级

Java必知必会-Maven初级

深入拆解 Java 虚拟机

Java语言基础8-Java多线程

Java性能调优实战

Java高并发秒杀入门与实战