[数据结构与算法]【JavaSE系列】第六话 —— 数组

?目录?

?🍔前言

?🍚一、思维导图

?🥞二、数组的基本概念

? ? ? ? ? ? 🍟🍟2.1 为什么要使用数组

? ? ? ? ? ? 🥩🥩2.2 什么是数组

? ? ? ? ? ? 🥛🥛2.3 数组的创建及初始化

? ? ? ? ? ? ? ? ? ? 🍍🍍🍍2.3.1 数组的定义

? ? ? ? ? ? 🍞🍞2.4 数组的使用

? ? ? ? ? ? ? ? ? ? 🌭🌭🌭2.4.1?数组中元素访问

? ? ? ? ? ? ? ? ? ? 🍗🍗🍗2.4.2 数组遍历

?🧀三、数组是引用类型

? ? ? ? ? ? 🧊🧊3.1?初始JVM的内存分布

? ? ? ? ? ? 🍖🍖3.2 认识null

? ? ? ? ? ? 🍕🍕3.3 分析引用变量

? ? ? ? ? ? 🍤🍤3.4 四个小问题

?🍜四、数组的使用方式

? ? ? ? ? ? 🍺🍺4.1 保存数据

? ? ? ? ? ? 🥤🥤4.2 作为函数的参数

? ? ? ? ? ? 🍉🍉4.3 作为函数的返回值

??五、数组练习

? ? ? ? ? ? 🎁🎁5.1 写一个函数myToString，将数组以字符串的形式输出

? ? ? ? ? ? 🏐🏐5.2?数组拷贝

? ? ? ? ? ? 🎩🎩5.3 求一个整型数组的平均值

? ? ? ? ? ? 📓📓5.4 查找数组中指定元素（顺序查找）

? ? ? ? ? ? 🎵🎵5.5?查找数组中指定元素(二分查找)?

? ? ? ? ? ? ??5.6 冒泡排序

? ? ? ? ? ? 📝📝5.7?数组逆序

? ? ? ? ? ? 🍓🍓?5.8 其他?

?🍲六、二维数组

🧇总结

前言

? ? ? ?从数组这一章开始，Java就开始逐渐的和C语言有点区别了。

? ? ? ?因此，大家一定要端起自己的小板凳，认认真真的看完接下来的博客，希望看完博客的都是干货满满哦。

一、思维导图

二、数组的基本概念

2.1 为什么要使用数组

? ? ? ?假如说，我们有这样的一个需求，需要存储10个整型变量的值；

? ? ? ?那么，按照以前的所学知识，我们会定义10个变量；但是，定义10个变量 的数量有一点点多，而且 它们全部都是整型变量。

? ? ? ?为了能够满足 可以存储多种相同类型的变量，于是 便规定了一种新的数据类型：数组。

2.2 什么是数组

数组：可以看成是相同类型元素的一个集合，在内存中是一段连续的空间。

【注意】

1. 数组中存放的元素其类型相同；
2. 数组的空间是连在一起的 ；
3. 每个空间有自己的编号，即数组的下标（从0开始编号，我们可以运用下标 来对数组中的元素进行访问和修改）。

   

2.3 数组的创建及初始化

2.3.1 数组的定义

? ? ? ?在Java中，数组和C语言中的是有着区别的；

? ? ? ?在Java中，int [ ] 是数组的 数据类型，那么我们可以这样来定义数组：

? ? ? ?int [ ] array —> int [ ] 是数据类型，array是 变量。

(1)第一种方式：

int[] array1 = {1,2,3,4,5,6,7,8,9,10}; 

?(2)第二种方式：

int[] array2 = new int[] {1,2,3,4,5,6,7,8,9,10};

?【注意】在前两种定义和初始化的过程中，中括号[ ]当中 不能有任何的数字，否则就会报错；当然，也不必当心编译器会不知道 所定义的数组的长度，编译器会自动推导出来的。

我们可以通过 数组名.length自动获取当前数组的长度：

?(3)定义的第三种方式

int[] array3 = new int[10];

? ? ? ?这一种方式的主要区别与前面两种的是：没有初始化。

? ? ? ?那么我们可以来测试一下 有没有默认值：

?【说明】三种定义方式 可以根据自己的需求，来决定到底用哪一种。但是，平常我们用的最多的是第一种方式（第一种方式 和 第二种方式 其实是一模一样的，但是它更加简便）。

? ? ? ?第一种方式 和 第二种方式 中括号[ ] 里面 是肯定不可以有数字的，

? ? ? ?至于第三种定义方式，肯定是要有数字的，否则它肯定推不了数组的长度（后面都没有赋值）。

?【注意】

? ? ? 如果没有对数组进行初始化，数组中元素有其默认值：

? ? ? ?如果数组中存储元素类型为引用类型，默认值为null 。

数组越界问题：

?

2.4 数组的使用

2.4.1?数组中元素访问

? ? ? ?当然， 访问数组下标的时候，千万不能越界：

2.4.2 数组遍历

第一种打印方式（for 循环）：

第二种打印方式（for-each）：

【注意】冒号 左边和右边的类型要相匹配。?

? ? ? ?普通的for循环和增强for循环的区别：

? ? ? ?普通for循环 可以拿到数组的下标，通过下标对数组进行操作；

? ? ? ?增强for循环 我们只是拿到了变量的值，与下标无关。

?第三种打印方式（借用Java本身提供的一些方法来实现数组的打印）：

? ? ? ?这里首先需要介绍一个 工具类（可以理解为C语言里面的头文件）：Arrays

? ? ? ?其主要作用是：帮助对数组进行一个操作（详情可查找帮助手册）。

?

三、数组是引用类型

3.1?初始JVM的内存分布

? ? ? ?划分内存的好处是：简洁、方便管理。就比如是这样：

? ? ? ?而现在我们只简单关心堆 和 虚拟机栈这两块空间，后序JVM中还会更详细介绍。

? ? ? ?堆(Heap): JVM所管理的最大内存区域。使用 new 创建的对象都是在堆上保存 (例如前面的 new int[]{1, 2, 3} )，堆是随着程序开始运行时而创建，随着程序的退出而销毁，堆中的数据只要还有在使用，就不会被销毁。

? ? ? ?虚拟机栈(JVM Stack): 与方法调用相关的一些信息，每个方法在执行时，都会先创建一个栈帧，栈帧中包含有：局部变量表、操作数栈、动态链接、返回地址以及其他的一些信息，保存的都是与方法执行时相关的一些信息。比如：局部变量。当方法运行结束后，栈帧就被销毁了，即栈帧中保存的数据也被销毁了。

举个例子：

public class TestDemo {
    public static void main(String[] args) {
        int a = 10;//a是局部变量，我们把它放到了Java虚拟机栈 当中
    }
}

我们来看一下定义数组内存分配的情况：

    public static void main(String[] args) {
        
        int[] array = {1,2,3};
        System.out.println(array);
    }

【注意】引用是一个变量，里面存的是地址。

?3.2 认识null

3.3 分析引用变量

分析一：

    public static void main(String[] args) {
        int[] array1 = {1,2,3,4};
        int[] array2 = array1;
        System.out.println("array1:"+Arrays.toString(array1));
        System.out.println("array2:"+Arrays.toString(array2));
    }

? ? ? ? 此时，如果 array2的对象 发生了改变，那么array2的对象也必然会发生改变：

? ? ? ?所以可以得出一个结论：不要说array2引用指向了引用，而是说 这个引用array2 指向了 array1所指向的对象。

?

分析二：

?

3.4 四个小问题

问题一：引用能指向引用吗？

答案：不能，这句说法就是有问题的（引用只能指向对象，引用不能指向引用）。

array1 = array2 代表：array1这个引用 引用了array2所引用的对象。?

问题二：一个引用可以同时指向多个对象吗？

答案：不能，可以不同时指向多个对象，但只能同时指向一个对象（指向另外一个对象的时候，上一次所存储的对象的地址被销毁掉）。

问题三：引用一定是在栈上吗？

答案：不是的，现在之所以把它画在栈上，是因为我们目前只接触到了 局部变量，还没有接触到成员变量；这个成员变量在后面会继续介绍的。?

问题四：引用赋值null代表啥？

答案：int[ ] array = null； 代表整个引用不指向任何对象。?

四、数组的使用方式

4.1 保存数据

    public static void main(String[] args) {
        int[] array = {1,2,3};
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

?

4.2 作为函数的参数

? ? ? ?首先我们需要一个不带数组的简单类型的方法：?

一步一步的来分析：

? ? ? ?首先，在栈上分配了一块内存空间存储 x=10；

? ? ? ?然后，进入func1方法，在栈上又开辟了一块int[ ] 类型的内存，把10赋给a；

? ? ? ?接着，又把20赋值给了a；

? ? ? ?当最终func1方法结束以后，x的值仍然还是10，并没有发生改变；所以打印的还是10，并没有打印20。

接下来我们再来看一下引用类型的方法：

第一种：?

第二种：

【说明】只要new一下，就会开辟一块新的空间，然后数组就会存储一块新的地址。?

4.3 作为函数的返回值

? ? ? ?C语言里面是不能返回数组的；

? ? ? ?但是Java里面可以返回数组，不过返回的都是地址。

【注意】函数回收 只会把 栈上面的内存回收掉。

五、数组练习

5.1 写一个函数myToString，将数组以字符串的形式输出

import java.util.Arrays;

public class TestDemo {
    public static String myToString(int[] array) {
        String str = "[";
        for (int i = 0; i < array.length; i++) {
            str = str + array[i];
            if(i!=array.length-1){
                str+=",";
            }
        }
        str = str + "]";
        return str;
    }
    public static void main(String[] args) {
        int[] array = {1,2,3,4};
        String ret = myToString(array);
        System.out.println(ret);
    }
}

5.2?数组拷贝

第一种拷贝方式：

? ? ? ?使用for循环进行拷贝：

import java.util.Arrays;

public class TestDemo {
    //数组拷贝
    public static void main(String[] args) {
        int[] array = {1,2,3,4};

        int[] copy = new int[array.length];

        for (int i = 0; i < array.length; i++) {
            copy[i] = array[i];
        }
        System.out.println(Arrays.toString(copy));
    }

}

第二种拷贝方式：

? ? ? ?通过Arrays这个类自带的拷贝方法（Arrays.copyOf）：

import java.util.Arrays;

public class TestDemo {
    public static void main(String[] args) {
        int[] array = {1,2,3,4};
        int[] copy = Arrays.copyOf(array,array.length);
        System.out.println(Arrays.toString(copy));
    }
}

这个方法虽然说是拷贝，但也可以理解成扩容：

第三种拷贝方式：

System.arraycopy：

?【说明】src是你要拷贝的数组，srcPos是开始拷贝的下标，dest是目的地数组，destPos是从目的地数组的位置开始拷贝，length是你要拷贝的长度。

至于要取什么值，可以自己去试试看，确实是很有意思的：

import java.util.Arrays;

public class TestDemo {
    public static void main(String[] args) {
        int[] array = {1,2,3,4};
        int[] copy = new int[array.length];
        System.arraycopy(array,0,copy,0,array.length);

        System.out.println(Arrays.toString(copy));
    }
}

第四种拷贝方式：

Arrays.copyOf（这个也是以后用的非常多的拷贝方式）：

import java.util.Arrays;

public class TestDemo {
    public static void main(String[] args) {
        int[] array = {1,2,3,4};
        int[] copy = array.clone();
        System.out.println(Arrays.toString(copy));
    }
}

?

怎么去证明这个：

5.3 求一个整型数组的平均值

import java.util.Arrays;

public class TestDemo {
    public static double avg(int[] array){
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum = sum+array[i];
        }
        return sum*1.0/array.length;
    }
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5};
        System.out.println(avg(array));
    }
}

5.4 查找数组中指定元素（顺序查找）

顺序查找

根据给定的数组，然后去找数组中的某一个值；

需要从头开始，一个一个的去往下找，看 哪一个是所需要找的值，找到就可以返回它的下标。

import java.util.Arrays;

public class TestDemo {
    public static int search(int[] array,int key){
        for (int i = 0; i < array.length; i++) {
            if(array[i]==key){
                return i;
            }
        }
        //如果代码走到这里，说明退出了for循环，或者是没有进入for循环
        return -1;//返回-1的原因是 因为数组没有负数下标(当然随便一个负数都可以)
    }
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5};
        int index = search(array,4);
        if (index == -1){
            System.out.println("没有你要找的关键字！");
        }else {
            System.out.println("找到了你要的关键字，下标是："+index);
        }
    }

}

最坏的情况下，需要遍历所有数组的元素一个一个的去找，即时间复杂度是O(N)，这个效率就会比较慢。?

5.5?查找数组中指定元素(二分查找)?

由于顺序查找的效率可能比较慢，下面来介绍一种比较高效的查找方法：二分查找。

二分查找

二分查找需要一个前提条件：要查找的这一数组中的数据必须是有序的。

import java.util.Arrays;

public class TestDemo {
    public static int binarySearch(int[] array,int key){
        int left = 0;
        int right = array.length-1;
        while (left <= right){
            int mid = (left + right)/2;
            if (array[mid] < key){
                left = mid + 1;
            }else if (array[mid]==key){
                return mid;
            }else {
                right = mid - 1;
            }
        }
        //假如代码可以走到这里，说明 left>right
        return -1;
    }
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5};
        int index = search(array,4);
        if (index == -1){
            System.out.println("没有你要找的关键字！");
        }else {
            System.out.println("找到了你要的关键字，下标是："+index);
        }
    }
}

? ? ? ?那么有的人就会说，二分查找限制好大啊，还需要 有序数组；

? ? ? ?可以先对数组进行排序，然后再去查找某个元素；

? ? ? ?其实，Java是很友好的，它提供了一个专门去排序的sort方法（在工具类Arrays里面）：

Arrays.sort(要排序的数组名);

【说明】如果面试的时候，一定要先和面试官说一下是否可以先用Arrays.sout排序，要不然面试官是想让你好好找元素，而不是要来排序的；如果在不排序的情况下，再把问题解决了那才是最厉害的。

【注意】

1. sort方法是没有返回值的,并且默认是升序；
2. 对于现在的简单数据类型，能不能用降序排序 ——> 答案是做不到；
3. 怎么样可以做到 指定的升序或者降序，我们需要继续向后学习，去学习接口；
4. 只有所要排序的数据 是引用类型的时候 才可以做到 指定的升序和降序。至于具体的做法，则会在抽象类和接口的那一部分会介绍的。

【说明】 其实在Java中也已经有排序的方法了，甚至于以后可以不用自己写排序了（binarySearch方法)：

5.6 冒泡排序

算法思路：

1. 将数组中相邻元素从前往后依次进行比较，如果前一个元素比后一个元素大，则交换，一趟下来后最大元素就在数组的末尾；
2. 依次从上上述过程，直到数组中所有的元素都排列好。

代码示例：

import java.util.Arrays;

public class TestDemo {
    public static void bubbleSort(int[] array){
        //[0~length-1) i代表的是要比较的趟数
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;

            //在这里可以不用减i，如果减了i说明进行了一次优化
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;
                }
            }
            if (flg == false){
                break;
            }
        }
    }
    public static void main(String[] args) {
        int[] array = {12,5,7,3,8};
        System.out.println("排序之前："+Arrays.toString(array));
        bubbleSort(array);
        System.out.println("排序之后："+Arrays.toString(array));
    }

?图示：?

最后的优化：?

? ? ? ?检查是否发生了交换，如果没有就说明已经有序了，就不需要再进行接下来的交换了。

? ? ? ?即上面所示例的代码 flg那部分是false、true、false或者是true、false、true都可以，亲测有效哦！?

? ? ? ?冒泡排序的思想暂时就介绍到这里了，上面的代码示例也是稍微优化过的代码；

? ? ? ?如果有时间的话，会专门出一期关于排序的博客，会从头到尾的介绍一下优化过程之类的......

?

5.7?数组逆序

思路：

import java.util.Arrays;

public class TestDemo {
    public static void reserve(int[] array){
        int left = 0;
        int right = array.length-1;
        int tmp = 0;
        while (left<right){
            tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
            left++;
            right--;
        }
    }
    public static void main(String[] args) {
        int[] array = {11,22,33,44,55,66,77,88,99,1010};
        System.out.println("逆置之前："+ Arrays.toString(array));
        reserve(array);
        System.out.println("逆置之后："+Arrays.toString(array));
    }
}

5.8 其他?

? ? ? ?浅浅的介绍一下 Arrays这个工具类，里面具有很多的方法，详情可以去看看帮助手册：

? ? ? ?通过之前的介绍，我们已经知道了 打印数组的toSpring()方法，以及 拷贝数组的copyOf()方法，这里就不过多的介绍了嗷。

? ? ? ?现在来介绍一下其他的方法：

? ? ? ?copyOfRange()方法 ——> 这个只是拷贝一部分的情况：

六、二维数组

【说明】这个二维数组也会和C语言中的二维数组有细微的差别，请听我娓娓道来：?

二维数组本质上也就是一维数组，?只不过每个元素又是一个一维数组。?

基本语法：

定义及初始化：

第一种（以直接赋值的方式）：

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

第二种（直接new）：

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

? ? ? ?前面两种方式（后面有自己 赋初值的） 都不能在 中括号里面 写数字，否则就会报错；它会自动识别并给出相应的数据。

第三种（没有赋初始值的）：

    int[][] array3 = new int[2][3];

? ? ? ?此时右端需要数值（不然判断不出来有几行几列），并且默认初始值都是0。

打印二维数组：

? ? ? ?可是，难道需要每一次都去改变 i 和 j 的值来改变 行和列的嘛，这明显不现实；

? ? ? ?因此咱们还需要修改一下：

具体分析一下：

用各种方式打印二维数组的代码示例：

import java.util.Arrays;

public class TestDemo {
    public static void main(String[] args) {
        int[][] array1 = {{1,2,3},{4,5,6}};
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1[i].length; j++) {
                System.out.print(array1[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("使用foreach来进行打印：");
        for (int[] tmp:array1){
            for (int x:tmp) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
        System.out.println("使用toString方法来进行打印：");
        System.out.println(Arrays.deepToString(array1));
    }

}

?上面示例的结果：?

总结

这一话的需要知道的内容就这么多了，

如果有啥不到位的地方欢迎指出来，大家互相督促、共同进步啊。

当然啦如果铁铁们可以一键三连那就更棒了，特别特别感谢 ?(???????)??。