一、数组的概述

数组(Array)，是多个相同类型数据按一定顺序排列 的集合，并使用一个名字命名，并通过编号的方式 对这些数据进行统一管理。

数组的常见概念：

  • 数组名
  • 下标(或索引)
  • 元素
  • 数组的长度：元素的个数

数组的特点：

  1. 数组是有序排列的；
  2. 数组属于引用数据类型的变量。数组的元素既可以是基本数据类型，也可以是引用数据类型；
  3. 创建数组对象会在内存中开辟一整块连续的空间；
  4. 数组的长度一旦确定，就不能修改。

数组的分类：

  1. 按照维度：一维数组、二维数组、三维数组、…
  2. 按照元素的数据类型分：基本数据类型元素的数组、引用数据类型元素的数组(即对象数组）

二、一维数组的使用：6个点

一维数组的声明和初始化的两种方式
声明：type 数组名[ ] 或者 type[ ] 数组名

初始化：
动态初始化： 数组声明且为数组元素分配空间与赋值的操作分开进行。
静态初始化：数组的初始化和数组元素的赋值操作同时进行。
int[] arr = new int[5];//动态初始化
String[] arr1 = new String[]{“Tom”,”Jerry”,”Jim”};//静态初始化

  • 数组一旦初始化，其长度就是确定的。arr.length
  • 数组长度一旦确定，就不可修改。【我的理解：为什么一旦初始化长度就确定？因为如果没有确定长度，就不能在内存中确定要开辟的空间，所以一旦初始化长度必确定。】

数组元素的引用：
定义并用运算符 new 为之分配空间后，才可以引用数组中的每个元素；
数组元素的引用方式：数组名[数组元素下标]

如何获取数组的长度：
每个数组都有一个属性 length 指明它的长度，例如：a.length 指明数组a的长度(元素个数)

如何遍历数组：
for ( int i = 0; i < 数组名.length; i++) { …}

数组元素的默认初始化值：
image.png

数组的内存解析：
看这个视频说的很清楚https://www.bilibili.com/video/BV1Kb411W75N?p=146
内存的简化结构：
数组 - 图2

  • 注意：在 main 方法中的 new 出来的对象都是局部变量
  • image.png
  • 内存解析的步骤
    • 1）声明 type[ ] 数组名 会先在栈中出现 数组名的空间
    • 2）初始化 在堆中开辟一个数组空间，先给予默认初始化值，如果有赋值就会替换掉初始值
    • 3）最后给栈中该数组名的空间赋值，赋值为堆中该数组的地址。
    • 4）如果对一个已经声明和初始化过的变量（即这个数组），重新初始化，如上图：arr1 = new String[3];（看：在第二行已经给 arr1 声明过了，为数组类型。）所以这句话就是重新初始化 arr1。这时会先在堆中开辟一个新的数组空间，再把新的数组空间的地址给 arr1 替换掉原来的数组地址。（就是重复以上的2）、3）步骤啦）

三、二维数组的使用：6个点

二维数组的声明和初始化：
声明： type[ ][ ] 数组名 或者 type[ ] 数组名[ ] 或者 type 数组名[ ][ ]
静态初始化：

  • int[ ][ ] 数组名 = new int[ ][ ];

动态初始化：

  • int[ ][ ] 数组名 = new int[3][3]; //动态初始化1
  • int[ ][ ] 数组名 = new int [3][ ];//动态初始化2
    • 数组名[0] = new int[1];//可以分别再初始化内层数组的元素
      • 数组名[0][0] = 100;//再对内层数组的元素赋值
      • 数组名[0][1] = 999;//赋值
    • 数组名[1] = new int[5];
    • …

错误示范：

  • String[3][3] 数组名 = new String[ ][ ];//错误，声明的时候不能在声明里面写数组的大小String[ ][ ]，[ ]里面要为空。
  • String [ ][ ] 数组名 = new String [ ][3];//错误，new 出来的第一个[ ]里面必须先给大小，才能给第二个[ ]给大小。
  • String[ ][ ] 数组名 = new String[3][3]{{1,1,1},{2,2,2},{3,3}};//错误，动态初始化和静态初始化不能混在一起使用。

第一个[ ]：表示有几行
第二个[ ]：表示有几列

数组元素的引用：

  • 数组名[1][1];

如何获取数组的长度：

  • 数组名.length
  • 数组名[1].length
  • 二维数组的长度就是第一个[ ] 的长度 数组名.length
  • 我们还可以得到二维数组第一个元素的数组长度，因为二位数组里面还是数组，
  • 所以 数组名[1].length

如何遍历数组：
for ( int i = 0; i < 数组名.length; i++) {
for ( int j = 0; j < 数组名[i].length; j++){
…
}
}

数组元素的默认初始化值：
int[ ][ ] 数组名 = new int[3][4];
外层数组的元素：数组名[0]，数组名[2]等
内层数组的元素：数组名[0][1]，数组名[3][4]等

  • 针对初始化方式一：int[ ][ ] 数组名 = new int[3][3]; //动态初始化1
    • 外层数组的元素的初始化值为：地址值
    • 内层数组的元素的初始化值为：与一维数组的初始化情况相同
  • 针对初始化方式一：int[ ][ ] 数组名 = new int [3][ ];//动态初始化2
    • 外层数组的元素的初始化值为：null
    • 内层数组的元素的初始化值为：异常报错。【我的理解：你想想啊，第一个地址是null，就是不存在该地址，那么这个地址下的内层数组就肯定在堆里面没有开辟出空间，就会空指针异常报错啦】

数组的内存解析：
这个视频说的很明白：https://www.bilibili.com/video/BV1Kb411W75N?p=153
image.png

  • 第一句：先在栈中声明一个 arr1，new int[4][]表示在堆中开辟一个数组空间大小为4，给默认初始化值为null（为什么会是null？因为外层元素都属于数组类型，引用数据类型里的数组，引用数据类型的默认初始化都为null）。
  • 第二句：给外层元素arr1[1]，静态初始化在栈中开辟一个数组空间，arr1[1]指向该数组空间的第一个元素的地址，在静态初始化前默认初始化值是0（为什么是0？因为在声明的时候，声明了里面的元素为 int 型，【我的理解：声明数据类型的时候，是声明最内层的元素的数据类型，除去最内层的元素，其他层存的元素值都是一个地址。】），再静态初始化为{1,2,3}，替换掉原来的默认值。
  • 第三句：给外层元素arr1[2]，动态初始化，在堆中开辟一个数组大小为4的空间，arr1[2]指向该空间的地址，默认初始化值为0，同第二句话。
  • 第四句：给arr1[2][1]，赋值为30，替换掉原来的默认初始值。

四、数组中涉及到的常见算法

4.1 数组元素的赋值(杨辉三角、回形数等)

  1. package com.atguigu.exer;
  2. /*
  3.  * 使用二维数组打印一个 10 行杨辉三角。
  5. 【提示】
  6.  1. 第一行有 1 个元素, 第 n 行有 n 个元素
  7.  2. 每一行的第一个元素和最后一个元素都是 1
  8.  3. 从第三行开始, 对于非第一个元素和最后一个元素的元素。即：
  9. yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
  10.  * 
  11.  */
  12. public class YangHuiTest {
  14.     public static void main(String[] args) {
  15.         //1.声明并初始化二维数组
  16.         int[][] yangHui = new int[10][];
  18.         //2.给数组的元素赋值
  19.         for(int i = 0;i < yangHui.length;i++){
  20.             yangHui[i] = new int[i + 1];
  22.             //2.1 给首末元素赋值
  23.             yangHui[i][0] = yangHui[i][i] = 1;
  24.             //2.2 给每行的非首末元素赋值
  25.             //if(i > 1){
  26.             for(int j = 1;j < yangHui[i].length - 1;j++){
  27.                 yangHui[i][j] = yangHui[i-1][j-1] + yangHui[i-1][j];
  28.             }
  29.             //}
  30.         }
  33.         //3.遍历二维数组
  34.         for(int i = 0;i < yangHui.length;i++){
  35.             for(int j = 0;j < yangHui[i].length;j++){
  36.                 System.out.print(yangHui[i][j] + "  ");
  37.             }
  38.             System.out.println();
  39.         }
  43.     }
  46. }

4.2 求数值型数组中元素的最大值、最小值、平均数、总和等

  1. package com.atguigu.java;
  2. /*
  3.  * 算法的考查：求数值型数组中元素的最大值、最小值、平均数、总和等
  4.  * 
  5.  * 定义一个int型的一维数组，包含10个元素，分别赋一些随机整数，
  6.  * 然后求出所有元素的最大值，最小值，和值，平均值，并输出出来。    
  7.  * 要求：所有随机数都是两位数。
  8.  * 
  9.  * [10,99]
  10.  * 公式：(int)(Math.random() * (99 - 10 + 1) + 10)
  11.  * 
  12.  */
  13. public class ArrayTest1 {
  14.     public static void main(String[] args) {
  15.         int[] arr = new int[10];
  17.         for(int i = 0;i < arr.length;i++){
  18.             arr[i] = (int)(Math.random() * (99 - 10 + 1) + 10);
  19.         }
  21.         //遍历
  22.         for(int i = 0;i < arr.length;i++){
  23.             System.out.print(arr[i] + "\t");
  24.         }
  25.         System.out.println();
  27.         //求数组元素的最大值
  28.         int maxValue = arr[0];
  29.         for(int i = 1;i < arr.length;i++){
  30.             if(maxValue < arr[i]){
  31.                 maxValue = arr[i];
  32.             }
  33.         }
  34.         System.out.println("最大值为：" + maxValue);
  36.         //求数组元素的最小值
  37.         int minValue = arr[0];
  38.         for(int i = 1;i < arr.length;i++){
  39.             if(minValue > arr[i]){
  40.                 minValue = arr[i];
  41.             }
  42.         }
  43.         System.out.println("最小值为：" + minValue);
  44.         //求数组元素的总和
  45.         int sum = 0;
  46.         for(int i = 0;i < arr.length;i++){
  47.             sum += arr[i];
  48.         }
  49.         System.out.println("总和为：" + sum);
  50.         //求数组元素的平均数
  51.         int avgValue = sum / arr.length;
  52.         System.out.println("平均数为：" + avgValue);
  53.     }
  54. }

4.3 数组的复制、反转、查找(线性查找、二分法查找)

  1. package com.atguigu.java;
  2. /*
  3.  * 算法的考查：数组的复制、反转、查找(线性查找、二分法查找)
  4.  * 
  5.  * 
  6.  */
  7. public class ArrayTest2 {
  9.     public static void main(String[] args) {
  11.         String[] arr = new String[]{"JJ","DD","MM","BB","GG","AA"};
  14.         //数组的复制(区别于数组变量的赋值：arr1 = arr)
  15.         String[] arr1 = new String[arr.length];
  16.         for(int i = 0;i < arr1.length;i++){
  17.             arr1[i] = arr[i];
  18.         }
  20.         //数组的反转
  21.         //方法一：
  22. //        for(int i = 0;i < arr.length / 2;i++){
  23. //            String temp = arr[i];
  24. //            arr[i] = arr[arr.length - i -1];
  25. //            arr[arr.length - i -1] = temp;
  26. //        }
  28.         //方法二：
  29. //        for(int i = 0,j = arr.length - 1;i < j;i++,j--){
  30. //            String temp = arr[i];
  31. //            arr[i] = arr[j];
  32. //            arr[j] = temp;
  33. //        }
  35.         //遍历
  36.         for(int i = 0;i < arr.length;i++){
  37.             System.out.print(arr[i] + "\t");
  38.         }
  40.         System.out.println();
  41.         //查找（或搜索）
  42.         //线性查找：
  43.         String dest = "BB";
  44.         dest = "CC";
  46.         boolean isFlag = true;
  48.         for(int i = 0;i < arr.length;i++){
  50.             if(dest.equals(arr[i])){
  51.                 System.out.println("找到了指定的元素，位置为：" + i);
  52.                 isFlag = false;
  53.                 break;
  54.             }
  56.         }
  57.         if(isFlag){
  58.             System.out.println("很遗憾，没有找到的啦！");
  60.         }
  61.         //二分法查找：(熟悉)
  62.         //前提：所要查找的数组必须有序。
  63.         int[] arr2 = new int[]{-98,-34,2,34,54,66,79,105,210,333};
  65.         int dest1 = -34;
  66.         dest1 = 35;
  67.         int head = 0;//初始的首索引
  68.         int end = arr2.length - 1;//初始的末索引
  69.         boolean isFlag1 = true;
  70.         while(head <= end){
  72.             int middle = (head + end)/2;
  74.             if(dest1 == arr2[middle]){
  75.                 System.out.println("找到了指定的元素，位置为：" + middle);
  76.                 isFlag1 = false;
  77.                 break;
  78.             }else if(arr2[middle] > dest1){
  79.                 end = middle - 1;
  80.             }else{//arr2[middle] < dest1
  81.                 head = middle + 1;
  82.             }
  85.         }
  87.         if(isFlag1){
  88.             System.out.println("很遗憾，没有找到的啦！");
  89.         }
  92.     }
  93. }

数组的赋值(相当于快捷方式，打开的还是原来地址的文件)：https://www.bilibili.com/video/BV1Kb411W75N?p=162

  1. package com.atguigu.exer;
  2. /*
  3.  * 使用简单数组
  4. (1)创建一个名为ArrayExer2的类，在main()方法中声明array1和array2两个变量，他们是int[]类型的数组。
  5. (2)使用大括号{}，把array1初始化为8个素数：2,3,5,7,11,13,17,19。
  6. (3)显示array1的内容。
  7. (4)赋值array2变量等于array1，修改array2中的偶索引元素，使其等于索引值(如array[0]=0,array[2]=2)。打印出array1。
  8.  * 
  9.  * 思考：array1和array2是什么关系？array1和array2地址值相同，都指向了堆空间的唯一的一个数组实体。
  10.  * 拓展：修改题目，实现array2对array1数组的复制
  11.  */
  12. public class ArrayExer2 {
  13.     public static void main(String[] args) {  //alt + /
  14.         int[] array1,array2;
  16.         array1 = new int[]{2,3,5,7,11,13,17,19};
  18.         //显示array1的内容
  19.         for(int i = 0;i < array1.length;i++){
  20.             System.out.print(array1[i] + "\t");
  21.         }
  23.         //赋值array2变量等于array1
  24.         //不能称作数组的复制。
  25.         array2 = array1;
  27.         //修改array2中的偶索引元素，使其等于索引值(如array[0]=0,array[2]=2)
  28.         for(int i = 0;i < array2.length;i++){
  29.             if(i % 2 == 0){
  30.                 array2[i] = i;
  31.             }
  33.         }
  34.         System.out.println();
  35.         //打印出array1
  36.         for(int i = 0;i < array1.length;i++){
  37.             System.out.print(array1[i] + "\t");
  38.         }
  39.     }
  40. }

image.png
image.png

4.4 数组元素的排序算法

五、数据结构

  1. 数据与数据之间的逻辑关系：集合、一对一、一对多、多对多
  2. 数据的存储结构：
  • 线性表：顺序表（比如：数组）、链表、栈、队列
  • 树形结构：二叉树
  • 图形结构：

六、排序算法

十大内部排序算法

选择排序 直接选择排序、堆排序
交换排序 冒泡排序、快速排序
插入排序 直接插入排序、折半插入排序、shell（希尔）排序
归并排序
桶式排序
基数排序

:::info 堆排序.gif
冒泡排序.gif
快速排序.gif
归并排序.gif

::: 红色的必须掌握，黄色的要说的出思想。

  1. package com.atguigu.java;
  2. /*
  3.  * 数组的冒泡排序的实现
  4.  * 
  5.  */
  6. public class BubbleSortTest {
  7.     public static void main(String[] args) {
  9.         int[] arr = new int[]{43,32,76,-98,0,64,33,-21,32,99};
  11.         //冒泡排序
  12.         for(int i = 0;i < arr.length - 1;i++){
  14.             for(int j = 0;j < arr.length - 1 - i;j++){
  16.                 if(arr[j] > arr[j + 1]){
  17.                     int temp = arr[j];
  18.                     arr[j] = arr[j + 1];
  19.                     arr[j + 1] = temp;
  20.                 }
  22.             }
  24.         }
  29.         for(int i = 0;i < arr.length;i++){
  30.             System.out.print(arr[i] + "\t");
  31.         }
  33.     }
  34. }
  1. package com.atguigu.java;
  3. /**
  4.  * 快速排序
  5.  * 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，
  6.  * 则分别对这两部分继续进行排序，直到整个序列有序。
  7.  * @author shkstart
  8.  * 2018-12-17
  9.  */
  10. public class QuickSort {
  11.     private static void swap(int[] data, int i, int j) {
  12.         int temp = data[i];
  13.         data[i] = data[j];
  14.         data[j] = temp;
  15.     }
  17.     private static void subSort(int[] data, int start, int end) {
  18.         if (start < end) {
  19.             int base = data[start];
  20.             int low = start;
  21.             int high = end + 1;
  22.             while (true) {
  23.                 while (low < end && data[++low] - base <= 0)
  24.                     ;
  25.                 while (high > start && data[--high] - base >= 0)
  26.                     ;
  27.                 if (low < high) {
  28.                     swap(data, low, high);
  29.                 } else {
  30.                     break;
  31.                 }
  32.             }
  33.             swap(data, start, high);
  35.             subSort(data, start, high - 1);//递归调用
  36.             subSort(data, high + 1, end);
  37.         }
  38.     }
  39.     public static void quickSort(int[] data){
  40.         subSort(data,0,data.length-1);
  41.     }
  44.     public static void main(String[] args) {
  45.         int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
  46.         System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
  47.         quickSort(data);
  48.         System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  49.     }
  50. }

七、数组中常见的异常

7.1 数组角标越界的异常：ArrayIndexOutOfBoundsExcetion

7.2 空指针异常：NullPointerException

  1. package com.atguigu.java;
  2. /*
  3.  * 数组中的常见异常：
  4.  * 1. 数组角标越界的异常：ArrayIndexOutOfBoundsExcetion
  5.  * 
  6.  * 2. 空指针异常：NullPointerException
  7.  * 
  8.  */
  9. public class ArrayExceptionTest {
  10.     public static void main(String[] args) {
  12.         //1. 数组角标越界的异常：ArrayIndexOutOfBoundsExcetion
  13.         int[] arr = new int[]{1,2,3,4,5};
  15. //        for(int i = 0;i <= arr.length;i++){
  16. //            System.out.println(arr[i]);
  17. //        }
  19. //        System.out.println(arr[-2]);
  21. //        System.out.println("hello");
  23.         //2.2. 空指针异常：NullPointerException
  24.         //情况一：
  25. //        int[] arr1 = new int[]{1,2,3};
  26. //        arr1 = null;
  27. //        System.out.println(arr1[0]);
  29.         //情况二：
  30. //        int[][] arr2 = new int[4][];
  31. //      System.out.println(arr2[0]);//null，不明白可以看看上面的二维数组
  32. //        System.out.println(arr2[0][0]);
  34.         //情况三：
  35.         String[] arr3 = new String[]{"AA","BB","CC"};
  36.         arr3[0] = null;
  37.         System.out.println(arr3[0].toString());
  38.     }
  39. }

数组的声明和初始化举例：

  1. int[] 数组名；//声明
  2. 数组名 = new int[] {1,2,3};//静态初始化
  1. int[] 数组名；//声明
  2. 数组名 = new int[3];//动态初始化
  3. //赋值
  4. 数组名[0] = 1;
  5. 数组名[1] = 2;
  6. 数组名[2] = 3;
  7. 数组名[3] = 4;
  1. int[] 数组名 = {1,2,3,4} ;//声明加和初始化
  1. int[] 数组名;//声明
  2. 数组名 = {1,2,3,4};
  1. int[] 数组名 = new int[];//错误示范2.1，没有给定数组大小
  2. int[5] 数组名 = new int[5];//错误示范2.2，声明数组的数据类型时，不能给数组大小，
  3. //即int[],[]里面不能，添加数字
  4. int[] 数组名 = new int[3]{1,2,3};//错误示范2.3，静态初始化和动态初始化不能混合在了一起使用
  5. //正确的写法：int[] 数组名 = new int[3];//动态初始化
  6. //             数组名[0] = 1; 数组名[1] = 2; 数组名[2] = 3;
  7. //             int[] 数组名 = new int[]{1,2,3};//静态初始化