数组

数组概述

数组是同类型数据的有序集合
每个数据都是数组的一个元素,可以通过下标来进行访
数组的特点:

其长度是确定的,数组一旦被创建,其大小就不可改变
其元素均为同一数据类型
数组元素可以是任何数据类型:基本类型和引用类型
数组变量自身属于引用数据类型,数组可以视为对象,数组中各元素相当于对象的成员变量
数组本身为对象,在Java中,对象都存在堆内存中;所以数组不管保存何种数据类型,数组对象本身都存放在堆中

数组声明创建

像变量一样,必须先声明数组,才能在之后的程序中使用,声明数组有两种方法:

dataType[] arrayRefVar;		// 首选方法
dataType arrayRefVar[];		// 效果相同,但不推荐

使用new操作符来创建数组,语法如下:

dataType[] arrayRefVar = new dataType[arraySize];

数组的元素通过索引进行访问,索引从0开始,例:array[0]
获取数组的长度:array.length
数组的下标合法区间:[0, length-1],若越界就会报错(数组越界异常):ArrayIndexOutOfBoundsException

数组的初始化

数组有三种初始化方法:

静态初始化:创建+赋值

int[] a = {1, 2, 3};
Man[] mans = {new Man(1, 1), new Man(2, 2)};

动态初始化:包含默认初始化

int[] a = new int[2];
a[0] = 1;
a[1] = 2;

默认初始化

数组为引用类型,其元素相当于类的实例变量,因此数组一经分配空间,其中的每个元素也会按照实例变量的初始化方法进行隐式初始化

数组使用

普通的for循环:对数组进行遍历
for-each循环(增强for循环)

IDEA可以通过array.for快速生成增强for循环
增强for循环无法访问数组的下标

数组作为方法的参数
作为方法的返回值

多维数组

多维数组可以视为数组的数组,即数组的元素仍未数组
二维数组:int[][] a = new int[2][5];,此数组可视为一个2行5列的二维数组
多维数组有多个索引,访问元素的方法与一维数组相同:a[0][2]
遍历多维数组需要嵌套多个for循环,逐层遍历.例:

int[][] arr = new int[2][5];
for (int[] ints : arr) {
	for (int i : ints) {
		System.out.print(i);
	}
}

Arrays类

数组的工具类java.util.Arrays:

数组对象本身没有方法可以调用,但是API提供了Arrays工具类供使用,从而对数组对象进行一系列基本操作
Arrays类中的方法都是static修饰的静态方法,可以直接用类名进行调用,不用使用对象来调用
当用的功能函数:
给数组赋值:fill()方法
给数组排序:sort()方法
比较数组:equals()方法,比较数组中的元素是否相等
查找数组元素:binarySearch()方法,能对排序好的数组进行二分查找

冒泡排序

时间复杂度:O(n²)
算法实现:

public static void bubbleSort(int[] arr) {
	int n = arr.length-1;
	int temp = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - i; j++) {
			if (arr[j] > arr[j+1]){
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

算法优化:通过添加flag标识位减少不必要的比较判断

public static void bubbleSort(int[] arr) {
    int n = arr.length-1;
    int temp = 0;
    boolean flag = false;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            if (arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

稀疏数组

当数组中大部分元素为0或同一值时,可以使用稀疏数组来保存
稀疏数组的保存方式:

记录数组的行数和列数,以及不同值的个数
将具有不同值的元素及行列索引值记录在一个小规模数组中,从而缩小数组规模

图解:

第一行中[6, 7, 8]表示原数组为6行7列,其中包含8个不同值
其余行为各个不同值所在的行列索引和值

实现将原数组转换为稀疏数组:

public static int[][] arr2sparse(int[][] arr){
    int n = 0;
    for (int[] ints : arr) {
        for (int anInt : ints) {
            if (anInt != 0) {
                n++;
            }
        }
    }
    int[][] result = new int[n+1][3];
    result[0] = new int[]{arr.length, arr[0].length, n};
    int index = 1;
    for (int i = 0;i < arr.length; i++) {
        for (int j = 0; j < arr[0].length; j++) {
            if (arr[i][j] != 0) {
                result[index] = new int[]{i, j, arr[i][j]};
                index++;
            }
        }
    }

    return result;
}

实现还原稀疏数组:

public static int[][] sparse2arr(int[][] arr) {
    int[][] result = new int[arr[0][0]][arr[0][1]];
    for (int i = 1; i < arr.length; i++) {
        result[arr[i][0]][arr[i][1]] = arr[i][2];
    }

    return result;
}

Java内存分析

堆内存

堆内存用来存放 new 运算符创建的对象和数组,在堆中分配的内存,由Java虚拟机的自动垃级回收器来管理。

存放new的对象或数组
可以被所有线程共享,不会存放别的对象引用

在堆中创建了一个数组或对象后,同时还在栈中定义一个特殊的变量,让栈中的这个变量的取值等于数组或对象在堆内存中的首地址,栈中的这个变量就成了数组或对象的引用变量,以后就可以在程序中使用栈的引用变量访问堆中的数组或对象。引用变量是普通的变量,定义时在栈中分配,引用变量在程序运行到其作用域之外后被释放。

数组或对象本身在堆内存中分配,即使程序运行到使用new运算符创建数组或对象的语句所在的代码块之外,数组或对象本身所占据的内存也不会释放,数组或对象在没有引用变量指向它时,会变为垃圾,不能再被使用,但仍然占据内存空间不放,在随后一个不确定的时间被垃圾回收器收走(释放掉),这是导致Java比较占内存的原因。

栈内存

在方法中定义的一些基本类型的变量和对象的引用变量都在方法的栈内存中分配

存放基本变量类型(会包含这个基本类型的具体数值)
引用对象的变量(存放这个引用在堆中的存放地址)

当在一段代码块中定义一个变量时,Java就在栈内存中为这个变量分配内存空间,当超出变量的作用域后,Java会自动释放掉为该变量所分配的内存空间。

方法区

可以被所有线程共享
包含了所有的class和static变量

数组声明创建的内存分析

声明数组:int[] array = null;,在栈中存放其基本变量类型(int),声明数组时,不分配内存
创建数组:array = new int[10];,在堆中分配内存,存放new的数组,同时在栈中存放数组的引用变量(数组首地址)
给数组元素赋值,元素值存放在堆中

Java09

数组