数组的定义

  • 数组是相同类型数据的有序集合。

数组的声明创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//声明一个数组
int[] nums;//1.声明一个数组
int nums2[];
//两种方法都可以声明一个整型数组，但建议使用第一个
nums = new int[10];//2.创建一个数组

//也可以这样写
int[] nums = new int[10];//声明并创建一个数组

//3.给数组元素赋值
nums[0] = 1;
nums[1] = 2;
nums[2] = 3;
nums[3] = 4;
nums[4] = 5;
nums[5] = 6;
nums[6] = 7;
nums[7] = 8;
nums[8] = 9;
nums[9] = 10;
//int类型数组未赋值的元素默认值是0
  • 获取数组长度：arrays.length。
1
2
3
4
5
6
//计算所有元素的和
int sum = 0;

for (int i = 0;i<nums.length;i++){
    sum = sum + nums[i];
}

内存分析

三种初始化

  1. 静态初始化

    1
    int[] a = {1,2,3,4,5,6,7,8,};//一旦定义不可改变

  1. 动态初始化(包含默认初始化)

    1
    2
    3
    4
    int[] nums = new int[10];
    nums[0] = 1;
    nums[1] = 2;
    nums[2] = 3;
  1. 数组的默认初始化

数组的四个基本特点

  1. 长度确定。数组一旦被创建，它的大小就不可以改变。

  2. 元素必须是相同类型，不允许出现混合类型。

  3. 数组中的元素可以是任意数据类型，包括基本类型和引用类型。

  4. 数组本身就是对象，可以无限套娃。数组对象本身是在堆中。

数组边界

  • 下标的合法区间：[0,length-1]，如果越界就会报错。

数组的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
    int[] arrays = {1,2,3,4,5};
    //计算所有元素的和
    int sum = 0;
    for (int i = 0; i < arrays.length; i++) {
        sum += arrays[i];
    }
    System.out.println("sum="+sum);//sum=15
    //查找最大元素
    int max =arrays[0];
    for (int i = 0; i < arrays.length; i++) {
        if (arrays[i]>max){
            max = arrays[i];
        }
    }
    System.out.println("max="+max);
}

For-Each循环

1
2
3
4
for (int array: arrays) {
    System.out.println(array);
}//遍历每一个元素
//缺点：没有下标，不方便对某个元素操作

数组作为方法入参

1
2
3
4
5
6
//定义一个方法，打印数组元素
public static void printArray(int[] arrays){
    for (int i = 0; i < arrays.length; i++) {
        System.out.print(arrays[i]+" ");
    }
}

数组作返回值

1
2
3
4
5
6
7
8
9
//定义一个方法，反转数组
public static int[] reverse(int[] arrays){
    int[] result = new int[arrays.length];
    //反转的操作
    for (int i = 0,j = result.length-1; i < arrays.length; i++,j--) {
        result[j] = arrays[i];
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Demo03 {
    public static void main(String[] args) {
        int[] arrays = {1,2,3,4,5};
        printArray(arrays);
        System.out.println();
        int[] reverse = reverse(arrays);
        printArray(reverse);
    }
    //定义一个方法，打印数组元素
    public static void printArray(int[] arrays){
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i]+" ");
        }
    }
    //定义一个方法，反转数组
    public static int[] reverse(int[] arrays){
        int[] result = new int[arrays.length];
        //反转的操作
        for (int i = 0,j = result.length-1; i < arrays.length; i++,j--) {
            result[j] = arrays[i];
        }
        return result;
    }
}

多维数组

  • 一般我们这样定义一个数组：

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

  • int a[][] = new int[2][5];

    以上二维数组a可以看成一个两行五列数组。

使用

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
    int[][] array = {{1,2},{2,4},{3,4},{4,5}};
    //打印二维数组的每一个元素
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[i].length; j++) {
            System.out.println(array[i][j]);
        }
    }
}

Arrays类

  • import java.util.Arrays; 
1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.Arrays;

public class Demo05 {
    public static void main(String[] args) {
        int[] a = {1,5,7,6485,4564,789,26};
        //打印数组元素Array.toString
        System.out.println(Arrays.toString(a));
        Arrays.sort(a);//数组进行排序
        System.out.println(Arrays.toString(a));
    }
}
//[1, 5, 7, 6485, 4564, 789, 26]
//[1, 5, 7, 26, 789, 4564, 6485]

  • 具有以下常用功能：

    • 给数组赋值：通过fill方法。

    • 对数组排序：通过sort方法，按升序。

    • 比较数组：通过equals方法比较数组中元素值是否相等。

    • 查找数组元素：通过binarySearch方法能对排序好的数组进行二分查找法操作。

冒泡排序

  1. 比较数组中，两个相邻的元素，如果第一个数比第二个数大，我们就交换他们的位置。

  2. 每一次比较，都会产出一个最大，或者最小的数字。

  3. 下一轮则可以少一次排序。

  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
import java.util.Arrays;

public class Demo06 {
    public static void main(String[] args) {
        int[] a = {1,45,1574,18574,45,2,2,78,2};
        int[] sort = sort(a);//调用完我们自己写的排序算法后，返回一个排序后的数组
        System.out.println(Arrays.toString(sort));
    }

    public static int[] sort(int[] array){
        //临时变量
        int temp = 0;

        //外层循环，判断我们要走多少次
        for (int i = 0; i < array.length-1; i++) {
            //内层循环，比价判断两个数，如果第一个数比第二个数大，则交换位置
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j+1]<array[j]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        return array;
    }
}

时间复杂度优化

  • 通过定义一个布尔值，在外层循环下，默认为false，在内层循环内，将布尔值重改为true，然后每当内层循环结束后判断布尔值是否为false，如果为false，表明排序已完成，直接跳出外层循环。
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
import java.util.Arrays;

public class Demo06 {
    public static void main(String[] args) {
        int[] a = {1,45,1574,18574,45,2,2,78,2};
        int[] sort = sort(a);//调用完我们自己写的排序算法后，返回一个排序后的数组
        System.out.println(Arrays.toString(sort));
    }

    public static int[] sort(int[] array){
        //临时变量
        int temp = 0;

        //外层循环，判断我们要走多少次
        for (int i = 0; i < array.length-1; i++) {
            //内层循环，比价判断两个数，如果第一个数比第二个数大，则交换位置
            boolean flag = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j+1]<array[j]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = true;
                }
            }
            if (flag==false){
                break;
            }
        }
        return array;
    }
}

稀疏数组

  • 二维数组中如果很多值都是0或者同一数值时，意味着记录了很多没有意义的数据。采用稀疏数组是不错的选择。

  • 稀疏数组的处理方式是：

    • 记录数组一共有几行几列，有多少个不同值。

    • 把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模。

原始数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Demo07 {
    public static void main(String[] args) {
        //创建一个二维数组 11*11   0：没有棋子   1：黑棋   2：白棋
        int [][] array1 = new int[11][11];
        array1[1][2] = 1;
        array1[2][3] = 2;
        System.out.println("输出原始的数组：");

        for (int[] ints : array1) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
    }
}

稀疏数组

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package cool.ply.array;

public class Demo07 {
    public static void main(String[] args) {
        //创建一个二维数组 11*11   0：没有棋子   1：黑棋   2：白棋
        int [][] array1 = new int[11][11];
        array1[1][2] = 1;
        array1[2][3] = 2;
        System.out.println("输出原始的数组：");

        for (int[] ints : array1) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
        //转化为稀疏数组保存
        //获取有效值的个数
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (array1[i][j]!=0){
                    sum++;
                }
            }
        }
        System.out.println("有效值个数为："+sum);

        //创建一个稀疏数组的数组
        int[][] array2 = new int[sum+1][3];
        array2[0][0] = 11;
        array2[0][1] = 11;
        array2[0][2] = sum;

        //遍历二维数组，将非零的值存放在稀疏数组中
        int count = 0;
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1[i].length; j++) {
                if (array1[i][j]!=0){
                    count++;
                    array2[count][0] = i;
                    array2[count][1] = j;
                    array2[count][2] = array1[i][j];
                }
            }
        }

        //输出稀疏数组
        System.out.println("稀疏数组");
        for (int i = 0; i < array2.length; i++) {
            System.out.println(array2[i][0]+"\t"
                    +array2[i][1]+"\t"
                    +array2[i][2]+"\t");
        }

        System.out.println("======================");
        System.out.println("还原");
        //读取稀疏数组
        int[][] array3 = new int[array2[0][0]][array2[0][1]];
        //给其中的元素还原值
        for (int i = 1; i < array2.length; i++) {
            array3[array2[i][0]][array2[i][1]] = array2[i][2];
        }
        //打印
        System.out.println("输出还原的数组");
        for (int[] ints : array3) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
    }
}

  • 输出结果为：