JAVA学习第八天之数组

学习目的

掌握数组的概念
掌握一维数组和二维数组的定义、初始化、赋值及循环遍历
掌握数组的常用方法（复制和扩容）
掌握基本算法的原理和使用（冒泡排序、选择排序、二分查找）
了解Arrays工具类的使用和常用方法

一.数组

概念
数组是一组数据的集合，是java提供的除了单个元素以外，可以存储多个元素的集合。数组本身是一种引用数据类型，但数组中元素类型可以是基本类型，也可以是引用类型。但同一个数组只能存储同一种类型，一个数组内不能同时存储基本数据类型和引用数据类型。
特点

数组本身作为对象<存储在堆内存中>，而元素则作为数组对象的属性；
数组的长度在数组对象创建声明后立即确定，过后无法再修改；
数组中的元素根据下标来标识，第一个元素从 0 开始，类推到最后一个元素的下标为 n-1，可通过下标来访问数组元素。

用途

多元素的一个容器，一次可以存储多个元素；
作为方法的形式参数，当一个方法的形式参数是一个数组时，可以传递进来一个数组对象。

1.1 一维数组

定义
一维数组是指数组中存储的是一个单一的元素，每个元素类型相同，且都只带有一个下标。其本质上是一组相同类型数据的线性集合。
一维数组声明
<不建议立即声明数组长度[int]>

推荐：数组元素类型[] 变量名 = new 数组元素类型[数组元素个数]；
数组元素类型变量名[] = new 数组元素类型[数组元素个数]。

       int[] i = {1,34,5,7,9,369};
//静态初始化-第一种数组定义格式：推荐
       int[] j = new int[5];
        j[0] = 2;
        j[1] = 4;
        j[2] = 6;
        j[3] = 8;
        j[4] = 10;

//静态初始化-第二种数组定义格式：不推荐
        int j[] = new int[5];
        j[0] = 2;
        j[1] = 4;
        j[2] = 6;
        j[3] = 8;
        j[4] = 10;
//一次定义多个数组
        int[] a, b, c;

数组赋值图解

一维数组赋值的内存显示.png

1.1.1 基本数据类型一维数组

概念
基本类型数组的元素只能是统一的基本数据类型，int类型数组只能存int元素，double类型数组只能存double元素。
数组定义格式
基本数据类型[] 变量名称 = {基本元素 1，基本元素 2,...基本元素 n}

//静态初始化-第一种数组定义格式：推荐
        int[] i = {1,2,3,4,5};

基本数据类型一维数组图解

基本数据类型的一维数组内存模型.png

1.1.2 引用数据类型一维数组

引用类型数组的元素只能是统一的引用数据类型，String类型数组只能存String元素，Person类型数组只能存Person元素，Animal类型数组只能存Animal元素。

数组定义格式
引用数据类型类型变量名称[] = {引用元素 1，引用元素 2,...引用元素 n}

        //静态初始化引用类型数组，推荐该方式
        String[] s1 = {"张三","李四","王五","赵六","钱七"};
        //定义动态初始化数组，不推荐一开始就限定数组长度        
        String s3[] = new String[5];
        //动态初始化引用类型数组（同上）
        Person[] p = new Person[5];
        for (int m = 0;m<p.length;m++){
            Person ps = new Person();
            p[m] = ps;
            System.out.println(p[m].hashCode());
        }

引用数据类型一维数组图解

引用数据类型的一维数组内存模型.png

1.1.3 数组初始化

定义
在定义数组时，若不对数组中元素手动赋值初始化，系统为该类型的每个元素赋对应数据类型的默认值。
静态赋值
在创建数组对象的时候直接赋值，<静态初始化在编译阶段进行，能减少运行时间>。
动态赋值
先创建声明一个数组，后续根据元素下标再逐个赋值，<动态初始化在运行时进行>。
引用数据类型赋值
对于引用数据类型的数组，数组元素为对象内存地址。因此赋予数组元素的值也是对象，不是赋予对象的属性。
若没有对引用数据类型的数组手动赋值，系统默认引用类型元素的初始值为null，访问该数组元素时会引发空指针异常。
引用类型数组赋值图解

引用数据类型数组赋值.png

1.1.4 数组与多态

概念
一个元素类型定义为父类型的数组，实际存入数组的元素可以为子类型。但若要使用到子类型的方法时，需要使用instanceof符号进行类型转换。
代码示例

public static void main(String[] args) {
        // 创建一个Animal类型的数组
        Animal a1 = new Animal();
        Animal a2 = new Animal();
        Animal[] animals = {a1, a2};
        // 对Animal数组进行遍历
        for (int i = 0; i < animals.length; i++) {
            animals[i].move(); // 此处的move()方法是数组当中Animal父类的move()方法
        }

        // 动态初始化一个长度为3的Animal类型数组
        Animal[] ans = new Animal[3];
        ans[0] = new Animal();// Animal数组中存放父类对象
        ans[1] = new Cat(); // Animal数组中存放子类Cat
       ans[2]= new Bird(); // Animal数组中存放子类Bird
        for (int i = 0; i < anis.length; i++){
            // 对取出来的对象进行向下转型，以调用子类重写后的方法
            if(anis[i] instanceof Cat){
                Cat cat = (Cat)anis[i];
                cat.catchMouse();
            }else if(anis[i] instanceof Bird){
                Bird bird = (Bird)anis[i];
                bird.sing();
            }
        }
}

class Animal{
    public void move(){
        System.out.println("Animal move...");
    }
}
// Cat子类
class Cat extends Animal {
    public void move(){
        System.out.println("猫在走猫步！");
    }
    public void catchMouse(){
        System.out.println("猫抓老鼠！");
    }
}
// Bird子类
class Bird extends Animal {
    public void move(){
        System.out.println("Bird Fly!!!");
    }
    public void sing(){
        System.out.println("鸟儿在歌唱！！！");
    }
}

1.1.5 数组扩容

概念
数组从一开始定义时，就已经限定了数组的长度，容量不再变。当业务需求改变，需要存储更多的数据元素时，旧数组已经容纳不下，因此要进行数组扩容。
做法

新建一个大容量的数组，
将原数组中的数据一个一个拷贝到大数组当中。
从旧数组的指定下标开始，拷贝指定长度的元素，到新数组指定的下标开始，粘贴拷贝过来的元素。

关键
调用System类中的arraycopy(Object src, int srcPos, Object dest, int destPos,int length)方法。

Object src：旧数组对象
int srcPos：旧数组下标
Object dest：新数组对象
int destPos：新数组下标
int length：拷贝长度

数组扩容内存图解

数组扩容的内存模型分析.png
代码示例

public static void main(String[] args) {
        // java数组拷贝原理：arraycopy(旧数组，旧数组下标，新数组，新数组下标，拷贝长度)
        //System.arraycopy(Object src,  int srcPos, Object dest, int destPos,int length);

        // 拷贝源（旧数组）
        int[] src = {1, 11, 22, 3, 4};
        // 拷贝目标（新数组）
        int[] dest = new int[20]; 
        System.arraycopy(src, 1, dest, 3, 2);//从旧的下标1开始，拷贝到新的下标3下，长度为2
        System.arraycopy(src, 0, dest, 0, src.length); //拷贝全部元素
        for (int i = 0; i < dest.length; i++) {
            System.out.println(dest[i]);
        }
        // 引用数据类型数组的拷贝
        String[] strs = {"hello", "world!", "java", "oracle", "mysql", "jdbc"};
        String[] newStrs = new String[20];
        System.arraycopy(strs, 0, newStrs, 0, strs.length);
        for (int i = 0; i < newStrs.length; i++) {
            System.out.println(newStrs[i]);
        }
        //拷贝对象类型数组：存储的对象内存地址，拷贝的也是对象内存地址        
        Object[] objs = {new Object(), new Object(), new Object()};
        Object[] newObjs = new Object[5];
        System.arraycopy(objs, 0, newObjs, 0, objs.length);
        for (int i = 0; i < newObjs.length; i++) {
            System.out.println(newObjs[i]);
        }
    }

注意点

数组扩容效率较低：数组扩容涉及到拷贝问题，在以后的开发中应尽可能少的进行数组拷贝；
在创建数组对象时预估长度：预估准确数组定义的长度，可以减少数组的扩容次数，提高开发效率。

1.2 string[] args数组

概念
在最常使用main方法中，main方法的参数列表也是一个数组，且是String类型数组。main方法虽然是由开发者编写，由jvm自动执行的一个方法，但main方法的参数数组args是由开发者编写的调用程序传入的。
位置
程序的主方法入口，main()方法的形式参数列表。
经典代码示例

//模拟系统登录：使用main方法参数列表接收控制台输入的用户名和密码，并完成判断
public class ArrayTest06 {
    public static void main(String[] args) {
        // 输入参数必须为 2个，用户名和密码
        if(args.length != 2){
            System.out.println("请输入用户信息参数，参数包括用户名和密码");
            return;
        }
        // 获取参数列表中的用户名和密码，判断是否正确
        String username = args[0]; // 取出用户名
        String password = args[1]; // 取出密码
        // 假设用户名是admin，密码是123表示登录成功
        //if(username.equals("admin") && password.equals("123")){ // 易出现空指针异常。
        // 采用以下编码风格避免出现空指针异常（老程序员的一条编程经验）
        if("admin".equals(username) && "123".equals(password)){
            System.out.println("登录成功，欢迎[" + username + "]回来");
            System.out.println("欢迎您使用该系统....");
        }else{
            System.out.println("验证失败，用户名不存在或者密码错误！");
        }
    }
}

1.3 二维数组

定义
二维数组是指数组中的每个元素都是一个一维数组，本质是以数组作为元素的数组。二维数组的使用类似于直角坐标系，通过坐标可以获得指定元素。
二维数组声明

数组元素数据类型[][] 变量名 = new 数组元素数据类型[][]；
数组元素数据类型变量名[][] = = new 数组元素数据类型[][]；

//定义二维数组，推荐该方式
int[][] data = new int[][];

//c++定义二维数组，不推荐
int   data[][]  =  new  int[2][3];//定义一个2行，3列的二维数组

二维数组初始化
静态初始化：int[][] data = {{元素1,元素2},{元素1,元素2,元素3,元素4}};

//初始化一维数组
        int[] a = {1,2,4,45,6,68,3};
        int[] b = {9,2,44,56,68,3,23};
        int[] c = {8,2,4,7,2,435,7,68};

        //静态初始化二维数组
        int[][] data = {{1,2,3,},{11,22,33},{1,2,4,8},{3,6,9,0}};
        //二维数组的元素可以直接赋值"一维数组对象"
        int[][] nm = {a,b,c};

二维数组的遍历（分两步）

先获取"行"：即先获取二位数组的元素--一维数组，每一个一维数组本身作为一行；
获取"列"：获取得到每一个一维数组后，开始遍历一维数组的元素，每一个一维数组元素就是一列；

        //定义一个具有三个元素的二维数组
        int[][] nm = {{1,3,5},{2,4,6},{7,8,9}};
        for (int i = 0;i<nm.length;i++){    //外层获得元素是每一个一维数组
            for (int j=0;j<nm[i].length;j++){   //内层从每一个一维数组中获取元素
                System.out.println(nm[i][j]);//i=第几个一维数组，j=第i个一维数组中的第j个元素
            }
        }

1.3 多维数组

定义
多维数组指的是数组中的每一个元素都是二维数组。
分类

一维数组：数组元素为普通数据类型
二维数组：数组元素为一维数组
三维数组：数组元素为二维数组

二. 数组和算法

算法概念
如何将文字描述转换为有效率、高效率的代码输出。

2.1 冒泡排序（重点）

算法要求
对于一个无序的数组，要求按从小到大排序输出。
实质
利用水中相邻泡泡比较的原理，最大气泡最先升出水面。冒泡算法从数组最小下标开始，每次比较下标 n 和 n+1两个元素，若大小不相等则交换位置，继续比较n+1和n+2下标的元素。每一轮升出一个最大元素排最后，每下一轮减少一个元素进行比较。
特点

一个数组有几个元素a.length，就比较 a.length-1轮；
每一轮比较几次，就交换几次位置；
保证每一轮比较都有一个数移到最右边（最后面），每下一轮可以减少一个元素的比较。

实现原理

先根据数组的长度，获取总的排序轮数 = 数组.length - 1；
根据每一轮的最大下标，确定每一轮比较的次数，比较次数 = 最大的下标数 - 1；
开始每一轮比较，从数组的最左边开始<下标为0开始>，逐个往右比较
取出第 0 号下标的元素和第 1号下标的元素比较
如果0 号数据大于1号数据则进行交换，否则不进行交换
在第一次比较交换了数据后的基础上
取出1号下标元素和 2号下标元素，重复；
取出2号下标元素和 3号下标元素，重复；
取出3号下标元素和 4号下标元素，重复；
取出n-1号下标元素和 n号下标元素，重复；
每完成一轮比较，可以确定一个最大的数排到最右边，下一轮的比较则较少一个数；
开始下一轮，最大下标 -1，比较次数-1；
重复以上步骤。

图解

冒泡排序.png
代码实现

int[] data = {3,1,6,2,5};
        //先根据数组长度，确定总的比较轮数
        for (int i=data.length-1; i>0; i--) {
            //开始每一轮的比较，第一轮有data.length-1个数，每一轮减少一个
            for (int j=0; j<i; j++) {
            //开始比较，每一次都从下标0开始和相邻下标比较，直到每次的最大下标
            //第一轮最大下标为4，则依次比较下标01，12，23，34
            //第二轮最大下标为3，则依次比较下标0和1，1和2，2和3
            //第三轮最大下标为2，则依次比较下标0和1，1和2
            //第四轮最大下标为1，则依次比较下标0和1
                //若前一个数大于后一个数，两数进行交换
                if (data[j] > data[j+1]) {
                    int temp = data[j];//前面较大值 暂存 到中间变量
                    data[j] = data[j+1];//将后面较小的值赋给前面一个下标
                    data[j+1] = temp;//将暂存的最大值赋给后面一个下标
                }
            }
        }
        //对排序完的数组进行遍历输出
        for (int i=0; i<data.length; i++) {
           System.out.println(data[i]);
        }

2.2 选择排序（重点）

算法要求
对于一个无序的数组，要求按从小到大排序输出。
实质
利用相对固定的第一个位置的元素跟其他位置的所有元素比较，得出最小元素再和第一个位置的元素交换位置。
保证
默认每一轮的比较都从左边"第一个下标"开始，保证了每一轮都有一个最小元素移到最左边，下一轮减少一个元素的比较。
特点
对冒泡排序进行改进，使交换次数减少，但比较次数没有减少<每一轮比较只交换一次位置>。
选择排序原理

先根据数组长度确定总的比较轮数，总轮数 = 数组.length - 1；
每一轮都从左边的下标开始，第一轮下标0开始，第二轮下标1开始，最后一轮数组.length - 1开始比较最后两个数；
定义初始下标：存储每一轮从相对最左端开始的下标
将下标为 0 的元素和下标为1，2，3，4的元素依次比较
如果找到比初始下标小的元素，将该元素下标赋给初始下标
然后按当前最小元素的下标，继续往后依次比较
直到比较完每一轮中所有的元素
若初始下标的元素就是最小值，不需要换位置；若不是，把最小的元素和初始下标元素位置互换；
完成一轮后，初始下标开始+1，初始下标从0到1，1到2，2到3，n-2到n-1，重复以上步骤的比较。

图解

选择排序.png
代码实现

        int[] data = {3,1,6,2,5,4,7};
        //根据数组的长度确定，总的轮数<交换的次数>
        for (int i=0; i<data.length; i++) {
            int min = i;//每一轮比较的初始元素下标，从左边开始
            //每一轮从初始下标与初始下标的下一个元素开始进行比较
            for (int j=i+1; j<data.length; j++) {
             //第一轮，初始元素下标为0，则从下标1元素开始比较；
             //第二轮，初始元素下标为1，则从下标2元素开始比较；
             //第三轮，初始元素下标为2，则从下标3元素开始比较；
             //第n-1轮，初始元素下标为n-2，则从下标n-1元素开始比较
                //若初始下标元素大于比较的元素，则互换下标，继续往下比较
                if (data[j] < data[min]) {
                    min = j;//互换较小元素的 下标，继而往下比较
                }
            }
            //每完成一轮比较，进行最小元素位置的交换
            //若初始下标就是最小下标，则不用交换
            if (min != i) {
                int temp = data[i];//将每一轮最小元素 赋给 中间量暂存
                data[i] = data[min];//将初始位置的元素 互换到本轮最小元素位置
                data[min] = temp;//将暂存的最小元素 换到 初始位置中
            }
        }
        //遍历最终排序的数组
        for (int i=0; i<data.length; i++) {
            System.out.println(data[i]);
        }

2.3 二分查找（折半查找）

要求
给定一个已经排序好的数组，查找出符合条件的一个元素。
查找方式
遍历数组中的所有元素，逐个查找。
实质
在一个排序好的数组中，找到期望值的元素下标，并输出。
实现原理

对于一个已经排好序的数组，从数组中查找一个期望值；
先初始化两个变量，数组起始元素的下标为0，数组末位元素的下标为数组.length - 1；
在已排序的数组里循环的二分进行查找；
循环条件：起始下标元素 < 末位下标元素；
执行循环体：定义二分的中间下标 = ( 起始下标 + 末位下标 )/ 2
若中间下标的元素和期望值相等，直接返回中间下标；
若中间下标的元素小于期望值，则从后半段数组中重新查找，且起始下标更新为当前中间下标 + 1，末位下标不变；
若中间下标的元素大于期望值，则从前半段数组中重新查找，且起始下标不变，末位下标更新为当前中间下标 - 1；
若数组中没有这个期望值元素，直接返回 -1。

图解
代码解释

public static void main(String[] args) {
        //定义一个数组，必须有序，才能进行二分查找
        int[] data = {1,3,6,9,11,21,23,24,32,33,34,41};
        //在数组中查找指定元素，返回该元素下标
        int index = binarySearch(data, 18);
        System.out.println(index);//找不到目标值18，返回-1

        int index2 = binarySearch(data,11);
        System.out.println(index2);//输出目标值下标为：4

        int index3 = binarySearch(data,33);
        System.out.println(index3);//输出目标值下标为：9
    }

    private static int binarySearch(int[] data, int i) {
        //定义每一次二分的初始下标，下标从0开始
        int begin = 0;
        //定义每一次二分的末位下标，最开始是数组的长度-1
        int end = data.length - 1;

        //判断数组是否有序：起始下标和末位下标的元素大小
        //不能用if控制语句，二分查找是循环、不断取2的过程，要用while
        while(data[begin] <= data[end]){
            //定义中间元素的下标：中间 =（起始+末位）/2         
            int mid = (begin + end)/2;
            //根据中间下标的元素值 和 目标值匹配
            if (data[mid] == i){
                return mid;
            }else if (data[mid] >= i){
                //中间元素值 大于 目标值，下一次二分从前半段中查找
                //前半段初始下标不变，结束下标为中间下标-1
                end = mid - 1;
            }else if (data[mid] <= i){
                //中间元素值 小于 目标值，下一次二分从后半段中查找
                //前半段的末位下标不变，初始下标为中间下标+1
                begin = mid + 1;
            }
        }
        //执行到这里，说明以上找不到目标值，返回-1 表示查找失败
        return -1;
    }

2.4 快速排序

原理
图解
代码解释

2.5 Arrays工具类

概念
Arrays类是java提供的用来操作数组的各种方法的工具类。在该类中提供了排序和搜索数组的方法，在这些方法的底层已经封装好了算法实现。不需要开发者自己编写。Arrays类还包含一个允许将数组作为列表来查看的静态工厂。
常用方法

void sort(数组名)：Arrays工具类封装好的排序方法，调用该方法时，直接传递进入一个数组即可对该无序数组进行排序；
int binarySearch(数组名, 期望值)：Arrays工具类封装好的二分查找方法，调用该方法时，直接传递进入一个数组和期望值即可，返回期望值的下标。

常见面试题

描述一下equals() 方法和 hashcode() 方法的关系？
答：

两个对象hashCode()相等，对象不一定相等；
两个对象 equals 相等，那么它们的 hashcode 一定相等。
两个对象 equals 不相等，那么它们的 hashcode 并不要求不相等<一般建议不相等>；
对象在堆内存中是存储在HashSet或HashMap中的，HashSet底层采用的是数组 + 单向链表组合存储，数组中的每一个元素都是单向链表。每一个对象都是存储在数组中，而对象调用hashCode()方法得到的哈希地址--经过哈希算法的运算，最终得到对象在数组中的下标。
但是由于每一个数组下标上的元素都是单向链表，因此该位置上存在多个元素，该位置链表上的元素hashCode()都相同，但对象不一定相同。还需要比较对象的每一个属性值，也就是需要使用 equals(）方法。
当两个对象hashCode()不相同时，认为两个对象在数组中的下标不一样，因此两个对象也不同。

使用数组模拟栈数据结构？

/*使用一维数组，模拟栈数据结构：
        1、这个栈可以存储java中的任何引用类型的数据。
        2、栈中提供push方法模拟压栈（栈满要有提示信息）
        3、栈中提供pop方法模拟弹栈（栈空也有提示信息）
        4、编写测试程序，new栈对象，调用push pop方法来模拟压栈弹栈的动作。
        5、假设栈的默认初始化容量是100
    思路：
        1、定义一个一维数组，有一个栈顶元素永远指向数组第一个下标（数组未有数据时，初始化下标是-1，栈顶元素也为-1）
        2、push压栈就是给一维数组添加一个元素(传入参数)，下标往上加一，栈顶元素指向增加后的下标
        3、pop弹栈相当于给一维数组删除一个元素，实际只是栈顶元素往下移动，下标往下减一
        4、无论压栈、弹栈都要先判断该数组空间是否能已满，或者是否还有元素可以弹出
 */
public class Stack{
    //Object[] ojbs = new Object[100];
    //定义一个可以存储任何数据类型的一维数组    
    Object[] ojbs;
    //栈帧：永远指向栈顶部元素，最初栈为空
    //private int index = 0; // index==0，表示栈帧指向顶部元素上方
    //private int index = -1; // index==-1，表示栈帧指向顶部元素
    int index;//栈顶元素

    public Stack() {
        this.ojbs= new Object[10];//初始化数组的容量
        index = -1;//初始化栈帧，并让栈帧指向栈顶元素(-1表示栈一开始为空)
    }
    public Stack(Object[] ojbs){
        this.ojbs = ojbs;
    }

    public Object[] getOjbs() {
        return ojbs;
    }
    public void setOjbs(Object[] ojbs) {
        this.ojbs = ojbs;
    }
    public int getIndex() {
        return index;
    }
    public void setIndex(int index) {
        this.index = index;
    }

    //压栈--往数组中添加元素
    public void push(Object obj){
        if(index >= ojbs.length-1){  //下标永远小于等于数组长度-1
            System.out.println("栈已满，不能再添加啦!");
            return;
        }
        //栈未满，可以压栈。index初始=-1指向栈顶元素，压入数据时，index自增+1；
        index++;//index由-1变成0，元素可以压入
        ojbs[index] = obj;//将压入元素赋给栈顶下标
        System.out.println(obj +"压栈元素成功，栈帧指向:" + index);
    }

    //出栈不是删除元素，只是栈顶元素(下标)往下移动，下标改变代表删除
    public void pop(){
        //if (ojbs.length<0){ //ojbs.length表示数组的长度，出栈不是删除数组，因此长度不会小于0
        if (index < 0){
            System.out.println("栈已空，无法继续删除啦！");
            return;
        }
        //栈未空，有元素可以继续删除
        System.out.print(ojbs[index] + "出栈成功啦！");//先出栈
        index--;//栈顶元素自减1
        System.out.println("栈帧指向：" + index);
    }
}

//测试
public static void main(String[] args) {
        //创造一个栈对象，初始化数组容量为100，栈顶元素为-1
        Stack st = new Stack();
        //调用push()，测试压栈
        st.push(new Object());//java.lang.Object@4554617c压栈元素成功，栈帧指向:0
        ...//此处重复压栈8次
        st.push(new Object());//java.lang.Object@330bedb4压栈元素成功，栈帧指向:9
        //数组初始容量只有10，超过10不能再压栈
        st.push(new Object());//栈已满，不能再添加啦!

        //调用pop()，测试出栈
        st.pop();//java.lang.Object@330bedb4出栈成功啦！栈帧指向：8
        ...//此处重复出栈8次
        st.pop();//栈已空，无法继续删除啦！
    }