9.[Java 基础]数组

1. 数组类型介绍

• 数组是一种常见的数据结构, 用于存放多个同一类型的数据
• 数组中存放的数据，既可以是基本数据类型也可以是引用数据类型
• 数组本身是一种引用数据类型
• 通过 数组名称[数组下标] 来访问数组的元素
• 数组元素如果没有显式的赋值, 默认使用元素对应类型的默认值
• 数组下标是从 0 开始的, 比如第一个元素就是 a[0], 第二个元素就是 a[1]
• 数组的元素可以通过 for 循环访问
• 代码示例

// 使用for循环访问数组内所有元素（遍历数组）
public class Array01 {
    public static void main(String[] args) {
        int a[] = {1, 2, 3, 4, 5};
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

2. 声明数组

有两种语法格式支持声明数组:

// 1. 数据类型 [] 数组名称;
int[] array;

// 2. 数据类型 数组名称[];
int array[];

// int[]  和 int 不是一种数据类型, 
// int[] 定义的是一个 int 类型的数组, 是一个引用数据类型
// int 表示的是一个基本数据类型

3. 数组的初始化

• 数组的初始化就是为数组元素分配内存空间, 并为每个元素赋予初始值

• 数组未初始化时也就未指向任何有效内存, 所以这个数组还不可使用, 只有对数组初始化之后才能使用

• 数组一旦初始化完成, 它所占用的空间将被固定下来, 因此数组的长度将不可改变

• 即使把数组内的元素清空, 数组占用的空间仍然被保留

• 数组初始化有两种方式:

1. 动态初始化: 初始化时指定数组长度, 由系统为数组元素分配初始值
2. 静态初始化: 初始化时显式的指定每个元素的初始值, 由系统根据初始元素的个数决定数组长度

3.1 动态初始化

动态初始化只指定数组的长度, 由系统为每个数组指定初始值, 语法如下:

// 数据类型 数组名 [] = new 数据类型[数组容量]
int a[] = new int[5];
// 或
int[] a = new int[5];

// 也可以先声明在定义的方式初始化数组

// 1. 先声明数组, 这是 a 数组为 null
int a[];
// 或
int [] a;

// 2. 创建数组, 为 a 数组分配 5 个存储空间, 可以存放数据, 每个空间的默认值为 0
a = new int[5];

// 注意:
// 1. 定义数组时需要指定数组的长度, 这个长度就是该数组可以容纳元素的数量
// 2. 定义数组时new 后面的数据类型必须是定义数组的数据类型或其子类

执行动态初始化以后, 就会为每个数组元素指定所需的内存空间, 系统将会负责为这些数据元素分配初始值, 指定初始值情况如下表所示:

类型	默认值
byte, short, int , long	0
Float, double	0.0
char	\u0000
boolean	false
String, 其他引用类型	null

数组初始化之后就可以使用数组了, 包括遍历数组访问数组中的元素, 获取数组长度等等.

// 声明一个数组
int a[] = new int[5];

// 访问数组下标为 0 的元素, (数组的第一个元素)
a[0]; // 值为 0

// 访问数组下标为 1 的元素, (数组的第二个元素)
a[1]; // 值为 0

3.2 静态初始化

静态初始化语法格式:

数据类型[]  数组名称 = new 数据类型[]{元素1值,元素2值,元素3值...}

//也可以使用类型推断
var 数组名称 = new 数组类型[]{元素1值,元素2值,元素3值...}

// 可以简化成 （简化方式不能使用类型推断）
数据类型[]  数组名称 = {元素1值,元素2值,元素3值...}

1. 花括号中的数据类型需要与定义的数据类型一致,或为定义的数据类型的子类

2. 花括号中有多个元素 要用逗号 , 分隔

3. 只有在定义数组的同时进行初始化才能使用简化的静态初始化

4. 动态初始化与静态初始化都可以使用 var 类型推断的方式, 但不能在简化静态初始化数组时使用

• 使用示例

// 定义一个数组
int a[] = {1,2,3};

// 上面初始化相当于
int a[] = new int[3];
a[0] = 1;
a[1] = 2;
a[2] = 3;

4. 数组内存模型

• 数组是一种引用数据类型, 数组元素和数组变量在内存中是分开存放的
• 数组引用变量可以指向任何一块有效的内存, 只有在引用指向内存后, 才能够通过数组变量访问数组元素
• 数组的引用变量是一个局部变量, 存放在栈中, 数组对象存储在堆中
• 如果想要访问数组对象本身, 只能通过数组引用变量来访问
• 多个数组引用变量可以指向同一块内存, 当这块内存中的数据有修改时, 将影响每个指向这块内存的数组引用变量

栈内存中的引用变量会随着方法的结束而销毁, 但堆中的数据因为可能有其他引用变量指向自己, 所以不会跟随引用变量的销毁而销毁, 而是会被垃圾回收器回收, 当一个堆内存的数据没有任何引用变量指向自己时才能够被垃圾回收器回收

如下代码:

int[] a = {1,2,3};
int[] b = {4,5};
// b 的引用指向a
b = a;
// 此时没有引用指向 b对象, 所以会被垃圾回收器回收

此时没有引用变量指向内存地址 0X5678 , 所以会被垃圾回收器回收

4.1 基本类型数组内存

基本数据类型的数组, 数组元素的值直接保存在对应的数组元素中, 在数组初始化时, 先分配空间, 然后将数组元素的值保存到数组元素中

• 如下代码

public class Array12 {
    public static void main(String args[]) {
        int[] a = new int[3];
        for (int i = 0; i < a.length; i++) {
            a[i] = i+10;
        }
        for (int i = 0; i < a.length; i++) {
            System.out.println(i);
        }
    }
}

• 对应内存变化应该是

1. 数组初始化

当定义了 int[] a = new int[3]; 后, 会在栈中增加一个引用变量a, 指向内存地址 0X1234, 并在堆中分配一块内存空间, 在堆中为每个数组元素赋予初始值 0

2. 为数组元素赋值

当使用循环依次为数组中的每个元素赋值后, 元素的值直接存储在对应的内存中, 相当于操作基本类型的变量.

4.2 引用类型数组内存

因为引用类型的数组元素是引用类型, 所以内存情况比基本类型的数组稍微复杂一些,引用类型的数据内存情况如下:

1. 编写java 代码:

public class Array13 {
    public static void main(String args[]) {

        Persion[] p= new Persion[3];
        Persion p1 = new Persion();
        p1.age = 15;
        p1.name="xiaom";
        p[0] = p1;
    }
}
class Persion{
    int age;
    String name;
}

将 p1 对象装进 p 数组以后, p1对象 与 p[0] 元素都指向同一块内存空间, 无论修改 p1 还是 p[0] 都会互相影响

5. 遍历数组

• 数组最常用的方式就是访问数组元素, 包括对数组元素的 取值 和 赋值

• 访问数组元素是通过 数组名称[数组下标] 的方式, 访问到元素后可以把该元素当成一个普通变量使用

• 数组的下标是从 0 开始的, 也就是说数组第一个元素下标为 0, 数组最后一个元素下标为 数组长度 - 1

• 数组有一个长度属性 length , 得到 length 就可以通过循环遍历数组的各个元素

• 当访问数组元素的下标大于或小于数组元素范围的时候, 都会抛出数组下标越界异常

5.1 使用 for 循环遍历数组

public class Array04 {
    public static void main(String[] args) {
        // 定义一个数组, 一共有 5 个元素, 分别是 1,2,3,4,5
        int a[] = {1, 2, 3, 4, 5};
        // a.length 表示数组长度
        // 遍历数组, 并打印每个元素
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

5.2 使用 foreach遍历数组

通常情况下, 我们会使用 for 循环遍历数组, 但 Java 也提供了另外一种遍历数组的方式 foreach

• 使用 foreach 遍历数组更加简洁, 无需得到数组长度即可遍历数组
• foreach 会自动遍历数组中的每个元素
• foreach 在遍历数组时相当于定义了一个临时变量接收数组元素, 所以不能用作为数组赋值
• 代码示例

public class ArrayForeach {
    public static void main(String args[]) {
        // 定义数组
        int[] a = {1,2,3,4,5};
        // 使用 foreach 的方式遍历数组
        for (int i : a) {
            System.out.println(i);
        }
    }
}

6. 使用数组

6.1 数组拷贝

数组拷贝即将一个数组的元素，原封不动的拷贝到另一个数组中

public class Array08 {
    public static void main(String[] args) {
        // 定义数组
        int[] a = {1,2,3};
        // 将数组 a 的数据拷贝到数组 b, 两个数组为独立空间
        int [] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[i] = a[i];
        }

        for (int i = 0; i < b.length; i++) {
            System.out.println("a["+i+"] = "+a[i]);
            System.out.println("b["+i+"] = "+b[i]);
        }
    }
}

6.2 数组反转

public class Array09 {
    public static void main(String[] args) {
        // 定义数组a
        int[] a = {1,2,3,4,5,6,7,8};

        // 定义临时变量
        int temp = -1;
        for (int i = 0; i < a.length/2; i++) {
            temp = a[i];
            a[i] = a[a.length-i-1];
            a[a.length-i-1] = temp;
        }

        // 打印数组元素
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

6.3 数组扩容

public class Array10 {
    public static void main(String args[]) {
        // 定义原始数组
        int [] a = {1,2,3};
        // 定义扩展数组， 长度比原始数组大1
        int [] b = new int[a.length+1];

        // 首先做数组复制
        for (int i = 0; i < a.length; i++) {
            b[i] = a[i];
        }
        // 为扩展数组增加原始数组中没有的元素
        b[b.length-1] = 4;
        // 打印数组元素
        for (int i = 0; i < b.length; i++) {
            System.out.println(b[i]);
        }
    }
}

7. 数组排序

排序是将多个数据按照指定的顺序进行排列的过程.

数组排序根据数据存储位置不同有内部排序和外部排序两种:

内部排序: 指将需要处理的所有数据都加载到内存存储器中进行排序, 包括(交换式排序法, 选择式排序法, 插入式排序法)

外部排序: 数据量过大, 无法全部加载到内存中, 需要借助外部存储进行排序, 包括合并排序法和直接合并排序法

• 冒泡排序

冒泡排序的基本思想是, 通过对待排序的系列从后向前(从下表较大的元素开始), 依次比较相邻的元素值, 若发现逆序则交换, 使值较大的元素主键从前向后移动, 就像水底下的起泡逐渐向上冒

总结冒泡排序的大致流程

1. 假设我们一共有 5 个元素需要排序
2. 一共需进行 4 轮排序, 可以看成是外层循环
3. 每 1 轮排序可以确定一个数的位置, 比如第一轮排序确定最大的数, 第二轮排序确定第二大的数
4. 当进行比较时, 如果前面的数大于后面的数就交换
5. 每轮比较在减少 5-4-3-2-1

• 代码示例

public class Sort01 {
    public static void main(String[] args) {
        int[] arr = {16, 8, 5, 9, 1, 4, 6, 8};

        for(int i = 0;i< arr.length-1;i++){ // 外层循环
            for(int j = 0;j< arr.length-i-1;j++){// 内层循环
                if(arr[j]> arr[j+1]){
                    int tmp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = tmp;
                }
            }
            for (int j = 0; j < arr.length; j++) { // 打印每次外层循环后数组排序情况
                System.out.print(arr[j]+"  ");
            }
            System.out.println();
        }
    }
}

8. 数组中查找数据

我们常用查找数组中的数据有两种方式:

1. 顺序查找
2. 二分法查找

8.1 顺序查找

• 顺序查找就是遍历数组的元素, 知道遇见要查找的数据.

• 代码示例

public class Array11 {
    public static void main(String args[]) {

        // 查找值为 8 的元素, 并返回其下标
        int a[] = {1,4,6,3,56,8,9};
        int index = -1;
        for (int i = 0; i < a.length; i++) {
            if(a[i] == 8){
                index = i;
                break;
            }
        }
        if(index == -1){
            System.out.println("未找到数据");
        }else{
            System.out.println(8 + ", 数组下标为: "+ index);
        }
    }
}

8.2 二分法查找数据

二分查找又称折半查找，二分法查找方法适用于不经常变动而查找频繁的有序列表

优点是比较次数少，查找速度快，平均性能好

缺点是要求待查表为有序表，且插入删除困难

8.2.1 二分法查找的流程

二分查找的基本思想是将n个元素分成大致相等的两部分

取 a[n/2] 与 x 做比较，如果 x = a[ n / 2 ], 则找到 x，算法中止

如果x < a[ n / 2 ], 则只要在数组a的左半部分继续搜索 x

如果x > a [ n / 2 ]，则只要在数组a的右半部搜索 x

• 具体逻辑如下图片所示

• 假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；

• 如果中间位置记录与查找关键字不相等，利用中间位置记录将表分成前、后两个子表，

• 如果中间位置记录的关键字大于查找关键字，则进一步查找前子表

• 如果中间位置记录的关键字小于查找关键字，则进一步查找后子表

• 重复以上过程，直到找到满足条件的记录

• 如果某个位置等于关键字则使查找成功

• 如果直到子表不存在，也没能匹配到关键字则说明列表中没有关键字

8.2.2 代码示例

public class BinarySearch {
    public static void main(String args[]) {
        int arr[] = {2, 5, 9, 13, 30, 41, 55, 58, 67, 72, 78, 83, 88, 95, 99};
        System.out.println(search(arr, 30, 0, arr.length) );
        System.out.println(search(arr, 55, 0, arr.length) );
        System.out.println(search(arr, 78, 0, arr.length) );
        System.out.println(search(arr, 95, 0, arr.length) );
        System.out.println(search(arr, 73, 0, arr.length) );
        System.out.println(search(arr, 0, 0, arr.length) );
        System.out.println(search(arr, 3, 0, arr.length) );
        System.out.println(search(arr, 100, 0, arr.length) );
        System.out.println(search(arr, 98, 0, arr.length) );
    }

    public static int search(int[] arr, int target, int start, int end) {
        // 计算中间值
        int midel = (start + end) / 2;
        // 当中间值等于查找值时, 返回查找值索引
        if(start > end || (arr[midel] != target &&( midel == start || midel == end))){
            return -1;
        }
        else if (arr[midel] == target) {
            return midel;
        } else if (arr[midel] > target) { // 如果中间值大于查找值, 再次中间值之前的部分
            end = midel - 1; // 结束位置等于中间值的前一个下标
            return search(arr, target, start, end);
        } else if (arr[midel] < target) {// 如果中间值小于查找值, 再次中间值之后的部分
            start = midel + 1; // 开始位置等于中间值的后一个下标
            return search(arr, target, start, end);
        } else {
            return -1;
        }
    }
}

9. 操作数据的工具类Arrays

Java提供了一个操作数组的工具类 Arrays, 它提供了一系列操作数组的方法, 如 二分法查找, 复制数组, 数组拼接字符串等功能.

方法	功能
sort(int[] a)	对基本类型数组的比较, 将指定的数组按数字升序排序
sort(int[] a, int fromIndex, int toIndex)	对基本类型数组的比较, 将指定的数组的指定区间按数字升序排序
parallelSort(int[] a)	对基本类型数组的比较, 将指定的数组按数字升序排序, 并行排序, 比单线程更快
parallelSort(int[] a, int fromIndex, int toIndex)	对基本类型数组的比较, 将指定的数组的指定区间按数字升序排序, 并行排序, 比单线程更快
parallelSort(T[] a)	对引用类型数组的排序
parallelSort(T[] a, int fromIndex, int toIndex)	对引用类型数组的指定区间排序
parallelSort(T[] a, Comparator<? super T> cmp)	通过比较器对数组进行排序,参数为引用类型数组与比较器
binarySearch(int[] a, long key)	使用二分法查找数组中的指定元素, 返回元素下标, 注意数组应该是排序后的, 不然可能找不到数据
equals(long[] a, long[] a2)	比较两个数组是否相等, 相等返回 true, 否则返回 false, 数组长度相同
copyOf(T[] original, int newLength)	复制指定的数组，对于在原始数组和副本中都有效的所有索引，这两个数组将包含相同的值。 对于在副本中有效但在原始副本中无效的任何索引，副本将包含null 。 当且仅当指定长度大于原始数组的长度时，此类索引才会存在。 结果数组与原始数组的类完全相同。
compare(int[] a, int[] b)	按字典顺序比较两个int数组
mismatch(int[] a, int[] b)	查找并返回两个int数组之间第一个不匹配的索引，如果没有找到不匹配则返回 -1。

10. 二维数组

• 二维数组可以理解成原来一位数组的每个元素都是一维数组, 这样就构成了二维数组,

• 从内存层面上看, 就是以为数组的每个元素又指向了一个一维数组

public class TwoDimensionalArray01 {
    public static void main(String args[]) {
        // 定义二维数组
        int t[][] = {{0,0,0,0,0},{0,0,0,0,0},{0,0,1,0,0},{0,2,0,3,0}};
        // 遍历二维数组
        for(int i = 0;i< t.length;i++){
            // 遍历二维数组中每个元素的数组中的元素
            for (int j = 0; j < t[i].length; j++) {
                System.out.print(t[i][j]+" ");
            }
            System.out.println();
        }
    }
}

10.1 二维数组的初始化

10.1.1 动态初始化

// 类型[][] 数组名 = new 类型[数组容量][数组容量];
// 或
// 类型[][] 数组名 = new 类型[数组容量][];
int a[][] = new int[2][3];
int a[][] = new int[2][];

// 同样可以先声明在初始化二维数组
// 1. 先声明二维数组
// 类型 数组名[][];
// 2. 初始化二维数组
// 数组名 = new 类型[数组容量][数组容量];
// 或
// 数组名 = new 类型[数组容量][];
int [][]y;
int [] y[];
int y[][];
y = new int[3][];

public class TwoDimensionalArray02 {
    public static void main(String args[]) {

        int a[][] = new int[2][3];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                System.out.print(a[i][j]);
            }
            System.out.println();
        }

        // 1. 声明二维数组
        int a[][];
        // 2. 初始化二维数组
        a = new int[3][];
        // 3. 为二维数组赋值
        for(int i = 0;i<a.length;i++){
            a[i] = new int[i+1];
            for (int j = 0; j <a[i].length ; j++) {
                a[i][j] = j;
            }
        }

        // 4. 使用二维数组
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                System.out.print(a[i][j]+"  ");
            }
            System.out.println();
        } 
    }
}

10.1.2 静态初始化

// 1. 定义 类型 数组名[][] = {{值 1,值 2...},{值 1,值 2...},{值 1,值 2...}...};
int arr[][] = {{1,2,3},{4,5},{6,7,8}};
// 定义了一个二维数组, 
// 其中第一个一维数组有三个元素,
// 第二个一维数组有两个元素
// 第三个一维数组有三个元素

10.2 二维数组的使用

• 使用二维数组存储杨辉三角, 并打印
  1
  1 1
  1 2 1
  1 3 3 1
  1 4 6 4 1
  . . .

public class Yanghui {
    public static void main(String[] args) {
        int a[][] = new int[10][];

        for (int i = 0; i < a.length; i++) {
            a[i] = new int[i+1];
            for(int j = 0;j<a[i].length;j++){
                if(j == 0 || j == a[i].length-1){
                    a[i][j] = 1;
                }else{
                    a[i][j] = a[i-1][j-1]+a[i-1][j];
                }
            }
        }

        for(int i = 0;i< a.length;i++){
            for(int j = 0;j< a[i].length;j++){
                System.out.print(a[i][j]+"  ");
            }
            System.out.println();
        }
    }
}