数组

数组可以存放多个同一类型的数据，数组也是一种数据类型，是引用类型

数组就是一组数据

数组的定义：

double[] newArray = {1.2, 2, 3.5};

double[] newArray 等价于double newArray[]

double[]表示声明double类型的数组，数组中的数据都应该是double类型

newArray表示定义的数组名

{1.2, 2, 3.5}表示数组的值（数组的元素），我们可以通过元素的下标来进行数组中具体元素的访问[i]

下标是从0开始编号的，表示数组中的第一个元素

数组可以通过for循环进行遍历，从而读取数组中的每个元素：

double[] newArray = {1.2, 2, 3.5};
for (int i = 0; i < newArray.length; i++) {
    System.out.println(newArray[i]);
}

注意事项：

• 数组是多个相同类型数据的组合，实现对这些数据的统一管理

• 数组中的元素可以是任何数据类型，包括基本类型和引用类型，但不能混用

  如果满足自动类型转换的，那么可以混合使用

• 数组创建后，如果没有赋值，有默认值，不同的类型默认值不一样：int 0、short 0、byte 0、long 0、float 0.0、double 0.0、char \u0000、boolean false、String null

• 使用数组的步骤：1.声明数组并开辟空间；2.给数组各个元素赋值；3.使用数组

• 数组的下标是从0开始的

• 数组下标必须在指定范围内使用，下标的最大值是数组的长度减一，否则会报错：下标越界异常

• 数组属于引用类型，数组的数据类型是对象object

---

动态初始化

动态初始化方式一：数据类型 数组名[] = new 数据类型[大小];

如：int a[] = new int[5]; 创建了一个数组，名字为a，存放5个int类型的数据，变量a[0]就指向了数组中的第一个元素

动态初始化方式二：

• 先声明数组：数据类型 数组名[]; 如：int a[]; 内存中有了数组a变量，但是是空值，没有返回空间
• 再创建数组：数组名 = new 数据类型[大小]; 如：a = new int[10]; 内存中开辟了空间

---

静态初始化

直接在声明的时候给定具体的值：数据类型 数组名[] = {元素值, 元素值, ...};

---

数组赋值机制

对于基本数据类型赋值，这个值就是具体的数据，且互相不影响，这种赋值方式为值拷贝，但是对于数组进行赋值，数组在默认情况下是引用传递，赋的值是地址，赋值方式为地址拷贝或者引用拷贝

int arr1[] = {1, 2, 3};
int arr2[] = arr1;     
arr2[0] = 10; // arr1数组的第一个值也变成了10，数组arr2的变化会影响arr1的变化，两个数组共有一共内存地址

从内存地址的角度进行分析：

在jvm中，内存由三个部分组成：栈、堆和方法区

对于值传递\值拷贝：会在栈中开辟一块空间（基本类型的存储都是在栈中开辟空间的），如果将n1赋值给n2，会将值拷贝一份，放到一个新开辟的内存空间，后续n2的值发生改变，不会对n1的值造成任何影响

对于引用传递\地址拷贝：数组会在栈中开辟一块空间，用于存放地址，地址的具体内容在堆中存放，通过地址可以访问到堆中的数据，如果数组进行赋值，会将地址进行拷贝，但是指向的还是同一个区域，所有对arr2数组的内容进行修改，会影响arr1的内容

---

数组的拷贝

经过数组的赋值机制，我们知道，我们对数组的赋值只是地址拷贝，两个数组公用一个内存地址

如果我们就想要得到一个完整的数组，我们需要进行数组的拷贝，这样两个数组的数据空间是独立的

int arr1[] = {10, 20, 30};
// 为arr2开辟一个新的数据空间，大小和arr1数组一样
int arr2[] = new int[arr1.length];
for(int i = 0; i < arr1.length; i++) {
    arr2[i] = arr1[i];
}

---

数组的反转

将数组中的元素值进行反转，第一个元素变成最后一个

常见方法：

int arr[] = {11, 22, 33, 44, 55, 66};
int length = arr.length;
int temp = 0;
for(int i = 0; i < length / 2; i++) {
    temp = arr[length - 1 - i];  // 使用临时变量进行保存
    arr[arr.length - 1 - i] = arr[i];
    arr[i] = temp;
}

逆序遍历：创建一个相等大小的新数组，逆序遍历，顺序拷贝，最后将原数组进行指向（原数组就会被垃圾回收）

int arr[] = {11, 22, 33, 44, 55, 66};
int arr2[] = new int[arr.length];
for(int i = arr.length - 1; i >= 0; i--) {
    arr2[arr2.length - i] = arr[i]; 
}
arr = arr2;

---

数组的扩容

数组的扩容也叫数组的添加，可以实现动态的给数组添加元素，实现对数组的扩容

我们需要定义一个新的数组，其数组的大小是原先数组大小加一，将原数组的数组值依次进行拷贝，最后一个数组值存放新的内容，最后将原数组进行指向这个新的数组：

int arr[] = {1, 2, 3};
int arr2[] = new int[arr.length + 1];
for(int i = 0; i < arr.length; i++) {
    arr2[i] = arr[i];
}
arr2[arr2.lengh - 1] = 4;
arr = arr2;

数组的缩减和数组的扩容思路类似

---

排序

排序是将多个数据，依指定的顺序进行排序的过程

排序的分类：

• 内部排序：将需要处理的所有数据都加载到内部存储器中进行排序，包括：交换式排序法、选择式排序法和插入式排序法
• 外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序，包括：合并排序法和直接合并排序法

冒泡排序法

通过对待排序序列从前向后（从下标小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒

有多少个元素，就进行了几轮的排序（可以看成是外层循环），每一轮排序会确定一个数的位置（如第一轮排序确定最大数，第二轮排序确定第二大的数）

当进行比较时，如果发现前面的数大于后面的数，就交换两个数的位置

每一轮的比较在逐渐减小（因为每一轮比较的数据量在减小）

代码实现：

int arr[] = {24, 69, 80, 57, 13};
int temp = 0;
for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j <  arr.length - 1 - i; j++) {
        if(arr[j] > arr[j + 1]) {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
    System.out.println("\n==第" + (i + 1) + "轮排序==");
    for(int j = 0; j < arr.length; j++) {
        System.out.print(arr[j] + "\t");
    }
}

---

查找

在java中，常见的查找方式有两种：

1. 顺序查找：先和第一个元素进行比较，如果不匹配，再和下一个元素进行比较，如果找到了，就将结果返回即可
2. 二分查找：对一个排列从小到大的有序数组进行查找，先查找中间这个数，如果匹配就返回，如果不匹配，就和中间这个数进行判断大小，如果要查找的数组比中间这个数大，就往右边（后面）查找，依次二分类推

---

二维数组

对于一维数组中的每一个元素，如果这个元素还是一个数组，我们将这个数组称为二维数组

动态初始化：类型[][] 数组名 = new 类型[大小][大小]; 如：int a[][] = new int[2][3];

第一个大小表示包含几个一维数组；第二个大小表示一维数组中包含几个元素

定义二维数组（静态初始化）：数据类型 数组名[][] = {一维数组, 一维数组}; 其中[][]可以写在数据类型的后面，二维数组的每一个元素都是一个一维数组，二维数组中只能放一维数组，不能放其他基本类型的数据

输出二维数组：

int arr[][] = {{1, 2}, {2, 3}};
for(int i = 0; i < arr.length; i++) {   // 统计多少个一维数组
    // 遍历二维数组的每个元素
    // arr[i]表示二维数组的第i个元素
    // arr[i].length表示得到对应的一维数组的长度
    for(int j = 0; j < arr[i].length; j++) {
        System.out.print(arr[i][j]);
    } 
    System.out.println();  // 换行
}

对于二维数组，如果要访问第(i+1)个元素的第(j+1)个值，我们应该这样访问：arr[i][j]

二维数组在内存中的存在形式：（重要）

二维数组在栈中，通过一个地址指向堆中的一个空间，该空间中存放的还是地址，用于被一维数组进行指向，一维数组通过地址指向堆中的另一个空间，这个空间中存放具体的值

二维数组动态初始化--列数不确定方式：在Java中允许二维数组中的一维数组的长度可以不相同

创建如下方式的二维数组：（一共有三个一维数组，每个一维数组的长度不一致）

int[][] arr = new int [3][];  // 创建了二维数组，一共有3个一维数组，但是列数不确定
for(int i = 0; i < arr.length; i++) {   // 遍历arr每个一维数组
    // 给每个一维数组开辟空间，如果没有给一维数组new，那么arr[i]就是null
    arr[i] = new int[i + 1];
    
    // 遍历一维数组，并给一维数组的每个元素赋值
    for(int j = 0; j < arr[i].length; j++) {
        arr[i][j] = i + 1;   // 赋值
    }
}

输出10行的杨辉三角：

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

注意事项：

• 对于二维数组的声明方式，有以下几种合法的方法：int[][] arr、int[] arr[]和int arr[][]
• 二维数组的本质是由多个一维数组构成的，它的各个一维数组的长度可以相同，也可以不相同