一、数组的概念

  • 数组概念： 数组是用于存储数据的长度固定的容器，保证多个数据的数据类型要一致

  • 数组的特点

    • 数组的长度一旦确定就不能修改
    • 创建数组时会在内存中开辟一整块连续的空间
    • 存取元素的速度快，因为可以通过[下标]，直接定位到任意一个元素

  • 数组的分类

    • 按照维度分：
      • 一维数组：存储一组数据
      • 二维数组：一行代表一组数据，每一行长度可以不一样
    • 按照元素类型分：
      • 基本数据类型的元素：存储数据值
      • 引用数据类型的元素：存储对象（本质上存储对象的首地址）

无论数组的元素是基本数据类型还是引用数据类型，数组本身都是引用数据类型

二、一维数组的声明与使用

1、一维数组的声明

  • 一维数组的声明格式

    • 数组类型[] 数组的名称;（推荐）
    • 数组类型 数组名[];

  • 声明数组三要素

    • 数组的维度：[]表示一维，[][]表示二维
    • 数组的元素类型：可以是任意的Java的数据类型
    • 数组名：引用数据类型的变量，因为它代表一组数据

2、一维数组的动态初始化

  • 动态初始化：确定元素的个数（即数组的长度），而元素此时只是默认值，并不是真正的数据

  • 动态初始化格式

    • 元素的数据类型[] 数组名 = new 元素的数据类型[长度];
    • 元素的数据类型[] 数组名;``数组名 = new 元素的数据类型[长度];

new：创建数组使用的关键字。因为数组本身是引用数据类型，所以要用new创建数组对象

  • 数组元素的默认值
数组元素类型 元素默认初始值
byte 0
short 0
int 0
long 0L
float 0.0F
double 0.0
char 0
boolean false
引用类型 null

3、一维数组的静态初始化

  • 静态初始化：用静态数据为数组初始化，此时数组的长度由静态数据的个数决定

  • 静态初始化格式

    • 数据类型[] 数组名 = {元素1,元素2,元素3...};（不能分两个语句写）
    • 数据类型[] 数组名 = new 数据类型[]{元素1,元素2,元素3...};
    • 数据类型[] 数组名;``数组名 = new 数据类型[]{元素1,元素2,元素3...};

4、一维数组的使用

  • 获取数组长度（元素总个数）：数组名.length

  • 访问数组元素：数组名[下标]

  • 数组的下标范围：[0, 数组名.length-1]

5、一维数组的遍历

  • 数组遍历： 将数组中的每个元素分别获取出来
1
2
3
for(int i=0; i<arr.length; i++){
    System.out.println(arr[i]);
}

三、一维数组内存分析

1、Java虚拟机的内存划分

为了提高运算效率，空间进行了不同区域的划分，每一片区域都有特定的处理数据方式和内存管理方式

img

区域名称 作用
程序计数器 程序计数器是CPU中的寄存器，它包含每一个线程下一条要执行的指令的地址
本地方法栈 当程序中调用了native的本地方法时，本地方法执行期间的内存区域
方法区 存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据
堆内存 存储对象（包括数组对象），new来创建的，都存储在堆内存
虚拟机栈 用于存储正在执行的每个Java方法的局部变量表等。局部变量表存放了编译期可知长度的各种基本数据类型、对象引用，方法执行完，自动释放

2、一维数组在内存中的存储

  • 因为第一个元素距离数组首地址间隔0个单元格，所以数组下标从0开始

  • 创建一个数组（方法栈），则会创建了一个连续的内存空间（堆），数组变量指向的是对象的首地址

    • 将一个数组变量赋值到另一个数组变量，两个数组变量本质上代表同一个数组

  • 直接打印数组名出现的不是数组的首地址，因为数组是引用数据类型，打印数组名时，会自动调用数组对象的toString()方法，该方法默认实现的是对象类型名@该对象的hashCode()值的十六进制值，这个值不一定就是对象的内存地址，和不同品牌的JVM产品的具体实现有关

例如：Oracle的OpenJDK中给出了5种实现，其中有一种是直接返回对象的内存地址，但是OpenJDK默认没有选择这种方式

四、数组的常见算法

1、数组统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Test08ArrayElementSum {
    public static void main(String[] args) {
        int[] arr = {4,5,6,1,9};
        //求总和、均值
        int sum = 0;//因为0加上任何数都不影响结果
        for(int i=0; i<arr.length; i++){
            sum += arr[i];
        }
        double avg = (double)sum/arr.length;

        System.out.println("sum = " + sum);
        System.out.println("avg = " + avg);
    }
}
public class Test09ArrayElementMul {
    public static void main(String[] args) {
        int[] arr = {4,5,6,1,9};

        //求总乘积
        long result = 1;//因为1乘以任何数都不影响结果
        for(int i=0; i<arr.length; i++){
            result *= arr[i];
        }

        System.out.println("result = " + result);
    }
}
public class Test10ArrayElementEvenCount {
    public static void main(String[] args) {
        int[] arr = {4,5,6,1,9};
        //统计偶数个数
        int evenCount = 0;
        for(int i=0; i<arr.length; i++){
            if(arr[i]%2==0){
                evenCount++;
            }
        }

        System.out.println("evenCount = " + evenCount);
    }
}

2、数组找最值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Test11ArrayMax {
    public static void main(String[] args) {
        int[] arr = {4,5,6,1,9};
        //找最大值
        int max = arr[0];
        for(int i=1; i<arr.length; i++){//此处i从1开始，max不需要与arr[0]再比较一次了
            if(arr[i] > max){
                max = arr[i];
            }
        }

        System.out.println("max = " + max);
    }
}

3、数组的元素查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class Test14ArrayOrderSearch {
    //查找value第一次在数组中出现的index
    public static void main(String[] args){
        int[] arr = {4,5,6,1,9};
        int value = 1;
        int index = -1;

        for(int i=0; i<arr.length; i++){
            if(arr[i] == value){
                index = i;
                break;
            }
        }

        if(index==-1){
            System.out.println(value + "不存在");
        }else{
            System.out.println(value + "的下标是" + index);
        }
    }
}
import java.util.Scanner;

public class Test15ArrayBinarySearch {
    public static void main(String[] args){
        //数组一定是有序的
        int[] arr = {8,15,23,35,45,56,75,85};

        Scanner input = new Scanner(System.in);
        System.out.print("请输入你要查找的值：");
        int target = input.nextInt();

        int index = -1;
        for(int left = 0,right = arr.length-1; left<=right; ){
            //int mid = (left+right)/2;
            int mid = left + (right-left)/2;

            if(arr[mid] == target){
                index = mid;
                break;
            }else if(target > arr[mid]){
                //说明target在[mid]右边
                left = mid+1;
            }else{
                //说明target<arr[mid]，target在[mid]左边
                right= mid-1;
            }
        }
        if(index!=-1){
            System.out.println("找到了，下标是"+index);
        }else{
            System.out.println("不存在");
        }

    }
}

4、数组的元素翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Test17ArrayReverse {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        System.out.println("反转之前：");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        
        for(int i=0; i<arr.length/2; i++){
            int temp = arr[i];
            arr[i] = arr[arr.length-1-i];
            arr[arr.length-1-i] = temp;
        }

        System.out.println("反转之后：");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

}
public class Test17ArrayReverse2 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        System.out.println("反转之前：");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

        //反转
        //左右对称位置交换
        for(int left=0,right=arr.length-1; left<right; left++,right--){
            //首  与  尾交换
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }

        System.out.println("反转之后：");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

5、数组元素排序

冒泡排序原理：比较两个相邻的元素，将值大的元素交换至右端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
1、冒泡排序（最经典）
思想：每一次比较“相邻（位置相邻）”元素，如果它们不符合目标顺序（例如：从小到大），
     就交换它们，经过多轮比较，最终实现排序。
*/
public class Test19BubbleSort{
    public static void main(String[] args){
        int[] arr = {6,9,2,9,1};

        for(int i=1; i<arr.length; i++){ //循环次数是arr.length-1次/轮
            for(int j=0; j<arr.length-i; j++){
                //希望的是arr[j] < arr[j+1]
                if(arr[j] > arr[j+1]){
                    //交换arr[j]与arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

        //完成排序，遍历结果
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i]+"  ");
        }
    }
}

6、算法时空复杂度

  • 时间复杂度：一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。n称为问题的规模，一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，当n不断变化时，时间频度T(n)也会不断变化。若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n))，称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

img

  • 空间复杂度(Space Complexity)：类似于时间复杂度的讨论，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数
  • 稳定性：排序算法一定会设计到数组元素位置的交换。如果两个元素相等，无论它们原来是否相邻，在排序过程中，最后它们变的相邻，但是它们前后顺序并没有改变，就称为稳定的，否则就是不稳定的

img

五、二维数组的声明与使用

1、二维数组的声明

  • 二维数组：本质上就是元素为一维数组的数组

  • 二维数组的标记：[][]

  • 二维数组声明的语法格式

    • 元素的数据类型[][] 二维数组名;（推荐）
    • 元素的数据类型 二维数组名[][];
    • 元素的数据类型[] 二维数组名[];

int[] x, y[];，此处x是一维数组，y是二维数组

2、二维数组动态初始化

  • 动态初始化格式

    • （1）规则二维表：每一行的列数是相同的
      • 元素的数据类型[][] 二维数组名 = new 元素的数据类型[m][n];
    • （2）不规则二维表：每一行的列数不一样
      • 元素的数据类型[][] 二维数组名 = new 元素的数据类型[总行数][];
      • 二维数组名[行下标] = new 元素的数据类型[该行的总列数];

3、二维数组的静态初始化

  • 静态初始化格式

    • 元素的数据类型[][] 二维数组的名称 = {{第一行的值列表}, ...{第n行的值列表}};（不能分两个语句写）
    • 元素的数据类型[][] 二维数组名 = new 元素的数据类型[][] {{第一行的值列表}, ...{第n行的值列表}};
    • 元素的数据类型[][] 二维数组名;``二维数组名 = new 元素的数据类型[][]{{第一行的值列表}, ...{第n行的值列表}};

new 数据类型[][]中不能写数字，因为行数和列数，由{}的元素个数决定

4、二维数组的使用

  • 获取二维数组长度(行数)：二维数组名.length
  • 访问二维数组某一行：二维数组名[行下标]
  • 访问某一行的列数：二维数组名[行下标].length
  • 访问某一个元素：二维数组名[行下标][列下标]
  • 获取行下标的范围：[0, 二维数组名.length-1]

5、二维数组的遍历

1
2
3
4
5
6
for(int i=0; i<二维数组名.length; i++){ //二维数组对象.length
    for(int j=0; j<二维数组名[i].length; j++){//二维数组行对象.length
        System.out.print(二维数组名[i][j]);
    }
    System.out.println();
}