Java基础-数组

前两篇介绍了Java的数据类型和流程控制，现在来讲一下Java的数组，作为一种引用类型，也是非常常见和常用的。这次的知识框架如下所示。

一、声明

Java在创建变量前必须先声明变量，而数组作为一种引用类型的变量，在创建数组变量前也必须要先声明数组变量，才能在程序中使用数组。声明格式如下。

1 2	int[] arr; // 数组元素类型[] 数组名; // 推荐 int arr[]; // 数组元素类型数组名[]; // 不推荐

二、创建（初始化）

数组的初始化可以分为静态初始化和动态初始化两种。

1、静态初始化

静态初始化即在数组创建的同时为数组赋好值。
1）写法1：在堆空间开辟（new）一块内存区域来存储数组的元素，并将该内存区域的地址值赋值给该数组的引用变量 arr（引用）

1 2	// 数组元素类型[] 数组名 = new 数组元素类型[] {元素 1, 元素 2, ...}; int[] arr = new int[] {1, 2, 3};

2）写法2：简洁，必须声明的同时作初始化。

1 2	// 数组元素类型[] 数组名 = {元素 1, 元素 2, ...}; int[] arr = {1, 2, 3};

2、动态初始化

动态初始化分配给定空间的数组大小（数组长度确定）。

1 2	// 数组元素类型[] 数组名 = new 数组元素类型[length]; int[] arr = new int[3]; // [0, 0, 0]

3、几点注意

1）数组是定长的：一旦初始化完成，数组的长度就固定了，不能更改，除非重新做初始化。
2）数组是引用数据类型，可以赋值为 null，表示没有引用任何内存空间。
3）new 关键字：在堆空间开辟一块内存区域，用来存储数据。

操作数组常见异常：

1）NullPointerException：空指针异常（没有引用地址值）。
2）ArrayIndexOutOfBoundsException：数组的索引越界异常。

三、相关操作

1、访问

访问数组元素非常简单，即 **数组变量[索引值]**，重新赋值也可以实现更改数组元素。还有一个是 length属性可以求得数组长度。eg：

public class Test {
    public static void main(String[] args) {
        int[] arr = {4, 2, 3}; // 静态初始化
        int len = arr.length;  // 数组长度，索引范围 [0, arr.length - 1]
        int num = arr[0];      // 访问
        arr[0] = 1;            // 修改 
        System.out.println(num);    // 4
        System.out.println(arr[0]); // 1
        System.out.println(len);    // 3
    }
}

2、遍历

数组的遍历即逐个输出数组元素的过程。

2.1 普通 for 循环

可以直接使用 for循环输出数组元素。如下：

public class Test {
    public static void main(String[] args) {
        int[] arr = {4, 2, 3}; // 静态初始化
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

2.2 for-each(增强 for循环)

for-each 是 JDK 1.5 引进了一种新的循环类型，可以在不使用索引（下标）的情况下遍历数组。
eg：以下列举3类数组元素类型，注意 for里面要加上对应的元素类型，ele任意命名（相当于 for循环里面的 i），冒号后面跟的是数组名。
1）数组元素为整数类型

public class Test {
    public static void main(String[] args) {
        int[] arr = {4, 2, 3}; // 静态初始化
        for (int ele : arr) {
            System.out.println(ele);
        }
    }
}

2）数组元素为字符类型

public class Test {
    public static void main(String[] args) {
        char[] arr = {'a', 'b', 'c'}; // 静态初始化
        for (char ele : arr) {
            System.out.println(ele);
        }
    }
}

3）数组元素为String类型

public class Test {
    public static void main(String[] args) {
        String[] name = {"zhangsan", "lishi", "wangwu"}; // 静态初始化
        for (String n : name) {
            System.out.println(n);
        }
    }
}

虽然 for-each循环比较好用，但也要注意以下几点：

1）只能访问数组元素，不能赋值，在不关心数组的索引时使用（因为它不需要使用索引）
2）当数组元素是引用类型（数组类型）时，不建议使用（需要先知道值不为 null 的元素个数）。

3、常见数组算法

这里列举几个与数组相关的算法，包括两个排序和一个查找。

3.1 冒泡排序

1）基本原理
冒泡排序（Bubble Sort）通过重复地走访过要排序的数列，一次比较两个元素，若顺序（从小到大/从大到小）错误就把他们交换过来，直到不需要交换为止（排序完成）。顾名思义，该算法名字的由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序的平均时间复杂度 O(n^2)，空间复杂度 O(1)。关键字相同的元素在排序之后相对位置不变，所以是稳定的（自行验证）。

2）过程演示

对未排序的各元素从头到尾依次比较相邻的两个元素 arr[i]、arr[i + 1]，共要进行 arr.length -1 轮比较。

3）代码实现

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] nums = {5,8,4,3,6,1};
        bubbleSort(nums);
        System.out.println("冒泡排序完的数组："+ Arrays.toString(nums));

    }
    static void bubbleSort(int[] arr) {
        for (int times = 1; times <= arr.length - 1; times++) {
            for (int i = 0; i <= arr.length - times - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    // 交换
                    arr[i] = arr[i] ^ arr[i + 1];
                    arr[i + 1] = arr[i] ^ arr[i + 1];
                    arr[i] = arr[i] ^ arr[i + 1];
                }
            }
            System.out.println("第"+times+"趟："+Arrays.toString(arr));
        }
    }
}

Arrays.toString()方法：用于将数组转换成一个字符串，括在方括号（”[]”）中，相邻元素用字符 “, “（逗号加空格）分隔。

3.2 选择排序

1）基本原理
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

选择排序平均时间复杂度 O(n^2)，空间复杂度 O(1)，不稳定。

2）过程演示

3）代码实现

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] nums = {5,8,4,3,6,1};
        selectionSort(nums);
        System.out.println("选择排序完的数组："+ Arrays.toString(nums));

    }
    static void selectionSort(int[] arr) {  // 选择排序
        for (int i = 0; i <= arr.length - 2; i++) {
            for (int j = i + 1; j <= arr.length - 1; j++) {
                if (arr[i] > arr[j]) {
                    // 交换
                    arr[i] = arr[i] ^ arr[j];
                    arr[j] = arr[i] ^ arr[j];
                    arr[i] = arr[i] ^ arr[j];
                }
            }
            System.out.println("第"+(i+1)+"趟："+Arrays.toString(arr));
        }
    }
}

3.3 二分查找（折半查找）

1）基本原理
二分查找，也称折半查找，是一种在有序数组中查找目标元素的算法。它的原理是不断将查找范围减半，直到找到目标元素或确定目标元素不存在。

pass：二分查找的前提是数组已经排好序

2）代码实现

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] nums = {5,8,4,3,6,1};
        int target = 5; // 查找目标元素
        Arrays.sort(nums);  // 二分查找的前提是数组必须有序
        System.out.println("排序后的数组为：" + Arrays.toString(nums));
        System.out.println("目标元素" + target + "的下标为：" + binarySearch(nums,target));

    }
    static int binarySearch(int[] arr, int key) {   // 二分查找
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (arr[mid] < key) {
                low = mid + 1;
            } else if (arr[mid] > key) {
                high = mid - 1;
            } else {
                while (mid - 1 >= 0 && arr[mid -1] == key) {
                    mid--;
                }
                return mid;
            }
        }
        return -1;
    }
}

4、Arrays工具类（重点）

java.util.Arrays 类能方便地操作数组，它提供的所有方法都是静态的。

4.1 常用方法汇总

1、 String toString(Object[] arr)：将 a 数组转换成一个字符串，括在方括号（”[]”）中，相邻元素用字符 “, “（逗号加空格）分隔。
2、 void sort(Object[] a)：根据元素的自然顺序对指定对象数组按升序进行排序，数组中的所有元素都必须实现 Comparable 接口。
3、 void parallelSort(Object[] a)：以并发的方式对 a 数组的数组元素进行排序。
4、 type binarySearch(Object[] a, type key)：使用二分法査询 key 元素值在 a 数组中出现的索引，如果 a 数组不包含 key 元素值，则返回 -(low + 1)（调用该方法时要求数组中元素已经按升序排列）。
5、 boolean equals(Object[] a, Object[] a2)：如果 a 数组和 a2 数组的长度相等，且 a 数组和 a2 数组的数组元素也对应相同，该方法将返回 true。
6、void fill(int[] a, int val)：将指定的 int 值分配给指定 int 型数组指定范围中的每个元素。同样的方法适用于所有的其他基本数据类型（Byte，short，Int等）。
7、 Object[] copyOf(Object[] original, int newLength)：复制 original 数组，截取或用 0（数值类型）、false（布尔类型）或者 null（引用类型）填充，以使新数组的长度为 newLength。

4.2 以上方法对应的代码实现

import java.util.Arrays;

public class Test {
    public static void main(String[] args){
        int[] arr1={1,3,6,7,9};
        int[] arr2={3,6,1,7,9};
        System.out.println(Arrays.toString(arr1));  //1.数组与字符串的相互转换 [1, 3, 6, 7, 9]
        Arrays.sort(arr2);  //2.排序后arr2为: 1,3,6,7,9
        System.out.println(Arrays.equals(arr1,arr2)); //3.数组比较，true

        Arrays.fill(arr1,9);    //4.fill方法给数组赋值
        for (int i:arr1){   // 遍历查看赋值结果
            System.out.println(i);  // 5个9
        }
        System.out.println("-------");
        int[] newarr=Arrays.copyOf(arr1,4); //5.数组复制,截取指定长度
        for(int i:newarr){
            System.out.println(i);  // 4个9
        }
        System.out.println("-------");
        Arrays.sort(arr2);  //查找时先排序，排序后arr2为：1,3,6,7,9
        int index=Arrays.binarySearch(arr2,6); //6.查找元素6在arr2的位置
        System.out.println(index);  //2
    }
}

注：使用前要先导入java.util.Arrays工具类，才能调用类中的方法。调用格式为：Arrays.要用的方法。

pass：Arrays工具类里面的方法还有很多，但较为常用的就是这些，其他的方法有兴趣的可以自行去了解。

四、二维数组

本质还是一维数组，只不过数组元素是引用类型（数组类型），数组元素里保存的引用指向一维数组。

1、初始化

1.1 静态初始化

1 2	int[][] arr = new int[][] { {1, 2, 3}, {4, 5}, {6} }; int[][] arr = { {1, 2, 3}, {4, 5}, {6} };

1.2 动态初始化

1 2	int[][] arr = new int[3][]; // 即 int[][] arr = {null, null, null}; int[][] arr = new int[3][4];

1.3 关于数组长度

arr.length 为外层数组的长度，arr[i].length 为内层数组的长度。

2、遍历

依葫芦画瓢，注意与一维的区别。

2.1 普通 for循环

public class Test {
    public static void main(String[] args){
        int[][] arr = { {1, 2, 3}, {4, 5}, {6} };
        for (int i = 0; i < arr.length; i++) {  // arr.length，外层数组的长度
            for (int j = 0; j < arr[i].length; j++) {   // arr[i].length，内层数组的长度
                System.out.println(arr[i][j]);
            }
        }
    }
}

2.2 增强 for 循环（for-each）

public class Test {
    public static void main(String[] args){
        int[][] arr = { {1, 2, 3}, {4, 5}, {6} };
        for (int[] outerArr : arr) {    // 注意这里与一维的区别
            for (int oa : outerArr)
                System.out.println(oa);
        }
    }
}